深入理解二叉樹（超詳細）

• 2020 年 9 月 18 日
• 筆記
• JAVA, 二叉樹, 數據結構, 數據結構與演算法

二叉樹（Binary Tree）

回顧

在前面的文章 — 二叉樹前奏中，我們對於二叉樹的一些基本概念進行了回顧，同時對比了線性結構與樹形結構，總結了一些常見的二叉樹的性質，像二叉樹，真二叉樹，完全二叉樹，以及滿二叉樹等等，但是，我們僅僅是在概念上對於二叉樹有所了解，並沒有進行編碼工作，今天來完善一下這一步的操作

直接進入二叉樹的設計與編碼，如果你對於二叉樹的概念以及性質不了解的話，可以回去翻翻 二叉樹前奏，熟悉一下，因為編碼實際上就是對於二叉樹性質的一個體現

設計

屬性與節點

首先，我們的二叉樹是用來存放元素的，同時它還需要知道自己的父節點與子節點的關係，那麼，很容易想到的是使用節點類，那麼二叉樹的節點類該如如設計呢，同時我的二叉樹類該有哪些基本元素呢？

首先，我們需要知道二叉樹的節點數量，同時，對於樹而言，要有根，我們需要根節點，那麼可以確定的是有：

//樹節點的數量
protected int size;

//樹的根結點
protected Node<E> root;

這裡我們先不說訪問修飾符為什麼是protected，先來說一說節點類該怎麼設計，我們需要知道一個節點的父節點，以及左右子節點的關係，同時還有節點中存儲的元素element,那麼我們的節點應該是這樣：

/**
 * 自定義節點類，用於維護二叉樹
 * @param <E>
 */
protected static class Node<E>{
    E element;
    Node<E> left;
    Node<E> right;
    Node<E> parent;

    /**
     * 構造函數，添加節點時，要指定元素
     * 父節點的，但不一定有左右子節點
     * @param element
     * @param parent
     */
    public Node(E element,Node<E> parent){
        this.element = element;
        this.parent = parent;
    }

    /**
     * 判斷是否為葉子節點
     * @return
     */
    public boolean isLeaf() {
        return left == null && right == null;
    }

    /**
     * 判斷是否左右子節點都具備
     * @return
     */
    public boolean hasTwoChildren() {
        return left != null && right != null;
    }
}

該節點類，提供了一個構造函數以及兩個特有的方法，對於構造函數而言，初始化的時候，我們需要指定節點存儲的元素以及父節點，為什麼左右子節點不初始化呢，因為你添加一個節點時，是一定要知道其父節點的，但是你並不知道它有沒有子節點。

對於另外兩個方法，我覺的這是節點類所特有的行為，因為節點的概念在二叉樹中是通用的，所以直接封裝在節點類中，而不是在後面，對於每一種獨特的二叉樹，需要用到判斷葉子節點以及度為 2 的節點的時候，再去編寫，那樣就太繁瑣了

針對前面說到的size,root,以及節點類，這些應該是二叉樹的內部邏輯，對外是不公開的，外界不知道節點類的，它只需要指定節點，也就是二叉樹存儲的類型就可以了，但是我們需要對外界開放介面，通過介面來使用二叉樹，也就是說你只要知道怎麼用就好了，不需要知道我是怎麼實現的。

公共介面

對於二叉樹，我們提供給外界的方法應該有以下方法：

public int size() —— 獲取元素節點的數量

public boolean isEmpty() —— 判斷樹是否為空樹

public void clear() —— 清空樹的所有元素

public void preorder() —— 前序遍歷

public void inorder() —— 中序遍歷

public void postorder() —— 後序遍歷

public void levelOrder() —— 層序遍歷

public int height() —— 計算樹的高度

public boolean isComplete() —— 判斷是否為完全二叉樹

public boolean isProper () —— 判斷是否為真二叉樹

public String toString() —— 重新toString方法，樹狀列印二叉樹

我們對外界提供的方法大致就是這些了，那麼問題來了，我們可以有疑惑了，既然二叉樹是用來存放元素的，為什麼沒有add、remove添加以及移除節點的方法的呢，那麼這樣的一棵樹new出來之後就是一棵空樹呀，是不是忘記了？很明確說明，沒有忘了，就是不給提供添加、移除的方法。

我們來思考一下，有下面這麼一段程式碼：

BinaryTree<Integer> bTree = new BinaryTree<>();
bTree.add(9);
bTree.add(5);
bTree.add(8);

可以明確的是第一個添加的元素9就是根節點，那麼問題來了，接下來的 5，是要作為 9 的左子節點還是右子節點，8 應該是 5 的兄弟節點還是左右子節點其中一個，是的，我們並沒有明確二叉樹的添加規則，寫起來是很麻煩也是沒有意義的，當然，我們也可以默認一致往左或者往右添加，但是這樣沒有多大意義，沒有明確的規則，那就是普通的二叉樹，是沒有什麼用處的，規則就是樹的特性，像二叉搜索樹，紅黑樹，AV樹等等，都是有明確的規則的。實際上，我們是在普通的二叉樹加一些自定義的邏輯和規則，所以這裡的二叉樹類BinaryTree實際上應該是基類，而添加以及移除等特有的規則，應該在繼承普通二叉樹的基礎上編寫的，而二叉樹提供的就是一些通用的方法。這也是前面將BinaryTree的類的屬性的訪問修飾符設計為protected的原因

簡單方法

public int size() —— 獲取元素節點的數量

/**
 * 獲取元素節點的數量
 * @return
 */
public int size() {
    return size;
}

public boolean isEmpty() —— 判斷樹是否為空樹

/**
 * 判斷樹是否為空樹
 * @return
 */
public boolean isEmpty() {
    return size == 0;
}

public void clear() —— 清空樹的所有元素

/**
 * 清空樹的所有元素
 */
public void clear() {
    root = null;
    size = 0;
}

簡單的方法直接放出來，直接瞄一眼即可

有趣的遍歷

對於數組，鏈表等數據結構，我們都能遍歷，獲取到所有元素，線性數據結構的遍歷比較簡單 — 正序遍歷與逆序遍歷，對於我們的二叉樹，同樣也應該提供遍歷的方法

根據節點訪問順序的不同，二叉樹的常見遍歷方式有4種常見的遍歷方式（Preorder Traversal）：

• 前序遍歷（Preorder Traversal）
• 中序遍歷（Inorder Traversal）
• 後序遍歷（Postorder Traversal）
• 層序遍歷（Level Order Traversal）

我們以二叉搜索樹 —— {7,4,9,2,5,8,11,3,12,1}為例，分別分析這四種遍歷方式

前序遍歷

訪問順序：根節點、前序遍歷左子樹、前序遍歷右子樹 — （根節點訪問在前）

遍歷結果是：7、4、2、1、3、5、9、8、11、10、12

前序遍歷、中序遍歷、後序遍歷用遞歸遍歷的方式實現都很簡單，這裡就不放出來占篇幅了，但是有提供，如果想看的話，後面會將完整程式碼上傳Github,需要再去下載下來即可，下載的時候，注意選擇dev分支，那邊才是最新的程式碼

實現步驟：

• 利用棧先進後出的特性：
• 設置node = root，將root入棧，循環執行以下操作，直到棧為空
• 彈出棧頂節點top，進行訪問
• 將top.right入棧將top.left入棧

/**
 * 迭代法實現 —— 前序遍歷
 */
private void preorderByIteration(){
    if (root == null) return;

    Stack<Node<E>> stack = new Stack<>();
    stack.push(root);

    while (!stack.isEmpty()) {
        Node<E> node = stack.pop();
        
		System.out.print(node.element + "  ");
        if (node.right != null){
            stack.push(node.right);
        }

        if (node.left != null){
            stack.push(node.left);
        }
    }
}

中序遍歷

訪問順序： — （根節點訪問在中）

1、中序遍歷左子樹、根節點、中序遍歷右子樹 （如果是二叉搜索樹，結果升序）

2、中序遍歷右子樹、根節點、中序遍歷左子樹 （如果是二叉搜索樹，結果降序）

遍歷結果是：1、2、3、4、5、7、8、9、10、11、12 （升序）

實現步驟：

• 利用棧先進後出的特性：
• 設置node = root，將root入棧，循環執行以下操作，直到棧為空
• 如果node！= null將node入棧，設置node = node.left
• 如果node == null如果棧為空，結束遍歷，如果棧不為空，彈出棧頂元素並賦值給node，對node進行訪問
• 設置node = node.right

/**
 * 迭代法實現 —— 中序遍歷
 */
private void inorderByIteration(){
    if (root == null) return;
    Stack<Node<E>> stack = new Stack<>();
    Node<E> node = root;
    
    while (node != null || !stack.isEmpty()) {

        while (node != null){
            stack.push(node);
            node = node.left;
        }
        node = stack.pop();
        System.out.print(node.element + "  ");
        node = node.right;
    }
}

後序遍歷

訪問順序：後序遍歷左子樹、後序遍歷右子樹、根節點 — （根節點訪問在後）

遍歷結果是：1、3、2、5、4、8、10、12、11、9、7

實現步驟：

• 利用棧先進後出的特性：
• 設置node = root，將root入棧，循環執行以下操作，直到棧為空
• 如果棧頂節點是葉子節點或者上一次訪問的節點是棧頂節點的子節點，彈出棧頂節點，進行訪問
• 否則，將棧頂節點的right、left按順序入棧

/**
 * 迭代法實現 —— 後序遍歷
 */
private void postorderByIteration(){
    if (root == null) return;

    Node<E> node = root;
    //記錄上一次訪問的節點
    Node<E> lastVisited = null;
    Stack<Node<E>> stack = new Stack<>();
    while (node != null || !stack.isEmpty()) {

        while (node != null){
            stack.push(node);
            node = node.left;
        }

        node = stack.pop();
        //棧頂節點是葉子節點或者上一次訪問的節點是棧頂節點的子節點
        if (node.right == null || node.right == lastVisited){
            System.out.print(node.element + "  ");
            lastVisited = node;
            //這裡node沒有改變指向，所以需要指向null，否則會死循環
            node = null;
        }else {
            //既不是子節點且上一次訪問的節點又不是棧頂節點的子節點話，代表是符節點，重新進棧
            stack.push(node);
            node = node.right;
        }
    }
}

層序遍歷

訪問順序：從上到下、從左到右依次訪問每一個節點

遍歷結果是：7、4、9、2、5、8、11、1、3、10、12

層序遍歷採用迭代的方式實現，利用隊列的先進先出性質，能很好的做到層序遍歷

實現步驟：

• 利用隊列先進先出的特性：
• 將根節點root入隊，循環執行以下操作，直到隊列為空
• 將隊頭節點node出隊，進行訪問，將node的左子節點入隊，將node的右子節點入隊

畫一波圖解：

結合圖解，看程式碼，很清晰

/**
 * 層序遍歷，迭代方式
 */
public void levelOrderTraversal(){
    if (root == null) return;

    Queue<Node<E>> queue = new LinkedList<>();
    //入隊
    queue.offer(root);

    while (!queue.isEmpty()){
        Node<E> node = queue.poll();
        System.out.print(node.element + "  ");

        //如果有左子節點，入隊
        if (node.left != null){
            queue.offer(node.left);
        }
        //如果有右子節點，入隊
        if (node.right != null){
            queue.offer(node.right);
        }
    }
}

補充

如果對於二叉樹的四種遍歷方式還是比較迷惑的話，我只是畫了靜態圖的順序，可能閱讀起來理解不夠到位，但是有時候畫圖解的時間很長，所以如果看不太明白的話，可以先看看別人的文章，圖解二叉樹的遍歷，看一下圖解，再回來閱讀，相信會好一些

增強遍歷介面

對比： 上面四種遍歷的方法都編寫出來了，但是你覺得這樣的遍歷，功能夠嗎？ 或者說，你覺得這個對比我們前面在動態數組，鏈表、棧和隊列中的遍歷有什麼區別？沒有閱讀過動手編寫 —— 動態數組，鏈表，棧和隊列的同學，有興趣的可以點擊關鍵詞看看

我們簡單寫一下JDK數組或者動態鏈表遍歷的程式碼:

//遍曆數組
int[] arr = {1,2,3,4,5,6,7,8,9};
for (int value:arr) {
    System.out.println(value);
}

//遍歷鏈表
List<Integer> list = new LinkedList<>(){{
    add(1);add(2);add(3);add(4);add(5);
}};
for (int value:list) {
    System.out.println(value);
}

這樣看起來好像沒有什麼問題，二叉樹遍歷是System.out.print(node.element);

而數組和鏈表是System.out.println(value); 都是列印呀，能有什麼區別呀。可能上面的程式碼具備迷惑性，我們再來看看另一個程式碼：

int[] arr = {1,2,3,4,5,6,7,8,9};
for (int value:arr) {
    System.out.println(value + "-->" + "Kalton是帥哥");
}

嗨，這樣就醒目點了，數組可以列印出節點存儲的元素的同時，補上一句Kalton是帥哥，而上面二叉樹的遍歷卻是做不到的，因為一個是寫死在類裡面的，一個是在類外部編寫的。

這樣的區別就是，二叉樹的遍歷只是列印一遍元素，並沒有真正獲取到存在在二叉樹的元素，而數組、鏈表的遍歷是獲取到每一個元素，至於做什麼，列印還是增加，還是說Kalton是帥哥，這些遍歷規則都是由調用者自定義的，而不是寫死了，所以我們的二叉樹內部應該做到能夠遍歷的同時將節點元素傳給調用者，由用戶自定義遍歷規則，我們的做法時，在二叉樹編寫一個抽象內部類Visitor：

/**
 * 提供外部使用的遍歷器介面
 * @param <E>
 */
public abstract static class Visitor<E>{

    //遍歷停止遍歷的標記
    boolean stop;

    /**
     * visit方法將節點元素傳給調用者
     * @param element
     * @return 如果返回true，結束遍歷
     */
    abstract boolean visit(E element);
}

visit方法方法參數為E element,在遍歷的時候接收節點元素，傳給外部調用者，返回值如果是true，表示用戶希望結束遍歷，我們以前序遍歷為例，實現我們的邏輯：

/**
 * 迭代法實現 —— 前序遍歷
 * @param visitor
 */
public void preorderByIteration(Visitor<E> visitor){
    if (root == null || visitor == null) return;

    Stack<Node<E>> stack = new Stack<>();
    stack.push(root);

    while (!stack.isEmpty()) {
        Node<E> node = stack.pop();

        //傳給外部調用者,如果條件成立，停止遍歷
        if (visitor.visit(node.element)) return;

        if (node.right != null){
            stack.push(node.right);
        }

        if (node.left != null){
            stack.push(node.left);
        }
    }
}

實際上，就是用戶在調用前序遍歷preorderByIteration，需要傳入自定義的遍歷規則類Visitor,然後在我們原來的方法列印元素的地方改為if (visitor.visit(node.element)) return;，即將節點元素返回給方法調用者，使用調用的遍歷規則，同時返回給二叉樹類一個boolean變數值，用stop接收，告知是否結束遍歷，所以什麼時候結束遍歷也是有用戶自定義規則的

但是有一點不好的是，這樣我們調用二叉樹的遍歷方法時，需要強制傳入一個遍歷規則類，同時我們遍歷的方法是遞歸還是迭代都對調用者暴露了，所以我做了一下小小的封裝：

/**
 * 前序遍歷 —— 如果用戶沒有傳遍歷規則，默認列印元素
 */
public void preorder(){
    preorder(new Visitor<>() {
        @Override
        boolean visit(E element) {
            System.out.print(element + " ");
            return false;
        }
    });
}

/**
 * 增強前序遍歷，提供調用者編寫自己的遍歷規則
 * @param visitor
 */
public void preorder(Visitor<E> visitor) {
    if (visitor == null) return;

    /**
     * 底層使用遞歸法
     */
    //preorderByRecursive(root, visitor);

    /**
     * 底層使用迭代法
     */
    preorderByIteration(visitor);
    System.out.println();
}

public void preorder()方法不需要傳參，默認遍歷規則是列印節點元素，而用戶需要自定義比較規則則調用public void preorder(Visitor<E> visitor)，傳入比較器，至於是使用preorderByRecursive遞歸還是preorderByIteration，用戶並不知道，由我們在設計時決定，其他 3 種遍歷也是一樣的邏輯，程式碼比較長，不必要的展示，我就沒有貼出來，會在後面給出GitHub地址，需要的話，大家自行下載閱讀

樹的判定

在二叉樹前奏中，我們已經講了完全二叉樹，真二叉樹的特點以及性質，這裡就不再複述了，實際上，對於他們的判定以及計算樹的高度，都是以層序遍歷方法為基礎，所完成的，所以層序遍歷是很重要的，最好是給我收手寫出來

完全二叉樹的判定

實現步驟：

/**
 * 判斷是否為完全二叉樹 —— (層序遍歷)
 * @return
 */
public boolean isComplete() {
    if (root == null) return false;
    Queue<Node<E>> queue = new LinkedList<>();
    queue.offer(root);

    boolean leaf = false;
    while (!queue.isEmpty()) {
        Node<E> node = queue.poll();
        if (leaf && !node.isLeaf()) return false;

        if (node.left != null) {
            queue.offer(node.left);
        } else if (node.right != null) {
            //相當於node.left == null && node.right != null
            return false;
        }

        if (node.right != null) {
            queue.offer(node.right);
        } else {
            //node.left == null && node.right == null
            //node.left ！= null && node.right == null
            // 後面遍歷的節點都必須是葉子節點
            leaf = true;
        }
    }
    return true;
}

真二叉樹的判定

實現步驟：

1、利用隊列先進先出的特性

2、利用真二叉樹的節點，要麼度為0，要麼度為2的特點

3、在層序遍歷的時候，判斷每層的節點數量，如果levelSize % 2 != 0，返回flase

4、結合上面層序遍歷的圖解，就會發現，每一層的節點遍歷完後，隊列中的節點數量size等於下一層的節點數量，而第一層只有根節點

/**
 * 判斷是否為真二叉樹 —— (層序遍歷)
 * @return
 */
public boolean isProper (){
    if (root == null) return false;

    // 存儲著每一層的元素數量
    int levelSize = 1;
    Queue<Node<E>> queue = new LinkedList<>();
    queue.offer(root);

    while (!queue.isEmpty()) {
        Node<E> node = queue.poll();
        levelSize--;

        if (node.left != null) {
            queue.offer(node.left);
        }

        if (node.right != null) {
            queue.offer(node.right);
        }

        // 意味著即將要訪問下一層
        if (levelSize == 0) {
            //每一層訪問完後，下一層的節點個數是隊列的size
            levelSize = queue.size();
            if (levelSize % 2 != 0) return false;
        }
    }
    return true;
}

樹的高度

樹的高度實際上就是樹的層數，與上面的判定真二叉樹很接近，只需要在設置一個height，在遍歷完每一層的時候，height++,結束遍歷後，返回的就是樹的高度

樹的高度實際上所有子節點的高度中最大的一個，然後再 + 1，這樣的思路，很容易以遞歸的方式實現，所以計算樹的高度，有遞歸和迭代兩種方法，這裡貼出遞歸的方法，因為迭代的方法就是上面判定二叉樹的方法做點小改動，就不貼出來了，需要的話，自行下載源碼。

/**
 * 計算樹的高度
 * @return
 */
public int height(){
    //遞歸法
    return heightByRecursive(root);

    //迭代法
    //return heightByIteration();
}

/**
 * (遞歸法)獲取傳入節點的高度
 * @param node
 * @return
 */
private int heightByRecursive(Node<E> node){
    if (node == null) return 0;
    return 1 + Math.max(heightByRecursive(node.left),heightByRecursive(node.right));
}

前驅與後繼

尋找前驅節點

根據上面的判定條件給出實現程式碼：

/**
 * 獲取傳入節點的前驅節點
 * @param node
 * @return
 */
protected Node<E> predecessor(Node<E> node) {
    if (node == null) return null;

    // 前驅節點在左子樹當中（left.right.right.right....）
    Node<E> p = node.left;
    if (p != null) {
        while (p.right != null) {
            p = p.right;
        }
        return p;
    }

    // 從父節點、祖父節點中尋找前驅節點
    while (node.parent != null && node == node.parent.left) {
        node = node.parent;
    }

    // node.parent == null
    // node == node.parent.right
    return node.parent;
}

尋找後繼節點

根據上面的判定條件給出實現程式碼：

/**
 * 獲取傳入節點的後繼節點
 * @param node
 * @return
 */
protected Node<E> successor(Node<E> node) {
    if (node == null) return null;

    // 前驅節點在左子樹當中（right.left.left.left....）
    Node<E> p = node.right;
    if (p != null) {
        while (p.left != null) {
            p = p.left;
        }
        return p;
    }

    // 從父節點、祖父節點中尋找前驅節點
    while (node.parent != null && node == node.parent.right) {
        node = node.parent;
    }

    return node.parent;
}

現在我們可能會比較疑惑，這兩個方法，找出前驅或者後繼節點有什麼用，不知道你有沒有看到方法的訪問修飾符：protected，實際上著兩個方法都不是給用戶調用的，正如我們的疑惑一樣，用戶不知道怎麼用，用來幹嘛，實際上這是為繼承二叉樹BinaryTree類的子類所使用的，其作用是在刪除度為 2 的時，將找到的前驅或者後繼節點用來替代的，這在下一篇，二叉搜索樹的時候回說到。

小結

​ 到這裡為止，已經將二叉樹的基本概念複習以及通用方法的設計編寫，對於二叉樹的結構有了一定的認識，但知識有時候總是在你覺得記住的時候偷偷溜走，因此，將所學的知識總結成筆記，以便後來翻閱，加深印象

聲明

文章為原創，歡迎轉載，註明出處即可

個人能力有限，有不正確的地方，還請指正

本文的程式碼已上傳github,歡迎star —— GitHub地址