• 樹形結(jié)構(gòu)

在前面章節(jié)中介紹到的數(shù)據(jù)結(jié)構(gòu)冤议，都為線性結(jié)構(gòu)斟薇，比如鏈表，數(shù)組恕酸，隊列等堪滨，都屬于線性結(jié)構(gòu)，類似于通過一根線串在一起

1569326231986.png

樹形結(jié)構(gòu)示意圖

二叉樹

多叉樹

現(xiàn)實生活中的樹蕊温，如果將現(xiàn)實生活中的樹倒過來袱箱，就類似于樹形結(jié)構(gòu)

• 生活中經(jīng)常用到的樹形結(jié)構(gòu)

1.公司的組織架構(gòu)

2.平時的文件夾組織

總結(jié)：1.使用樹形結(jié)構(gòu)可以大大提高效率

? 2.樹形結(jié)構(gòu)是算法面試的重點

• 樹(Tree)的基本概念

• 節(jié)點，根節(jié)點义矛，父節(jié)點发笔，子節(jié)點，兄弟節(jié)點
• 一棵樹可以沒有任何節(jié)點凉翻，稱為空樹
• 一棵樹可以只有一個節(jié)點筐咧，也就是只有根節(jié)點
• 子樹，左子樹噪矛，右子樹
• 節(jié)點的度(degree):子樹的個數(shù)
• 樹的度：所有節(jié)點度中的最大值
• 葉子節(jié)點(leaf):度為0的節(jié)點
• 非葉子節(jié)點：度不為0的節(jié)點
• 層數(shù)(level):根節(jié)點在第一層，根節(jié)點的子節(jié)點在第二層铺罢，以此類推(有些書籍也從第0層開始計算)
• 節(jié)點的深度(depth):從根節(jié)點到當前節(jié)點的唯一路徑上的節(jié)點總數(shù)
• 節(jié)點的高度(height):當從前節(jié)點到最遠葉子節(jié)點的路徑上的節(jié)點總數(shù)
• 樹的深度:所有節(jié)點深度中的最大值
• 樹的高度:所有節(jié)點高度中的最大值(一般來講艇挨，樹的深度與樹的高度相等)

多叉樹

• 有序樹

• 樹中任意節(jié)點的子節(jié)點之間有順序關(guān)系(如上面樹中，節(jié)點2,3,4,5,6是完全按照順序排列的韭赘，如果調(diào)換位置缩滨，就變成了另外一棵樹)

• 無序樹

• 樹種的任意節(jié)點的子節(jié)點之間沒有順序關(guān)系，也稱為自由樹

• 森林

• 由m(m ≥ 0)棵互不相交的樹組成的集合

• 二叉樹(Binary Tree)

二叉樹的特點

• 每個節(jié)點的度最大為2(最多擁有2棵子樹)
• 左子樹和右子樹是有順序的
• 即使某個節(jié)點只有一顆子樹，也要區(qū)分左右子樹

二叉樹有以下幾種形態(tài)

1.空樹

2.只有一個節(jié)點

3.只有左子樹

4.只有右子樹

5.右左右子樹

??二叉樹是有序樹還是無序樹脉漏？

• 二叉樹的性質(zhì)

• 非空二叉樹的第i層苞冯，最多有2^(i - 1)個字節(jié)點(i ≥ 1)
• 在高度為h的二叉樹上，最多有2^h - 1個節(jié)點(h ≥ 1)
• 對于任何一顆非空的二叉樹侧巨，如果葉子節(jié)點個數(shù)為n0舅锄，度為2的節(jié)點個數(shù)為n2,則有：n0 = n2 +1
• • 假設(shè)度為1的節(jié)點個數(shù)為n1，那么二叉樹的節(jié)點總數(shù)為 n = n0 + n1 +n2
  • 二叉樹的邊數(shù)T= n1 + 2 * n2 = n - 1 = n0 + n1 + n2 - 1

• 真二叉樹(Proper Binary Tree)

真二叉樹：所有節(jié)點的度司忱，要么為0皇忿，要么為2

下圖不是真二叉樹

• 滿二叉樹(Full Binary Tree)

滿二叉樹：所有節(jié)點的度都要么為0，要么為2坦仍，并且所有的葉子節(jié)點都在最后一層

在同樣高度的二叉樹中鳍烁，滿二叉樹的葉子節(jié)點數(shù)量最多，總節(jié)點數(shù)量最多

滿二叉樹一定是真二叉樹繁扎，真二叉樹不一定是滿二叉樹

假設(shè)滿二叉樹的高度為h(h ≥ 1)幔荒，那么

第i層的節(jié)點數(shù)量：2^(i - 1)

葉子節(jié)點的數(shù)量:2(h - 1)

總節(jié)點數(shù)量n: n = 2^h - 1 = 2^0 + 2^1 +2^2 + …… + 2^(h - 1)

• 完全二叉樹(Complete Binary Tree)

完全二叉樹:葉子節(jié)點只會出現(xiàn)在最后2層，并且最后1層的葉子節(jié)點都靠左對齊

完全二叉樹的記憶方法：所有節(jié)點從上往下梳玫，從左往右一次排布爹梁，就位完全二叉樹，如下圖

如果所有節(jié)點都排滿了汽纠，就叫做滿二叉樹

完全二叉樹從根節(jié)點至倒數(shù)第二層是一個滿二叉樹

滿二叉樹一定是一棵完全二叉樹卫键，完全二叉樹不一定是滿二叉樹

• 完全二叉樹的性質(zhì)

度為1的節(jié)點只有左子樹

度為1的節(jié)點，要么是1個虱朵，要么是0個

同樣節(jié)點數(shù)量的二叉樹莉炉，完全二叉樹的高度最小

假設(shè)完全二叉樹的高度為h(h ≥ 1)，那么

至少有2^(h - 1)個節(jié)點(2^0 + 2^1 + …… + 2^(h - 2) +1)

最多有2^ - 1個節(jié)點(滿二叉樹)

如果此時碴犬，總節(jié)點數(shù)量為n絮宁，那么有結(jié)論 2^(h -1) ≤ n ＜ 2^h

對 2^(h -1) ≤ n ＜ 2^h取對數(shù)，則有h - 1 ≤ log2n ＜ h,可以得出服协，h與n之間的關(guān)系為 h = log2n (向下取整) +1绍昂，即 h = floor(log2n) +1

一棵有n個節(jié)點的完全二叉樹(n＞0)[下圖],從上到下，從左到右對節(jié)點從1開始進行編號偿荷，對任意第i個節(jié)點

• 如果i = 1窘游，它是根節(jié)點
• 如果i > 1 ,它的父節(jié)點編號為floor(i / 2)
• 如果2i ≤ n ,它的左子節(jié)點編號為2i
• 如果2i ＞ n ,它沒有左子節(jié)點
• 如果2i + 1 ≤ n ,它的右子節(jié)點編號為2i + 1
• 如果2i + 1＞ n，它沒有右子節(jié)點

一棵有n個節(jié)點的完全二叉樹(n＞0)[下圖],從上到下跳纳，從左到右對節(jié)點從0開始進行編號忍饰，對任意第i個節(jié)點

• 如果i = 0，它是根節(jié)點
• 如果i > 0 ,它的父節(jié)點編號為floor((i - 1) / 2)
• 如果2i + 1 ≤ n - 1 ,它的左子節(jié)點編號為2i + 1
• 如果2i + 1＞ n - 1 ,它沒有左子節(jié)點
• 如果2i + 2 ≤ n - 1,它的右子節(jié)點編號為2i + 2
• 如果2i + 1＞ n寺庄，它沒有右子節(jié)點

• 下面的二叉樹不是完全二叉樹

• 面試題

如果一棵完全二叉樹有768個節(jié)點井联，求葉子節(jié)點的個數(shù)

解題思路：

1. 假設(shè)葉子節(jié)點個數(shù)為n0，度為1的節(jié)點個數(shù)為n1爸黄，度為2的節(jié)點個數(shù)為n2
2. 總結(jié)點個數(shù) n = n0 +n1 + n2 ,而且由前面的公式知道，n0 = n2 + 1

因此有 n = 2n0 + n1 - 1

由于題目告知二叉樹為完全二叉樹亮靴，那么我們知道度為1的節(jié)點數(shù)量，為1或者為0于置，所以

• 當n1為1時茧吊，n = 2n0，n必然是偶數(shù)俱两，所以葉子節(jié)點是數(shù)量n0 = n / 2,非葉子節(jié)點個數(shù) n1 +n2 = n / 2
• 當n1位0時饱狂，n = 2n0 - 1，n必然位奇數(shù)宪彩，所以葉子節(jié)點的數(shù)量n0 = (n +1) / 2休讳，非葉子節(jié)點的數(shù)量 n1 + n2 = (n - 1) / 2

所以最終，葉子節(jié)點的數(shù)量n0 = floor((n +1) / 2) = ceilling(n / 2)

非葉子節(jié)點的數(shù)量n1 + n2 = floor(n / 2) = ceilling((n - 1) / 2)

因此最終結(jié)果為384

• 國外資料的說法

Full Binary Tree: 完滿二叉樹

• 所有非葉子節(jié)點的度都為2
• 也就是我們所說的"真二叉樹“

Perfect Binary Tree:完美二叉樹

• 所有非葉子節(jié)點的度都為2尿孔，且所有的葉子節(jié)點都在最后一層
• 也就是我們所說的"滿二叉樹“

Complete Binary Tree:完全二叉樹

• 和我們說的一樣

以下內(nèi)容俊柔，建議閱讀二叉搜索樹部分后再來繼續(xù)閱讀

• 二叉樹的遍歷

遍歷是數(shù)據(jù)結(jié)構(gòu)中的常見操作

• 把所有元素都遍歷一遍

在前面我們介紹的線性數(shù)據(jù)結(jié)構(gòu)，它的遍歷方法比較簡單活合，一般是

• 正序遍歷
• 逆序遍歷

在二叉樹遍歷中雏婶，根據(jù)節(jié)點訪問的順序不同，常見的遍歷方式有4種白指，分別為

• 前序遍歷(Preorder Traversal)
• 中序遍歷(Inorder Traversal)
• 后序遍歷(Postorder Traversal)
• 層序遍歷(Level Order Traversal)

• 前序遍歷(Preorder Traversal)

例如現(xiàn)有如下的二叉樹

訪問順序

1. 優(yōu)先訪問根節(jié)點留晚，然后再前序遍歷左子樹，前序遍歷右子樹[訪問順序:下圖]

• 前序遍歷的代碼實現(xiàn)

結(jié)合前面二叉搜索樹的代碼告嘲，我們可以在里面新增一個preorderTraversal(Node<E> node)的方法

通過遞歸的方式實現(xiàn)代碼

public void  preorderTraversal(Node<E> node) {
    if (node == null) {
        return;
    }
    System.out.println(node.element);
    preorderTraversal(node.left);
    preorderTraversal(node.right);
}

另外错维，讀者可以嘗試使用其他的方式進行實現(xiàn)。如迭代

• 中序遍歷(Inorder Traversal)

訪問順序

1. 先中序遍歷左子樹橄唬，然后訪問根節(jié)點赋焕，最后中序遍歷右子樹

最終的訪問邏輯

由于我們當前的二叉樹是一棵二叉搜索樹，因此我們可以看到仰楚，如果我們使用中序遍歷的方法進行遍歷的話隆判，最紅遍歷的結(jié)果為1,2,3,4,5,6,7,8,9,10,11,12。它們的順序是從小到大的順序進行遍歷的

如果我們的訪問順序是：

先中序遍歷右子樹僧界，然后訪問根節(jié)點侨嘀，最后中序遍歷左子樹

我們不難發(fā)現(xiàn)，最終的訪問結(jié)果為12,11,10,9,8,7,6,5,4,3,2,1捂襟。它們的順序是中大到小的順序進行遍歷的

因此:二叉搜索樹的中序遍歷結(jié)果是升序或者降序的

• 中序遍歷的代碼實現(xiàn)

我們新增一個inorderTraversal(Node<E> node)的方法

通過遞歸實現(xiàn)中序遍歷的代碼

public void inorderTraversal(Node<E> node) {
    if (node == null) return;
    inorderTraversal(node.left);
    System.out.println(node.element);
    inorderTraversal(node.right);
}

同樣的飒炎，讀者可以使用其他方式來實現(xiàn)

• 后序遍歷(Postorder Traversal)

訪問順序

1. 先后續(xù)遍歷左子樹，然后后續(xù)遍歷右子樹笆豁，最后訪問根節(jié)點

最終的訪問邏輯

• 后續(xù)遍歷的代碼實現(xiàn)

我們新增一個postorderTraversal(Node<E> node)的方法

public void postorderTraversal(Node<E> node) {
    if (node == null) return;
    inorderTraversal(node.left);
    inorderTraversal(node.right);
    System.out.println(node.element);
}

• 層序遍歷(Level Order Traversal)

一層一層的往下進行訪問

訪問順序

1. 從上到下郎汪，從左到右依次訪問每個節(jié)點

也就意味著，我們最終的訪問順序為

實現(xiàn)思路：使用隊列

1. 將根節(jié)點入隊
2. 循環(huán)執(zhí)行下面的操作闯狱，直到隊列為空

• 將隊列頭節(jié)點A出隊煞赢，進行訪問
• 將A的左子節(jié)點入隊
• 將A的右子節(jié)點入隊

• 后續(xù)遍歷的代碼實現(xiàn)

我們新增一個levelorderTraversal(Node<E> node)的方法

層序遍歷的實現(xiàn)代碼

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.println(node.element);
        if (node.left != null) {
            queue.offer(node.left);
        }
        if (node.right != null) {
            queue.offer(node.right);
        }
    }
}

??如果允許外界遍歷二叉樹的元素，你會如何設(shè)計接口哄孤？

因此我們可以設(shè)計一個Visitor接口照筑，定義一個方法，讓調(diào)用者自己定義元素被訪問后瘦陈，需要做的操作

因此4中遍歷方法凝危，改造完成后的代碼是這樣的

public void preOrder(Visitor<E> visitor) {}
private void preOrder(Node<E> node , Visitor<E> visitor) {
    if (node == null || visitor == null) return;
    visitor.visit(node.element);
    preOrder(node.left,visitor);
    preOrder(node.right,visitor);
}

public void inOrder(Visitor<E> visitor) {}
private void inOrder(Node<E> node , Visitor<E> visitor) {
    if (node == null || visitor == null) return;
    preOrder(node.left,visitor);
    visitor.visit(node.element);
    preOrder(node.right,visitor);
}

public void postOrder(Visitor<E> visitor) {}
private void postOrder(Node<E> node ,Visitor<E> visitor) {
    if (node == null || visitor == null) return;
    preOrder(node.left,visitor);
    visitor.visit(node.element);
    preOrder(node.right,visitor);
}

public void levelOrder(Visitor<E> visitor) {
    if (root == null || visitor == null) return;
    Queue<Node<E>> queue = new LinkedList<>();
    queue.offer(root);
    while (!queue.isEmpty()) {
        Node<E> node = queue.poll();
        visitor.visit(node.element);
        if (node.left != null) {
            queue.offer(node.left);
        }
        if (node.right != null) {
            queue.offer(node.right);
        }
    }
}

• 遍歷的應(yīng)用

前序遍歷

樹狀結(jié)構(gòu)展示(注意左右子樹的順序)

練習-利用前序遍歷樹狀打印二叉樹

中序遍歷

二叉搜索樹的中序遍歷按照升序或者降序處理節(jié)點

后序遍歷

適用于一些先子后父的操作

層序遍歷

計算二叉樹的高度

判斷一棵樹是否為完全二叉樹

練習1:計算二叉樹的高度

建議使用遞歸和迭代的方式實現(xiàn)。

遞歸實現(xiàn)方式

public int height(Node<E> node) {
    if (node == null) return 0;
    return 1 + Math.max(height(node.left),height(node.right));
}

使用迭代的方式實現(xiàn)

public int height() {
        if (root == null) return 0;
        int height = 0;//樹的高度
        int levelSize = 1;//存儲著每一層元素的數(shù)量
        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) { //即將訪問下一層
                levelSize = queue.size();
                height++;
            }
        }
        return height(root);
    }

練習2:判斷一棵樹是否為完全二叉樹

解題思路

1. 如果樹為空晨逝，返回false
2. 如果樹不為空蛾默，開始層序遍歷二叉樹(使用隊列)
   • 如果node.left != null && node.right != null ，將node.left, node.right按順序入隊
   • 如果node.left == null && node.right != null捉貌，返回false
   • 如果node.left != null && node.right == null 或者node.left == null && node.right == null
     • 那么后序遍歷的節(jié)點應(yīng)該都為葉子節(jié)點支鸡，才是完全二叉樹
     • 否則返回false

解題源碼

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.hasTwoChildren()) {
            queue.offer(node.left);
            queue.offer(node.right);
        } else if (node.left == null && node.right != null) {
            return false;
        } else {
            //意味著后遍歷的節(jié)點，都必須是葉子節(jié)點
            leaf = true;
        }
    }
    return true;
}

練習3:翻轉(zhuǎn)二叉樹 題目來自[Leetcode]

將所有節(jié)點的左右子樹都交換

由于使用了多種解題方法趁窃，因此解題源碼在這里

• 根據(jù)遍歷結(jié)果重構(gòu)二叉樹

即：根據(jù)遍歷的結(jié)果牧挣，推導出該結(jié)果是哪種二叉樹

通過以下結(jié)果可以保證重構(gòu)出唯一的一棵二叉樹

• 前序遍歷結(jié)果 + 中序遍歷結(jié)果
• 后序遍歷結(jié)果 + 中序遍歷結(jié)果

為什么根據(jù)前序遍歷和中序遍歷的結(jié)果，就能推導出一棵二叉樹的結(jié)果

假設(shè)下圖為前序遍歷的結(jié)果示意圖醒陆，其中紅色為根節(jié)點

其中l(wèi)eft(左子樹)和right(右子樹)結(jié)果瀑构，同樣也是采用前序遍歷

下圖為中序遍歷的結(jié)果示意圖，其中紅色為根節(jié)點

其中l(wèi)eft(左子樹)和right(右子樹)結(jié)果刨摩，同樣也是采用中序遍歷

通過以上兩個結(jié)果寺晌，我們可以知道

1. 根據(jù)前序遍歷的結(jié)果，我們可以知道結(jié)果中的第一個節(jié)點為根節(jié)點
2. 找到根節(jié)點后码邻，根據(jù)中序遍歷的結(jié)果折剃，可以找到左子樹和右子樹的邊界，根節(jié)點左邊的為左子樹像屋，根節(jié)點右邊的為右子樹怕犁，也就知道了哪些元素屬于左子樹，哪些元素屬于右子樹
3. 通過中序遍歷的結(jié)果己莺，已經(jīng)知道了哪些元素屬于左子樹奏甫，哪些元素屬于右子樹，因此凌受，我們在前序遍歷中阵子，就知道了哪些元素為左子樹，哪些元素屬于右子樹
4. 已經(jīng)知道了哪些節(jié)點屬于哪個子樹胜蛉，因此前序遍歷的左子樹中的第一個元素挠进，為左子樹的根節(jié)點
5. 通過前序遍歷中找到的左子樹根節(jié)點色乾，可以在中序遍歷的左子樹中，找到左子樹的左子樹和右子樹领突，因為中序遍歷的特點是通過根節(jié)點暖璧，將左右區(qū)分開來
6. 通過這種拆分，又可以拆分為一個規(guī)模更小的遍歷結(jié)果君旦，以此類推澎办，誰是誰的左節(jié)點，誰是誰的右節(jié)點金砍，誰是誰的父節(jié)點局蚀，都能拆分出來

因此通過后序遍歷的結(jié)果 + 中序遍歷的結(jié)果，也是同理

通過這個結(jié)論恕稠，可以嘗試以下練習

通過前序遍歷結(jié)果 + 中序遍歷結(jié)果重構(gòu)二叉樹

• 前序遍歷結(jié)果：4 2 1 3 6 5
• 中序遍歷結(jié)果：1 2 3 4 5 6

利用前面的結(jié)論琅绅，我們知道

1. 當前二叉樹的根節(jié)點為 4

   
   

2. 通過中序遍歷的結(jié)果知道，該二叉樹的左子樹為 1 2 3 谱俭，右子樹為 5 6

3. 在通過前序遍歷奉件，就可以知道，左子樹的根節(jié)點為 2昆著，右子樹的根節(jié)點為 6

4. 由于已經(jīng)知道了2為左子樹的根節(jié)點,那么通過中序遍歷的結(jié)果,2位1 3 的父節(jié)點,1為2的左子樹,3為2的右子樹

5. 前面知道6位右子樹的根節(jié)點,那么通過中序遍歷的結(jié)果,6為 5的父節(jié)點,5在6的左邊,因此5為6的左子樹

??根據(jù)前序遍歷的結(jié)果 + 后序遍歷的結(jié)果,能重構(gòu)出唯一的一棵二叉樹嗎?

• 如果是一個真二叉樹,它的結(jié)果是唯一的
• 否則結(jié)果不唯一

因為有以下的情況

如果兩個的遍歷結(jié)果如上圖所示,并且其中一個子樹為空的話,就沒法知道該結(jié)果為左子樹的結(jié)果還是右子樹的結(jié)果

如果二叉樹的左右節(jié)點都不為空,遍歷結(jié)果如下圖

我們可以通過該結(jié)果得到以下信息

1. 首先我們可以馬上確認根節(jié)點,前序遍歷的結(jié)果,最前面的節(jié)點為根節(jié)點县貌，根節(jié)點的下一個節(jié)點為左子樹的根節(jié)點
2. 通過前序遍歷中找到的左子樹根節(jié)點，可以在后序遍歷的左子樹結(jié)果中找到凑懂，并且在后序遍歷結(jié)果中煤痕，左子樹根節(jié)點在左子樹結(jié)果中的最后一位
3. 在后序遍歷中，通過左子樹根節(jié)點的位置接谨，就可以知道左子樹和右子樹的范圍摆碉，然后再通過上面的結(jié)論，就可以重構(gòu)出二叉樹

• 前驅(qū)節(jié)點(predecessor)

前驅(qū)節(jié)點：中序遍歷時的前一個節(jié)點

• 如果是二叉搜索樹脓豪，前驅(qū)節(jié)點就是前一個比它小的節(jié)點

例如有下列的二叉樹

它的中序遍歷結(jié)果為

節(jié)點8的前驅(qū)節(jié)點為7

因此有以下情況:

情況1

如果左子樹不為空 node.left != null

例如上圖二叉樹中的6 13 8均符合這種情況

前驅(qū)節(jié)點predecessor = node.left.right.right.right...

終止條件為:right 為null

情況2：

node.left == null && node.parent != null

例如上圖二叉樹中的7 11 9 1 均符合這種情況

前驅(qū)節(jié)點predecessor = node.parent.parent.parent....

終止條件為:node的parent在右子樹當中

情況3：

node.left == null && node.parent == null

這種情況的假設(shè)上圖二叉樹的左子樹不存在巷帝，即滿足以上條件

在這種情況下，是沒有前驅(qū)節(jié)點的

因此查找前驅(qū)節(jié)點的實現(xiàn)代碼是這樣的

private Node<E> predecessor(Node<E> node) {
    if (node == null) return null;
    Node<E> p = node.left;
    if (node.left != null) {
        //從左子樹中找前驅(qū)
        while (p.right != null) {
            p = p.right;
        }
        return p;
    }
    //從父節(jié)點扫夜，祖父節(jié)點中尋找前驅(qū)節(jié)點
    while (node.parent != null && node == node.parent.left) {
        node = node.parent;
    }
    //node.parent == null
    //node == node.parent.right
    return node.parent;
}

• 后繼節(jié)點(successor)

后繼節(jié)點：中序遍歷是的后一個節(jié)點

如果是二叉搜索樹楞泼，后繼節(jié)點就是后一個比它大的節(jié)點

因此，如果有以下的一棵二叉樹

通過中序遍歷后的結(jié)果為

同樣的笤闯，也有以下幾種情況

情況1：

node.right != null

例如上圖二叉樹中的1 8 4均符合這種情況

successor = node.right.left.left.left....

終止條件：left == null

情況2：

node.right == null && node.parent != null

例如上圖二叉樹中的7 6 3 11均符合這種情況

successor = node.parent.parent.parent....

終止條件：node在parent的左子樹中

情況3：

node.right = null && node.parent == null

那就沒有前驅(qū)節(jié)點

例如：沒有右子樹的根節(jié)點

因此查找后繼節(jié)點的代碼是這樣的

private Node<E> successor(Node<E> node) {
    if (node == null) return null;
    Node<E> p = node.right;
    if (p != null) {
        //從右子樹中找前驅(qū)
        while (p.left != null) {
            p = p.left;
        }
        return p;
    }
    //從父節(jié)點堕阔，祖父節(jié)點中尋找前驅(qū)節(jié)點
    while (node.parent != null && node == node.parent.right) {
        node = node.parent;
    }
    //node.parent == null
    //node == node.parent.right
    return node.parent;
}

GitHub地址
本節(jié)完！