1.1. 樹的基本概念

樹是n(n>=0)個節點的有限集，當n為0時，稱為空樹。對於任意一棵非空樹，應滿足：

1） 有且僅有一個特定的稱為根的節點

2）當n>1時，其餘節點可分為m(m>0)個互不相交的有限集，每個集合本省又是一棵樹，並且稱為根的子樹

由此可見，樹的定義是遞歸的，即在樹的定義中有用到了自身，樹是一種遞歸的數據結構，樹作為一種邏輯結構，同時也是一種分層結構，具有以下特點：

1）樹的根節點沒有前驅，除根節點外的所有節點有且隻有一個前驅

2）樹中所有節點可以有零個或多個後繼

對於n個節點的樹，有n-1條邊。

1.2. 二叉樹的概念

二叉樹本質上也是樹，它的特點是，每個節點至多隻有兩棵子樹，並且二叉樹的子樹有左右之分，它是有序樹，如果將其左右子樹顛倒，那麼會成為另一棵不同的二叉樹，二叉樹的5種基本形態如下：

1.3. 幾種特殊的二叉樹

1）斜樹

所有節點都隻有左子樹的二叉樹，叫作左斜樹，所有節點都隻有右子樹的二叉樹叫作右斜樹。這兩者統稱為斜樹。

2）滿二叉樹

一棵高度為h，且含有2^h - 1個節點的二叉樹，稱為滿二叉樹，即樹的每層都含有最多的節點，滿二叉樹的葉子節點集中在二叉樹的最下一層，並且除葉子節點之外的每個節點，度數均為2。假設編號從根節點開始為1，自上而下，從左到右，那麼，對於編號為n的節點，如果有父節點， 父節點為n/2，如果有左孩子，左孩子為2n，如果有右孩子，右孩子為2n 1， 如下圖所示：

3）完全二叉樹

對於高度為h，有n個節點的二叉樹，除了第h層外，其他各層(1~h-1)的節點數都達到最大格式（即1~h-1層是一個滿二叉樹），第h層所有節點都連續集中在最左邊，這就是完全二叉樹。

2. 二叉搜索樹

二叉搜索樹有以下特點：

1）左子樹上所有節點的值均小於它的根節點的值

2）右子樹上所有節點的值均大於它的根節點的值

3）任意節點的左右子樹也分別為二叉搜索樹

4）沒有鍵值相等的節點

2.1. 二叉搜索樹的插入

1）對於插入，如果一開始為空樹，那麼新建一個節點，作為該樹的根節點。

2）當不為空樹時，判斷插入的數字，與當前根節點的大小進行比較，如果比當前值小，插入到左子樹

3）當不為空樹時，判斷插入的數字，與當前根節點的大小進行比較，如果比當前值大，插入到右子樹

2.2. 二叉搜索樹的查找

1）判斷當前節點是否為空，為空直接返回

2）當前節點不為空，判斷查詢值域當前節點值的大小，如果比當前值小，進入左子樹查詢

3）當前節點不為空，判斷查詢值域當前節點值的大小，如果比當前值大，進入右子樹查詢

2.3. 二叉搜索樹的刪除

1）判斷當前節點是否為空，為空直接返回

2）當前節點不為空，刪除值小於當前節點值，進入左子樹刪除

3）當前節點不為空，刪除值大於當前節點值，進入右子樹刪除

4）當前節點不為空，刪除值等於當前值：

4.1）如果當前節點左右子樹都為空，直接刪除當前節點

4.2）如果當前節點左子樹不為空，右子樹為空，使用左節點取代當前節點

4.3）如果當前節點右子樹不為空，左子樹為空，使用右節點取代當前節點

4.4）左右子樹都不為空，選擇左子樹的最右節點或右子樹的最左節點，代替當前節點

2.4. 遍歷

對於樹的遍歷，一般有前序遍歷、中序遍歷、後序遍歷這幾種方式。

1）前序遍歷：對樹按照根、左、右的規律進行訪問，如下圖所示，遍歷結果為F,B,A,D,C,E,G,I,H

2) 中序遍歷：對樹，按照左、根、右的規律進行訪問。如下圖所示，遍歷結果為:A,B,C,D,E,F,G,H,I

3) 後序遍歷：對樹，按照左、右、根的規律進行訪問。如下圖所示，遍歷結果為:A, C, E, D, B,H, I, G, F

2.5. 二叉搜索樹示例代碼

完整代碼如下：

public class BinarySearchTree {
    class Node {
        private int val;
        private Node left;
        private Node right;
        public Node(int val) {
            this.val = val;
            this.left = null;
            this.right = null;
        }
        public void setVal(int val) {
            this.val = val;
        }
        public int getVal() {
            return this.val;
        }
        public Node getLeft() {
            return left;
        }
        public void setLeft(Node left) {
            this.left = left;
        }
        public Node getRight() {
            return right;
        }
        public void setRight(Node right) {
            this.right = right;
        }
    }
    // 根節點
    private Node root;
    private Node insert(Node root, int val) {
        if (root == null) {
            root = new Node(val);
            return root;
        }
        if (root.val < val) {
            root.right = insert(root.right, val);
        } else if(root.val > val) {
            root.left = insert(root.left, val);
        }
        return root;
    }
    private Node search(Node root, int val) {
        if (root == null) {
            return null;
        }
        if (root.val < val) {
            return search(root.right, val);
        } else if (root.val > val) {
            return search(root.left, val);
        }
        return root;
    }
    private Node remove(Node root, int val) {
        if (root == null) {
            return null;
        }
        if (root.val < val) {
            return remove(root.right, val);
        } else if (root.val > val) {
            return remove(root.left, val);
        }
        if (root.left == null && root.right == null) {
            root = null;
            return root;
        } else if (root.left == null) {
            Node temp = root;
            root = root.right;
            temp = null;
            return root;
        } else if (root.right == null) {
            Node temp = root;
            root = root.left;
            temp = null;
            return root;
        } else {
            Node min = findMin(root.right);
            root.val = min.val;
            root.right = remove(root.right, root.val);
        }
        return root;
    }
    private Node findMin(Node t) {
        while (t.left != null) {
            t = t.left;
        }
        return t;
    }
    private void preOrderTraversal(Node t) {
        if (t == null) {
            return;
        }
        System.out.println(t.val);
        preOrderTraversal(t.left);
        preOrderTraversal(t.right);
    }
    private void midOrderTraversal(Node t) {
        if (t == null) {
            return;
        }
        midOrderTraversal(t.left);
        System.out.println(t.val);
        midOrderTraversal(t.right);
    }
    private void postOrderTraversal(Node t) {
        if (t == null) {
            return;
        }
        postOrderTraversal(t.left);
        postOrderTraversal(t.right);
        System.out.println(t.val);
    }
    public BinarySearchTree() {
    }
    public void insert(int val) {
        root = insert(root, val);
    }
    public Node search(int val) {
        return search(root, val);
    }
    public void remove(int val) {
        root = remove(root, val);
    }
    public void preOrderTraversal() {
        postOrderTraversal(this.root);
    }
    public void midOrderTraversal() {
        midOrderTraversal(this.root);
    }
    public void postOrderTraversal() {
        postOrderTraversal(this.root);
    }
}