首页 > 代码库 > D&F学数据结构系列——前驱和后继
D&F学数据结构系列——前驱和后继
前驱和后继
本文所述为二叉排序树的前驱和后继,如果想了解二叉排序树的概念,可以参考我的博文***
给定一个二叉查找树中的结点,有时候要求找出在中序遍历顺序下它的后继。如果所有的关键字均不同,则某一结X点的后继就是所有(结点值)大于X的结点中最小的那个。
包含两种情况:
情况一:结点X的右子树非空,则X的后继是其右子树中最左的结点
情况二:结点X的右子树为空,设X的后继为Y。则Y是X的最低祖先结点,且Y的左儿子也是X的祖先(X自身也可以看做是X的祖先)
1 BT* TreeSuccessor(BT* T) 2 { 3 BT* S; 4 if(!T) return NULL; 5 if(T->right) 6 { 7 for(S=N->right;S->left;S=S->left); 8 return S; 9 }10 for(S=T;S->parent&&(S->parent->right==S);S=S->parent);11 return S->parent;12 }
相应的,中序遍历下某结点X的前驱就是所有(结点值)小于X的结点中最大的那个。也包含两种情况:
情况一:结点X的左子树非空,则X的前驱是其左子树中最右的结点
情况二:结点X的左子树为空,设X的后继为Y。则Y是X的最低祖先结点,且Y的右儿子也是X的祖先(X自身也可以看做是X的祖先)
1 BT* TreePredecessor (BT* T) 2 { 3 BT * P; 5 if (!T) return NULL; 6 if (T->left) { 7 for (P = T->left; P->right; P = P->right); 8 return P; 9 }11 for (P = t; P->parent && (P->parent->left == P); P = P->parent);12 return P->parent;13 }
这里有一篇很详细的Bloghttp://blog.csdn.net/markcnsc/article/details/8566466
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。