二叉搜索树的前驱、后驱

二叉搜索树(Binary Search Tree) 简称BST,也叫二叉排序树, 它是学习平衡树的基础.
二叉搜索树的定义如下:
1.若任意节点的左子树不空，则左子树上所有节点的值均小于它的根节点的值；
2.若任意节点的右子树不空，则右子树上所有节点的值均大于它的根节点的值；
3.任意节点的左、右子树也分别为二叉查找树；
4.没有键值相等的节点。
5.二叉搜索树可以为一棵空树。

BST中序遍历能得到有序序列是其最常用的特性.

下图即为二叉搜索树

BST

定义如下:

public class TreeNode {
    int val;
    TreeNode left ;
    TreeNode right ;
    TreeNode parent ;

    public TreeNode(int val) {
        this.val = val;
    }
}

前驱:小于该节点值的最大节点(中序遍历时的上一个节点)

如上图:
4的前驱结点是3
2的前驱结点是1
6的前驱结点是5

查找规则如下:
1.有左孩子找左子树中最右边的值
没有左孩子则判断在其父节点的位子
2.如果是父节点的右孩子则父节点即是前驱节点
3.如果是父节点的左孩子则向上寻找一个节点Q 直到Q节点是其父节点P的右孩子 p节点即为前驱节点
Java代码实现如下:

    // 二叉搜索树前驱 小于该节点的最大节点(中序遍历时的上一个节点)
    public static TreeNode preNode(TreeNode node) {
        if (node == null)
            return null;
        // 1.有左孩子 找左子树中最右边的值
        if (node.left != null) {
            TreeNode child = node.left;
            while (child != null && child.right != null) {
                child = child.right;
            }
            return child;
        }
        // 没有左孩子 则判断在其父节点的位子
        // 2.如果是父节点的右孩子则父节点即是前驱节点
        // 3.如果是父节点的左孩子则 向上寻找一个节点Q 直到Q节点是其父节点P的右孩子 p节点即为前驱节点
        TreeNode p = node.parent;
        while (p != null && node == p.left) {
            node = p;
            p = p.parent;
        }
        return p;
    }

二叉搜索树后驱:大于该节点的最小节点(中序遍历时的下一个节点)

如上图:
7的后继结点是8
5的后继节点是6
2的后继节点是3
查找规则如下:
1.有右孩子右子树中最小节点即为后驱节点
没有右孩子判断在其父节点的位子
2.如果是父节点的左孩子则父节点就是后驱节点
3.如果是父节点的右孩子则继续向上寻找一节点Q 直到Q节点是其父节点P的左节点 p节点即为后驱节点
Java代码实现如下:

    // 二叉搜索树后驱 大于该节点的最小节点(中序遍历时的下一个节点)
    public static TreeNode postNode(TreeNode node) {
        if (node == null)
            return null;
        // 1.有右孩子 右子树中最小节点即为后驱节点
        if (node.right != null) {
            TreeNode child = node.right;
            while (child != null && child.left != null) {
                child = child.left;
            }
            return child;
        }

        // 没有右孩子 判断在其父节点的位子
        // 2.如果是父节点的左孩子 则父节点就是后驱节点
        // 3.如果是父节点的右孩子 则继续向上寻找一节点Q 直到Q节点是其父节点P的左节点 p节点即为后驱节点
        TreeNode p = node.parent;
        while (p != null && node == p.right) {
            node = p;
            p = p.parent;
        }
        return p;
    }

最后编辑于：2019.08.06 16:32:59