二叉搜索樹(Binary Search Tree) 簡(jiǎn)稱BST,也叫二叉排序樹, 它是學(xué)習(xí)平衡樹的基礎(chǔ).
二叉搜索樹的定義如下:
1.若任意節(jié)點(diǎn)的左子樹不空，則左子樹上所有節(jié)點(diǎn)的值均小于它的根節(jié)點(diǎn)的值；
2.若任意節(jié)點(diǎn)的右子樹不空，則右子樹上所有節(jié)點(diǎn)的值均大于它的根節(jié)點(diǎn)的值；
3.任意節(jié)點(diǎn)的左、右子樹也分別為二叉查找樹；
4.沒有鍵值相等的節(jié)點(diǎn)。
5.二叉搜索樹可以為一棵空樹。

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

下圖即為二叉搜索樹

BST

定義如下:

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

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

前驅(qū):小于該節(jié)點(diǎn)值的最大節(jié)點(diǎn)(中序遍歷時(shí)的上一個(gè)節(jié)點(diǎn))

如上圖:
4的前驅(qū)結(jié)點(diǎn)是3
2的前驅(qū)結(jié)點(diǎn)是1
6的前驅(qū)結(jié)點(diǎn)是5

查找規(guī)則如下:
1.有左孩子 找左子樹中最右邊的值
沒有左孩子 則判斷在其父節(jié)點(diǎn)的位子
2.如果是父節(jié)點(diǎn)的右孩子則父節(jié)點(diǎn)即是前驅(qū)節(jié)點(diǎn)
3.如果是父節(jié)點(diǎn)的左孩子則 向上尋找一個(gè)節(jié)點(diǎn)Q 直到Q節(jié)點(diǎn)是其父節(jié)點(diǎn)P的右孩子 p節(jié)點(diǎn)即為前驅(qū)節(jié)點(diǎn)
Java代碼實(shí)現(xiàn)如下:

    // 二叉搜索樹前驅(qū) 小于該節(jié)點(diǎn)的最大節(jié)點(diǎn)(中序遍歷時(shí)的上一個(gè)節(jié)點(diǎn))
    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;
        }
        // 沒有左孩子 則判斷在其父節(jié)點(diǎn)的位子
        // 2.如果是父節(jié)點(diǎn)的右孩子則父節(jié)點(diǎn)即是前驅(qū)節(jié)點(diǎn)
        // 3.如果是父節(jié)點(diǎn)的左孩子則 向上尋找一個(gè)節(jié)點(diǎn)Q 直到Q節(jié)點(diǎn)是其父節(jié)點(diǎn)P的右孩子 p節(jié)點(diǎn)即為前驅(qū)節(jié)點(diǎn)
        TreeNode p = node.parent;
        while (p != null && node == p.left) {
            node = p;
            p = p.parent;
        }
        return p;
    }

二叉搜索樹后驅(qū):大于該節(jié)點(diǎn)的最小節(jié)點(diǎn)(中序遍歷時(shí)的下一個(gè)節(jié)點(diǎn))

如上圖:
7的后繼結(jié)點(diǎn)是8
5的后繼節(jié)點(diǎn)是6
2的后繼節(jié)點(diǎn)是3
查找規(guī)則如下:
1.有右孩子 右子樹中最小節(jié)點(diǎn)即為后驅(qū)節(jié)點(diǎn)
沒有右孩子 判斷在其父節(jié)點(diǎn)的位子
2.如果是父節(jié)點(diǎn)的左孩子 則父節(jié)點(diǎn)就是后驅(qū)節(jié)點(diǎn)
3.如果是父節(jié)點(diǎn)的右孩子 則繼續(xù)向上尋找一節(jié)點(diǎn)Q 直到Q節(jié)點(diǎn)是其父節(jié)點(diǎn)P的左節(jié)點(diǎn) p節(jié)點(diǎn)即為后驅(qū)節(jié)點(diǎn)
Java代碼實(shí)現(xiàn)如下:

    // 二叉搜索樹后驅(qū) 大于該節(jié)點(diǎn)的最小節(jié)點(diǎn)(中序遍歷時(shí)的下一個(gè)節(jié)點(diǎn))
    public static TreeNode postNode(TreeNode node) {
        if (node == null)
            return null;
        // 1.有右孩子 右子樹中最小節(jié)點(diǎn)即為后驅(qū)節(jié)點(diǎn)
        if (node.right != null) {
            TreeNode child = node.right;
            while (child != null && child.left != null) {
                child = child.left;
            }
            return child;
        }

        // 沒有右孩子 判斷在其父節(jié)點(diǎn)的位子
        // 2.如果是父節(jié)點(diǎn)的左孩子 則父節(jié)點(diǎn)就是后驅(qū)節(jié)點(diǎn)
        // 3.如果是父節(jié)點(diǎn)的右孩子 則繼續(xù)向上尋找一節(jié)點(diǎn)Q 直到Q節(jié)點(diǎn)是其父節(jié)點(diǎn)P的左節(jié)點(diǎn) p節(jié)點(diǎn)即為后驅(qū)節(jié)點(diǎn)
        TreeNode p = node.parent;
        while (p != null && node == p.right) {
            node = p;
            p = p.parent;
        }
        return p;
    }