算法导论笔记-疑问篇之 找中序遍历上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的最低祖先结点。

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

查看更多 下一篇