二叉查找树的前驱后继
二叉搜索树节点的前驱后继节点
之前写过文章介绍了二叉搜索树以及其上的基本操作,但不包括求节点的前驱结点和后继节点。
这是一个很老的问题了,首先看下某节点前驱和后继节点的定义。一个节点的
前驱结点:节点val值小于该节点val值并且值最大的节点
后继节点:节点val值大于该节点val值并且值最小的节点
算法导论中给出了详细的求前驱结点和后继节点的算法,但是其中的节点数据结构包含了指向父亲节点的指针,但是一般的给出的节点不包含父亲指针,这就加大了就前驱节点和后继节点的难度。
本文在不含父指针的节点数据结构下,分析给出了时间复杂度为O(lgN)的求前驱后继结点的算法。
例子
树节点的依旧定义如下(我们的基本树节点没有指向父节点的指针):
1 struct TreeNode {
2 int val;
3 TreeNode *left;
4 TreeNode *right;
5 TreeNode(int x) : val(x), left(NULL), right(NULL) {}
6 };
给出一个二叉树如下图:
二叉树的节点val值是按照二叉树中序遍历顺序连续设定。
前驱结点
- 如图4的前驱结点是3
- 2的前驱结点是1
- 6的前驱结点是5
后继节点
- 7的后继结点是8
- 5的后继节点是6
- 2的后继节点是3
规则
根据上述例子,我们可以得到下述规则:
前驱节点
- 若一个节点有左子树,那么该节点的前驱节点是其左子树中val值最大的节点(也就是左子树中所谓的rightMostNode)
-
若一个节点没有左子树,那么判断该节点和其父节点的关系
2.1 若该节点是其父节点的右边孩子,那么该节点的前驱结点即为其父节点。
2.2 若该节点是其父节点的左边孩子,那么需要沿着其父亲节点一直向树的顶端寻找,直到找到一个节点P,P节点是其父节点Q的右边孩子(可参考例子2的前驱结点是1),那么Q就是该节点的后继节点
类似,我么可以得到求后继节点的规则。
- 若一个节点有右子树,那么该节点的后继节点是其右子树中val值最小的节点(也就是右子树中所谓的leftMostNode)
-
若一个节点没有右子树,那么判断该节点和其父节点的关系
2.1 若该节点是其父节点的左边孩子,那么该节点的后继结点即为其父节点
2.2 若该节点是其父节点的右边孩子,那么需要沿着其父亲节点一直向树的顶端寻找,直到找到一个节点P,P节点是其父节点Q的左边孩子(可参考例子2的前驱结点是1),那么Q就是该节点的后继节点
实现
求前驱节点
规则中我们是从下往上找,但实际代码中是不允许我们这么操作的(由于我们没有父亲指针),我们可以在寻找对应val节点的过程中从上向下找,并且过程中记录下parent节点和firstRParent节点(最后一次在查找路径中出现右拐的节点)。
实现如下:
1 TreeNode* getRightNode(TreeNode* root)
2 {
3 if(root ==NULL) return NULL;
4 while(root->right !=NULL)
5 root = root->right;
6 return root;
7 }
8
9
10 TreeNode* getPNode(TreeNode* root,int value,TreeNode*& parent,TreeNode*& firstRParent)
11 {
12 while(root)
13 {
14 if(root->val == value)
15 return root;
16
17 parent = root;
18 if(root->val>value)
19 {
20 root = root->left;
21 }else{
22 firstRParent = root;//出现右拐点
23 root = root->right;
24 }
25 }
26
27 return NULL;
28 }
29 //主函数
30 TreeNode* getPreNode(TreeNode* root, int value)
31 {
32 if(root)
33 {
34 TreeNode* parent =NULL;
35 TreeNode* firstRParent =NULL;
36
37 TreeNode* node = getPNode(root,value,parent ,firstRParent );
38 if(node == NULL)
39 return node;
40 if(node->left) //有左子树
41 return getRightNode(node->right);
42
43 if(NULL == parent ||(parent && (NULL == firstRParent))) return NULL; //没有前驱节点的情况
44
45 if(node == parent->right) //没有左子树 是其父节点的右边节点
46 return parent;
47 else//没有左子树 是其父节点的左边节点
48 {
49 return firstRParent ;
50 }
51
52 }
53 return root;
54 }
求后继节点
同样,求后继节点我们不能从底向上找,也是从上向下找,首先是找到对应val值的节点,顺便把其的parent节点和firstlParent节点(最后一次在查找路径中出现左拐的节点)。
1 TreeNode* getLeftNode(TreeNode* root)
2 {
3 if(root ==NULL) return NULL;
4 while(root->left !=NULL)
5 root = root->left;
6 return root;
7 }
8
9 TreeNode* getNode(TreeNode* root,int value,TreeNode*& parent,TreeNode*& firstlParent)
10 {
11 while(root)
12 {
13 if(root->val == value)
14 return root;
15
16 parent = root;//设置父亲节点
17 if(root->val<value)
18 {
19 root = root->right;
20 }else{
21 firstlParent = root;//发生了左拐
22 root = root->left;
23 }
24 }
25 return NULL;
26 }
27
28 //主函数
29 TreeNode* getNextNode(TreeNode* root, int value)
30 {
31 if(root)
32 {
33 TreeNode* parent =NULL;
34 TreeNode* firstlParent =NULL;
35
36 TreeNode* node = getNode(root,value,parent ,firstlParent );
37 if(node == NULL)
38 return node;
39 if(node->right)//有右子树
40 return getLeftNode(node->right);
41 if(NULL == parent ||(parent && (NULL == firstlParent))) return NULL; //没有后继节点的情况
42 if(node == parent->left)//没有右子树 是其父节点的左边节点
43 return parent;
44 else//没有右子树 是其父节点的右边节点
45 {
46 return firstlParent ;
47 }
48
49 }
50 return root;
51 }
总结
当然我们可以对一个二叉搜索树直接进行中序遍历,立马可以得到节点的前驱和后继节点,但是这样的方法时间复杂度为O(N),显然不是最好的方法。
本文讨论了在没有父亲指针的二叉树中如何查找一个节点的后继节点和前驱结点,算法的时间复杂度是O(lgN)。
我的旨在学过的东西不再忘记(主要使用艾宾浩斯遗忘曲线算法及其它智能学习复习算法)的偏公益性质的完全免费的编程视频学习网站:
fanrenyi.com;有各种前端、后端、算法、大数据、人工智能等课程。
版权申明:欢迎转载,但请注明出处
一些博文中有一些参考内容因时间久远找不到来源了没有注明,如果侵权请联系我删除。
博主25岁,前端后端算法大数据人工智能都有兴趣。
大家有啥都可以加博主联系方式(qq404006308,微信fan404006308)互相交流。工作、生活、心境,可以互相启迪。
聊技术,交朋友,修心境,qq404006308,微信fan404006308
26岁,真心找女朋友,非诚勿扰,微信fan404006308,qq404006308
人工智能群:939687837
作者相关推荐
感悟总结
其它重要感悟总结
感悟总结200813
最近心境200830
最近心境201019
201218-210205