為了后續(xù)學習堆排序以及MySQL索引等知識，接下來會重溫一下樹這種數(shù)據(jù)結構，包括二叉樹、赫夫曼樹、二叉排序樹(BST)、平衡二叉樹(AVL)、B樹和B+樹。

一、樹的介紹

1. 為什么要有樹這種結構？

有了數(shù)組和鏈表，為什么還要有樹？先來看看數(shù)組和鏈表的優(yōu)缺點。

• 數(shù)組：因為有索引，所以可以快速地訪問到某個元素。但是如果要進行插入或者刪除的話，被插入/刪除位置之后的元素都得移動，如果插入后超過了數(shù)組容量，還得進行數(shù)組擴容?？梢姡瑪?shù)組查詢快，增刪慢。

• 鏈表：沒有索引，要查詢某個元素，得從第一個元素開始，一個一個往后遍歷。但是要進行插入或者刪除，無需移動元素，只要找到插入/刪除位置的前一個元素即可。所以鏈表查詢慢，增刪快。

說到這里，那肯定知道樹存在的意義了，沒錯，它吸收了鏈表和數(shù)組的優(yōu)點，查詢快，增刪也快。

歡迎大家關注我的公眾號 javawebkf，目前正在慢慢地將簡書文章搬到公眾號，以后簡書和公眾號文章將同步更新，且簡書上的付費文章在公眾號上將免費。

2. 二叉樹：

每個節(jié)點最多有兩個葉子節(jié)點的樹，叫做二叉樹。假如一棵樹有n層，所以的葉子節(jié)點都在第n層，并且節(jié)點總數(shù)為(2^n) - 1，那么就把這棵樹稱為滿二叉樹。如果最后一層的葉子節(jié)點左邊是連續(xù)的，倒數(shù)第二層右邊的葉子節(jié)點是連續(xù)的，那就稱為完全二叉樹。

二、二叉樹的遍歷

前序遍歷、后序遍歷和中序遍歷，這里的前中后只的是父節(jié)點的遍歷時機。

• 前序遍歷：根左右。先輸出當前節(jié)點；如果左子節(jié)點不為空，則遞歸進行前序遍歷；如果右子節(jié)點不為空，則繼續(xù)遞歸前序遍歷。

• 中序遍歷：左根右。如果左子節(jié)點不為空，則遞歸中序遍歷；輸出當前節(jié)點；如果右子節(jié)點不為空，則遞歸中序遍歷。

• 后序遍歷：左右根。如果左子節(jié)點不為空，遞歸后序遍歷；如果右子節(jié)點不為空，遞歸后序遍歷；輸出當前節(jié)點。

1. 新建一個TreeNode類：

這個是節(jié)點類，省略了set/get方法。

public class TreeNode {
    
    private Object element;
    private TreeNode left;
    private TreeNode right;
    
    public TreeNode() {}
    public TreeNode(Object element) {
        this.element = element;
    }
}

2. 構建一棵二叉樹：

二叉樹

假如要構建這樣一棵樹，那么代碼實現(xiàn)就是：

TreeNode root = new TreeNode(6);
TreeNode node1 = new TreeNode(5);
TreeNode node2 = new TreeNode(4);
root.setLeft(node1);
root.setRight(node2);
TreeNode node3 = new TreeNode(3);
node1.setLeft(node3);
TreeNode node4 = new TreeNode(2);
node1.setRight(node4);
TreeNode node5 = new TreeNode(1);
node2.setLeft(node5);

按照遍歷規(guī)則，前中后序的遍歷結果應該是：

• 前序遍歷：6, 5, 3, 2, 4, 1
• 中序遍歷：3, 5, 2, 6, 1, 4
• 后序遍歷：3, 2, 5, 1, 4, 6

3. 代碼實現(xiàn)三種遍歷方式：

/**
 * 前序遍歷
 * 
 * @param root
 */
public static void preOrder(TreeNode root) {
    // 先輸出當前節(jié)點
    System.out.println(root.getElement());
    // 判斷左子節(jié)點是否為空，不為空就遞歸
    if (root.getLeft() != null) {
        preOrder(root.getLeft());
    }
    // 判斷右子節(jié)點是否為空，不為空就遞歸
    if (root.getRight() != null) {
        preOrder(root.getRight());
    }
}

/**
 * 中序遍歷
 * 
 * @param root
 */
public static void infixOrder(TreeNode root) {
    // 判斷左子節(jié)點是否為空，不為空就遞歸
    if (root.getLeft() != null) {
        infixOrder(root.getLeft());
    }
    // 輸出當前節(jié)點
    System.out.println(root.getElement());
    // 判斷右子節(jié)點是否為空，不為空就遞歸
    if (root.getRight() != null) {
        infixOrder(root.getRight());
    }
}

/**
 * 后序遍歷
 * @param root
 */
public static void postOrder(TreeNode root) {
    // 判斷左子節(jié)點是否為空，不為空就遞歸
    if (root.getLeft() != null) {
        postOrder(root.getLeft());
    }
    // 判斷右子節(jié)點是否為空，不為空就遞歸
    if (root.getRight() != null) {
        postOrder(root.getRight());
    }
    // 輸出當前節(jié)點
    System.out.println(root.getElement());
}

二叉樹的查找就不說了，都會遍歷了還不會查找嗎？

三、二叉樹的刪除

這里說的刪除先不考慮子節(jié)點上浮的情況，即如果刪除的非葉子節(jié)點，那就直接刪除整棵子樹。刪除的思路如下：

• 如果二叉樹只有一個節(jié)點，直接將該節(jié)點設置為null即可；
• 判斷當前節(jié)點的左子節(jié)點是否為要刪除的節(jié)點，如果是，就刪除當前節(jié)點左子節(jié)點；
• 判斷當前節(jié)點的右子節(jié)點是否為要刪除的節(jié)點，如果是，就刪除當前節(jié)點右子節(jié)點；
• 如果上述操作沒有找到要刪除的節(jié)點，就向當前節(jié)點左子樹遞歸；
• 如果向左子樹遞歸也沒找到要刪除的節(jié)點，就向當前節(jié)點右子樹遞歸；

代碼實現(xiàn)：

/**
* 刪除節(jié)點
* @param node
*/
public static void delNode(TreeNode root, Object ele) {
    // 如果二叉樹為空，直接return
    if (root == null) {
        return;
    }
    // 如果只有一個節(jié)點，或者root就是要刪除的節(jié)點，直接置空
    if ((root.getLeft() == null && root.getRight() == null) ||
            root.getElement() == ele) {
        root.setElement(null);
        root.setLeft(null);
        root.setRight(null);
        return;
    }
    // 判斷左子節(jié)點是否為要刪除的節(jié)點
    if (root.getLeft() != null && root.getLeft().getElement()== ele) {
        root.setLeft(null);
        return;
    }
    // 判斷右子節(jié)點是否為要刪除的節(jié)點
    if (root.getRight() != null && root.getRight().getElement()== ele) {
        root.setRight(null);
        return;
    }
    // 向左子樹遞歸
    if (root.getLeft() != null) {
        delNode(root.getLeft(), ele);
    }
    // 向右子樹遞歸
    if (root.getRight() != null) {
        delNode(root.getRight(), ele);
    }
}

四、順序存儲二叉樹

所謂順序存儲二叉樹，就是將二叉樹的元素用數(shù)組存起來，并且在數(shù)組中遍歷這些元素時依舊能體現(xiàn)出前/中/后序遍歷。為了達到這個目的，所以順序存儲二叉樹有一些要求：

• 通常只考慮完全二叉樹；

我們給二叉樹的元素從上到下從左往右從0開始依次標上號，這些號得滿足：

• n號元素的左節(jié)點標號為2n + 1；
• n號元素的右節(jié)點標號為2n + 2；
• n號元素的父節(jié)點標號為(n-1) / 2；

怎么將二叉樹用數(shù)組存起來就不說了，進行層序遍歷就好了，從上到下從左往右將元素依次存進數(shù)組。主要來看一看，用數(shù)組保存起來的二叉樹。如何遍歷，才能達到二叉樹前/中/后序遍歷的效果。

代碼實現(xiàn)：

/**
* 前序遍歷順序存儲的二叉樹
* @param arr
*/
public static void preOder(int[] arr) {
    if (arr == null || arr.length == 0) {
        return;
    }
    preOder(arr, 0);
}
    
/**
* 前序遍歷順序存儲的二叉樹
* @param index
*/
private static void preOder(int[] arr, int index) {
    // 輸出當前元素
    System.out.println(arr[index]);
    // 向左遞歸
    if ((index * 2 + 1) < arr.length) {
        preOder(arr, (index * 2 + 1));
    }
    // 向右遞歸
    if ((index * 2 + 2) < arr.length) {
        preOder(arr, (index * 2 + 2));
    }
}

這就是實現(xiàn)前序遍歷的代碼，中/后序遍歷就換一下輸出當前元素的位置就可以了。

五、線索化二叉樹

二叉樹

還是拿這棵二叉樹來說，3，2，1節(jié)點的left和right指針都沒用到，4節(jié)點的right指針沒有用到，也就是整棵二叉樹有7個指針是沒有用到的。其實我們可以充分利用這些指針，讓這些指針指向前/中/后序遍歷的前/后一個節(jié)點，這就叫線索化二叉樹。根據(jù)指針指向的不同節(jié)點，又可以分為前/中/后序線索化二叉樹。

注意，要線索化二叉樹，得滿足一個條件，假如總共有n個節(jié)點，那么未使用的指針數(shù)應為n + 1。一個節(jié)點的前一個節(jié)點稱為前驅節(jié)點，后一個節(jié)點稱為后繼節(jié)點。

1. 中序線索化二叉樹：

上面這棵二叉樹，中序遍歷的結果是：3, 5, 2, 6, 1, 4，我們讓有空閑指針的節(jié)點，left指針指向它的前驅，right指針指向它的后繼。首先從3開始，3沒有前驅，后繼是5，所以3的right指針指向5；然后是2，讓它left指向5，right指向6；1的left指向6，right指向4。中序線索化的二叉樹如下圖(綠色是左指針，黃色是右指針)：

中序線索化二叉樹

• 線索化二叉樹后，left指針可能指向的是左子樹，也可能指向前驅節(jié)點；
• right指針可能指向右子樹，也可能指向后繼節(jié)點；

2. 代碼實現(xiàn)：

首先，對于TreeNode節(jié)點類，得增加兩個屬性，用來表示左右節(jié)點的類型，約定用0表示子樹，用1表示前驅/后繼。改造后的節(jié)點類如下：

public class TreeNode {
    private Object element;
    private TreeNode left;
    private TreeNode right;
    private int leftType; // 0左子樹， 1前驅節(jié)點
    private int rightType; // 0右子樹，1后繼節(jié)點
}

上面所有操作二叉樹的方法，我都封裝在TreeUtil中，要線索化二叉樹，還需要在TreeUtil中定義一個變量，用來保存前一個節(jié)點，如下：

private static TreeNode preNode; // 前一個節(jié)點

線索化二叉樹的代碼：

public static void inSeqLineTree(TreeNode curNode) {
        if (curNode == null){
            return;
        }
        // 處理左子樹
        inSeqLineTree(curNode.getLeft());

        // 處理當前節(jié)點
        if (curNode.getLeft() == null){
            curNode.setLeft(preNode);
            curNode.setLeftType(1);
        }
        if (preNode != null && preNode.getRight() == null){
            preNode.setRight(curNode);
            preNode.setRightType(1);
        }
        preNode = curNode;

        // 處理右子樹
        inSeqLineTree(curNode.getRight());
}

那么怎么驗證有沒有線索化成功呢？如果成功的話，節(jié)點3的right應該是節(jié)點5，并且節(jié)點3的型是1；節(jié)點2的left是5，并且節(jié)點2的類型是1。

public static void main(String[] args) {
        TreeNode root = new TreeNode(6);
        TreeNode node1 = new TreeNode(5);
        TreeNode node2 = new TreeNode(4);
        root.setLeft(node1);
        root.setRight(node2);
        TreeNode node3 = new TreeNode(3);
        node1.setLeft(node3);
        TreeNode node4 = new TreeNode(2);
        node1.setRight(node4);
        TreeNode node5 = new TreeNode(1);
        node2.setLeft(node5);

        TreeUtil.inSeqLineTree(root); // 6, 5, 3, 2, 4, 1

        System.out.printf("節(jié)點3的right：%s, 類型：%s %n", node3.getRight().getElement(), node3.getRightType());
        System.out.printf("節(jié)點2的left：%s, 類型：%s %n", node4.getLeft().getElement(), node4.getLeftType());
}

運行結果

結果和預期一致，說明線索化成功。

六、遍歷線索化二叉樹

上面線索化了二叉樹，有什么用呢？其實就是為了可以更簡單地進行遍歷。線索化之后，各個節(jié)點的指向有變化，所以原來的遍歷方式就用不了了，現(xiàn)在可以用非遞歸的方式進行遍歷，可以提高效率。

遍歷線索化二叉樹的代碼：

public static void seqOrder(TreeNode root) {
        TreeNode curNode = root;
        while(curNode != null) {
            // 找到leftType為1的節(jié)點
            while(curNode.getLeftType() == 0) {
                curNode = curNode.getLeft();
            }
            // 找到就輸出
            System.out.println(curNode.getElement());
            // 如果當前節(jié)點的右指針指向的是后繼節(jié)點，就直接輸出
            while(curNode.getRightType() == 1) {
                curNode = curNode.getRight();
                System.out.println(curNode.getElement());
            }
            // 遇到了不等于1的，替換遍歷的節(jié)點
            curNode = curNode.getRight();
        }
}

傳入root后，運行結果是和中序遍歷的結果一致的，說明沒問題。