本文参考该作者文章当作编程笔记： 作者：Hawstein 出处：http://hawstein.com/posts/ctci-solutions-contents.html
Q:
给定二叉查找树的一个结点， 写一个算法查找它的“下一个”结点(即中序遍历后它的后继结点)， 其中每个结点都有指向其父亲的链接。
思路：
题目是在升序排列的情况下，查找他的下一个的节点。先在它的右孩子里找最小的节点，即下一个节点；如果没有右孩子，那么向上找它的父亲节点，直到找到比他大的父亲节点，即下一个节点。
（如果他是他父亲节点的右孩子，那么继续向上找直到找到某个节点是其父亲节点的左孩子，那么该父亲节点就是所找的下一个节点；如果他是它的父亲节点的左孩子，那么它的父亲节点就是所找的下一个节点。）
CODE：
1 #include<stdio.h> 2 #include<stdlib.h> 3 #include<limits.h> 4 #define N 9 /*树的结点数*/ 5 #define key(A) (A) 6 #define less(A,B) (A<B) 7 /*树的结构*/ 8 typedef struct node 9 { 10 char item; 11 struct node *l,*r,*parent; 12 }node; 13 /*构造2叉树*/ 14 void insertNode(node **h,node *parent,char s) 15 { 16 if((*h)==NULL) 17 { 18 (*h)=(node *)malloc(sizeof(node)); 19 (*h)->item=s; 20 (*h)->parent=parent; 21 (*h)->l=NULL; 22 (*h)->r=NULL; 23 return; 24 } 25 if(less(s,(*h)->item)) 26 insertNode(&((*h)->l),*h,s); 27 else 28 insertNode(&((*h)->r),*h,s); 29 } 30 /*打印2叉树*/ 31 void printfNode(char item,int blank) 32 { 33 int i; 34 for(i=0;i<blank;++i) 35 printf(" "); 36 printf("%c ",item); 37 } 38 void traversePre(node *h,int blank) 39 { 40 if(h==NULL) 41 {printfNode('*',blank); return;} 42 printfNode(h->item,blank); 43 traversePre(h->l,blank+1); 44 traversePre(h->r,blank+1); 45 } 46 /*查找给定节点的最小节点，即它的左孩子叶子节点*/ 47 node * findRChildMin(node *h) 48 { 49 while(h->l) 50 h=h->l; 51 return h; 52 } 53 /*查找它的下一个比他大的节点*/ 54 node * findNextNode(node *h) 55 { 56 if(h==NULL) 57 return NULL; 58 if(h->r) 59 return findRChildMin(h->r); /*该节点的右孩子节点一定比它大*/ 60 node * t=h->parent; 61 while(t && less(t->item,h->item)) /*向上找比他大的父亲节点*/ 62 { 63 t=t->parent; 64 } 65 return t; 66 } 67 int main() 68 { 69 node *head=NULL; 70 char s[]="DBCDEFAYZ"; 71 int i; 72 for(i=0;i<N;i++) 73 insertNode(&head,NULL,s[i]); 74 traversePre(head,0); /*前序遍历打印树*/ 75 node * t=findNextNode(head->r->r->r->r); 76 if(t) 77 printf("%c ",t->item); 78 return 0; 79 }