算法导论笔记-疑问篇之 找中序遍历上x结点的后继

算法导论笔记-疑问篇之 找中序遍历下x结点的后继

C/C++ code

//查找中序遍历下x结点的后继，后继是大于key[x]的最小的结点  
node *Tree_Successor(node *x)  
{  
    //如果有右孩子  
    if(x->right != NULL)  
        //右子树中的最小值  
        return Tree_Minimum(x->right);  
    //如果x的右子树为空且x有后继y，那么y是x的最低祖先结点，且y的左儿子也是  
    node *y = x->p;  
    while(y != NULL && x == y->right)  
    {  
        x = y;  
        y = y->p;  
    }  
    return y;  
}  

想问一下：代码中 while(y != NULL && x == y->right) 为什么加上 x == y->right
第二问书上说：如果求的节点没有有字数，那么后继的最低的祖先。
这里最低如何理解？

------解决方案--------------------
1.因为当x!=y->right时！即x=y->left时.y结点就是X结点的后继，所以不用循环！当x=y->right时说明X的后继是Y结点的父结点。所以需要循环！

2.如果x的右子树为空且x有后继y，那么y是x的最低祖先结点，且y的左儿子也是 。意思就是说如果X右子树为空，且有后继，说明X的后继肯定是X的父节点，或者是X父节点的父节点，简洁的说就是那么y是x的最低祖先结点。

楼主最好用笔画画图，分清楚说明是中序遍历。中序遍历规则是：左孩子，结点，右孩子。