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

前驱节点

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

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

思路：

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

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

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的左子树中

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;
}
}

最后

以上就是悦耳野狼为你收集整理的数据结构与算法---树---二叉树的前驱节点、后继节点的全部内容，希望文章能够帮你解决数据结构与算法---树---二叉树的前驱节点、后继节点所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。