摘要：又是來自我的好朋友的投稿，以下是原文基本定義二分搜索樹的每個子節(jié)點最多有兩個葉子節(jié)點二分搜索樹的每個節(jié)點最多有一個根節(jié)點存儲的元素必須具有可比較性二分搜索樹每個子節(jié)點的值大于其左子節(jié)的所有節(jié)點的值小于其右子節(jié)點的所有節(jié)點的值二分搜索樹不一定

又是來自我的好朋友 EvilSay 的投稿，以下是原文：

二分搜索樹的每個子節(jié)點最多有兩個葉子節(jié)點

二分搜索樹的每個節(jié)點最多有一個根節(jié)點

存儲的元素必須具有可比較性

二分搜索樹每個子節(jié)點的值

大于其左子節(jié)的所有節(jié)點的值

小于其右子節(jié)點的所有節(jié)點的值

二分搜索樹不一定是滿的

/**
 * @Author: EvilSay
 * @Date: 2019/8/6 19:00
 */
public class BSTMain > {
    private class Node {
        public E e;
        private Node left, right;

        public Node(E e) {
            this.e = e;
            left = null;
            right = null;
        }
    }

    //根節(jié)點
    private Node root;
    private int size;

    public BSTMain() {
        root = null;
        size = 0;
    }

    public int size() {
        return size;
    }

    public boolean isEmpty() {
        return size == 0;
    }
    public void add(E e){

        root = add(this.root, e);

    }

    // 向node為根的二分搜索樹中插入元素E,遞歸算法
    // 返回插入新節(jié)點后二分搜索樹的根
    private Node add(Node node, E e){

        if (node == null){

            size ++;
            return new Node(e);
        }

        if (e.compareTo(node.e) < 0)
            node.left = add(node.left, e);
        else if (e.compareTo(node.e) > 0)
            node.right = add(node.right,e);
        return node;
    }

    // 看二分搜索樹中是否包含元素e
    public boolean contains(E e){
        return contains(root,e);
    }

    // 看以node為根的二分搜索樹中是否包含元素e,遞歸算法
    private boolean contains(Node node, E e){
        if (node == null)
            return false;
        if (e.compareTo(node.e) == 0)
            return true;
        else if (e.compareTo(node.e) < 0)
            return contains(node.left, e);
        else
            return contains(node.right,e);
    }

    @Override
    public String toString() {
        StringBuilder res = new StringBuilder();
        generateBSTSString(root,0,res);
        return res.toString();
    }

    // 生成以node為根節(jié)點，深度為depth的描述二叉樹的字符串
    private void generateBSTSString(Node root, int depth, StringBuilder res) {
        if (root == null){
            res.append(generateDepthString(depth) + "null
");
            return;
        }
        res.append(generateDepthString(depth) + root.e + "
");
        generateBSTSString(root.left, depth + 1 ,res);
        generateBSTSString(root.right, depth + 1, res);

    }

    private String generateDepthString(int depth) {
        StringBuilder res = new StringBuilder();
        for (int i = 0; i < depth; i++)
            res.append("--");
        return res.toString();
    }
}

從圖上我們看出二分搜索樹每個節(jié)點的值大于其左子節(jié)的所有節(jié)點的值小于其右子節(jié)點的所有節(jié)點的值。

前序遍歷也叫先序遍歷，訪問順序是根左右，也就是先訪問根節(jié)點，再到左子樹，最后才到右子樹。所以上圖所示的訪問順序是 5、3、2、4、8、7、9。

二分搜索樹前序遍歷遞歸版與非遞歸版

    //前序遍歷以node為根的二分搜索樹，遞歸算法
    private void preOrder(Node node){

        if (node == null)
            return;

        System.out.println(node.e);
        preOrder(node.left);
        preOrder(node.right);
    }
    
    //二分搜索樹的前序遍歷遞歸調(diào)用
    public void preOrder(){
        preOrder(root);
    }
    
    //二分搜索樹的前序遍歷非遞歸寫法
    public void preOrderNG(){
        Stack stack = new Stack<>();
        //根節(jié)點
        stack.push(root);

        while (!stack.isEmpty()){
            Node cur = stack.pop();

            System.out.println(cur.e);
            //判斷是否還有葉子節(jié)點
            if (cur.right != null)
                stack.push(cur.right);
            if (cur.left != null)
                stack.push(cur.left);
        }
    }

理解非遞歸的實現(xiàn)邏輯、推導(dǎo)出前序遞歸的實現(xiàn)

創(chuàng)建一個堆棧，我們把根節(jié)點 5 推入棧中，接下來我們就要訪問 5 這個根節(jié)點了，所有把 5 從棧中推出 。

推出的元素有 {5}，棧中的元素有 [] 。

在推入 5 的子節(jié)點就是 3，8，我們先入后出，先推入 8 再推入 3，現(xiàn)在堆棧的元素有 [8，3]，棧頂?shù)?3 就是我們下一次要訪問的節(jié)點所以把 3 推出 。

推出的元素有 {5,3}，棧中的元素有 [8] 。

在推入 3 的子節(jié)點就是 2，4 繼續(xù)先入后出，先推入 4 再推入 2，現(xiàn)在堆棧的元素有 [8,4,2]，棧頂?shù)?2 就是我們下一次要訪問的節(jié)點所以把 2 推出 。

推出的元素有 {5,3,2}，棧中的元素有 [8,4] 。

訪問棧頂 4，由于 2 和 4 沒有子節(jié)點。所以我們直接把棧頂中的 4 推出 。

推出的元素有 {5,3,2,4}，棧中的元素有 [8] 。

訪問棧頂 8 把 8 推出棧堆，再把 8 的子節(jié)點 7、9 推入棧中，先推入 9 后推入 7 。

推出的元素有 {5,3,2,4,8}，棧中的元素有 [9,7] 。

訪問 7，沒有子節(jié)點，推出。

推出的元素有 {5,3,2,4,8,7}，棧中的元素有 [9] 。

訪問 9，沒有子節(jié)點，推出。

推出的元素有 {5,3,2,4,8,7,9}，棧中的元素有 [] 。

中序遍歷，訪問順序是左根右，也就是先訪問左子樹，再到根節(jié)點，最后才到右子樹。所以上圖所示的訪問順序是 2、3、4、5、7、8、9。

二分搜索樹中序遍歷遞歸版與非遞歸版

    //遞歸調(diào)用
    public void inOrder(){
        inOrder(root);
    }
    //二分搜索樹的中序遍歷遞歸寫法
    private void inOrder(Node root){
        if (root == null)
            return;

        inOrder(root.left);
        System.out.println(root.e);
        inOrder(root.right);
    }
    //二分搜索樹中序遍歷給遞歸寫法
    public void preInOrderNG(){
        // 創(chuàng)建棧,和前序遍歷類似
        Stack stack = new Stack<>();
        
        Node node = root;
        //添加暫時完畢，開始pop元素
        while(node!=null || stack.size()>0 ){

            while(node!=null){
                stack.push(node);
                node = node.left;
            }
            //一邊pop并且一邊進(jìn)行判斷，右結(jié)點不會null的，右子樹，繼續(xù)按照添加方法，將最左結(jié)點全部添加進(jìn)去
            if(stack.size()>0){
                Node pop = stack.pop();
                System.out.print(pop.e+"  ");
                if(pop.right!=null){
                    node = pop.right;
                }
            }
        }

理解非遞歸的實現(xiàn)邏輯、推導(dǎo)出中序遞歸的實現(xiàn)

首先我們把 5 這個節(jié)點推入棧中，再把 5 的左子節(jié)點 3 推入，再把 3的 左子節(jié)點 2 推入，再把 2 的左子節(jié)點推入(此時 2 的左子節(jié)點為空，node==null while 循環(huán)退出)。

推出的元素有 {}，棧中的元素有 [5,3,2]。

node 為空，但我們棧中還有元素，訪問棧頂元素 2，并查看 2 是否有右子節(jié)點。沒有則推出棧并結(jié)束循環(huán)。

推出的元素有 {2}，棧中的元素有 [5,3]。

訪問棧頂元素 3，把 3 推出棧中，并把 3 的右子節(jié)點 4 推入棧中，結(jié)束循環(huán)。

推出的元素有 {2,3}，棧中的元素有 [5]。

訪問棧頂元素5，把5推出棧中。把5的右子節(jié)點8推入棧中，并把8的左子節(jié)點7推入棧中,結(jié)束循環(huán)。

推出的元素有 {2,3,5}，棧中的元素有 [8,7]

訪問棧頂元素 7，并查看 2 是否有右子節(jié)點。沒有則推出棧并結(jié)束循環(huán)。

推出的元素有 {2,3,5,7}，棧中的元素有 [8]。

訪問棧頂元素 8，把 8 推出棧中。把 8 的右子節(jié)點 9 推入棧中

推出的元素有 {2,3,5,7,8}，棧中的元素有 [9]。

訪問棧頂元素 9，并查看 2 是否有右子節(jié)點。沒有則推出棧并結(jié)束循環(huán)。

推出的元素有 {2,3,4,5,7,8,9}，棧中的元素有 []。

中序遍歷，訪問順序是左右根，也就是先訪問左子樹，再到右子樹，最后才到根節(jié)點。所以上圖所示的訪問順序是 2、4、3、7、9、8、5。

二分搜索樹后序遍歷遞歸版與非遞歸版

//遞歸調(diào)用
public void postOrder() {
    postOrder(root);
} 

//二分搜索樹的后序遍歷遞歸方法
private void postOrder(Node node){
    if (node == null)
        return;

    postOrder(node.left);
    postOrder(node.right);
    System.out.println(node.e);
} 

public void postOrderNG(){
    Stack stack = new Stack<>();
    //利用一個list集合記錄已將被遍歷過的根節(jié)點，防止產(chǎn)生死循環(huán)
    ArrayList list = new ArrayList<>();
    Node node = root;
    Node proud; 
    int flag; 

    //首頁檢查完樹的左子樹，再右子數(shù)，最后將根節(jié)點輸出
    while (node != null || stack.size() > 0){
        //將最左子樹添加完畢
        while (node != null){
            stack.push(node);

            node = node.left;
        } 

        //和中序遍歷相似，為先輸出左子節(jié)點，但是做節(jié)點輸出完畢之后，不能直接將根節(jié)點彈出，而是必須先將右節(jié)點彈出，
        //最后再將根節(jié)點彈出來，就會牽扯到一個根節(jié)點的訪問狀態(tài)的問題，是否已經(jīng)被遍歷過了
        if (stack.size() > 0){

            Node peek = stack.peek();
            if (peek.right != null){
                boolean con = list.contains(peek);
                if (con){
                    Node pop = stack.pop();
                    System.out.println(pop.e);
                }else{
                    list.add(peek);
                    node = peek.right;
                }
            }else {
                Node pop = stack.pop();
                System.out.println(pop.e);
            }

        }

    }
}

理解非遞歸的實現(xiàn)邏輯、推導(dǎo)出后序遞歸的實現(xiàn)

把 5 這個節(jié)點推入棧中，再把 5 的左子節(jié)點 3 推入，再把 3 的左子節(jié)點 2 推入，再把 2 的左子節(jié)點推入(此時 2 的左子節(jié)點為空，node==null while 循環(huán)退出)。

推出的元素有 {}，棧中的元素有 [5,3,2]。

node 為空但我們棧中還有元素，訪問棧頂元素 2，并查看 2 是否有左子節(jié)點。沒有則推出棧并結(jié)束循環(huán)。

推出的元素有 {2}，棧中的元素有 [5,3]。

訪問棧頂元素 3，3 的右子節(jié)為 4，判斷 list 中是否有 3，沒有則把 3 放入 list 中并把 node 賦值為 4 結(jié)束循環(huán)。

推出的元素有 {2}，棧中的元素有 [5,3]。

node 為 4，把 4 推入棧中，并訪問棧頂元素 4，并查看 4 是否有右子節(jié)點。沒有則推出棧并結(jié)束循環(huán)。

推出的元素有 {2,4}，棧中的元素有 [5,3]。

訪問棧頂元素 3，list 中有 3，把 3 的推出棧中并結(jié)束循環(huán)。

推出的元素有 {2,4,3}，棧中的元素有 [5]。

訪問棧頂元素 5，5 的右子節(jié)為 8，判斷 lis t中是否有 8，沒有則把 5 放入 list 中并把 node 賦值為 8 結(jié)束循環(huán)。

推出的元素有 {2,4,3}，棧中的元素有 [5]。

node 為 8，把 8 推入棧中，并訪問棧頂元 素8，8 有左子節(jié)點為 7。把 7 推入棧中。

推出的元素有 {2,4,3}，棧中的元素有 [5,8,7]。

訪問棧頂元素 7，并查看 7 是否有右子節(jié)點。沒有則推出棧并結(jié)束循環(huán)。

推出的元素有 {2,4,3,7}，棧中的元素有 [5,8]。

訪問棧頂元素 8，8 的右子節(jié)點為 9。判斷 list 中是否有 9，沒有則把 8 放入 list 中并把 node 并把 node 賦值為 9 結(jié)束循環(huán)。

推出的元素有 {2,4,3,7}，棧中的元素有 [5,8]。

node 為 9，把 9 推入棧中，并訪問棧頂元素 9，并查看 9 是否有右子節(jié)點。沒有則推出棧并結(jié)束循環(huán)。

推出的元素有 {2,4,3,7,9}，棧中的元素有 [5,8]。

訪問棧頂元素 8，list 中有 8，把 8 的推出棧中并結(jié)束循環(huán)。

推出的元素有 {2,4,3,7,9,8}，棧中的元素有 [5]。

node 為空棧中還有元素，訪問棧頂元素 5，list 中有 5，把 5 的推出棧中并結(jié)束循環(huán)。

推出的元素有 {2,4,3,7,9,8,5}，棧中的元素有 []。

推薦閱讀：

1、java | 什么是動態(tài)代理

2、SpringBoot?| 啟動原理

3、SpringBoot | 自動配置原理