首页 > 代码库 > D&F学数据结构系列——前驱和后继

D&F学数据结构系列——前驱和后继

2024-07-13 18:41:16   221人阅读

前驱和后继

本文所述为二叉排序树的前驱和后继，如果想了解二叉排序树的概念，可以参考我的博文***

 

给定一个二叉查找树中的结点，有时候要求找出在中序遍历顺序下它的后继。如果所有的关键字均不同，则某一结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


联系
我们