数据结构与算法---树---二叉树的前驱节点、后继节点

127 阅读 0 评论 84 点赞

我是靠谱客的博主悦耳野狼，这篇文章主要介绍数据结构与算法---树---二叉树的前驱节点、后继节点，现在分享给大家，希望可以做个参考。

前驱节点

何为前驱节点？
前驱节点，指的是以中序遍历，遍历二叉树，某一个节点的前一个节点，被称为其前驱节点。
也就是，某一节点的左子树的右子节点的右子节点的右节点。。。

特殊情况，如果是二叉搜索树，则前驱节点是按从小到大的顺序，比其前面一个节点。

思路：

如果node.left != null;
则循环，node.left.right.right.right…直至为空，则找到了其前驱节点。

如果node.left == null;
如果node.parent == null;则没有前驱
如果node.parent != null;则前驱节点为node.parent.parent.parent…;
终止条件：node在parent的右子树中

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public static TreeNode preNode(TreeNode root)
{
if(root == null) return null;
TreeNode node = root.left;
if(node != null) {
while(node.right != null) {
node = node.right;
}
return node;
}else {
while(node.parent != null && node == node.parent.left) {
node = node.parent;
}
//来到这里包含两种情况：
//node.parent == null
//node = node.parent.right
return node.parent;
}
}

后继节点

中序遍历的某一节点的后一个节点，被称为后继节点
参照前驱节点，不难写成后继节点

思路：

如果node.right != null;
则循环，node.right.left.left.left…直至为空，则找到了其后继节点。

如果node.right == null;
如果node.parent == null;则没有后继
如果node.parent != null;则后继节点为node.parent.parent.parent…;
终止条件：node在parent的左子树中

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public static TreeNode postNode(TreeNode root) {
if(root == null) return null;
TreeNode node = root.right;
if(node != null) {
while(node.left != null)
{
node = node.left;
}
return node;
}else {
while(node.parent != null && node == node.parent.right)
{
node = node.parent;
}
return node.parent;
}
}