為了后續(xù)學(xué)習(xí)堆排序以及MySQL索引等知識，接下來會重溫一下樹這種數(shù)據(jù)結(jié)構(gòu)，包括二叉樹、赫夫曼樹、二叉排序樹(BST)、平衡二叉樹(AVL)、B樹和B+樹。本文只涉及二叉樹，其他樹后續(xù)再細說。

一、樹的介紹

「1. 為什么要有樹這種結(jié)構(gòu)？」

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

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

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

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

「2. 二叉樹：」

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

二、二叉樹的遍歷

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

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

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

• 后序遍歷：左右根。如果左子節(jié)點不為空，遞歸后序遍歷；如果右子節(jié)點不為空，遞歸后序遍歷；輸出當(dāng)前節(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. 構(gòu)建一棵二叉樹：」

假如要構(gòu)建這樣一棵樹，那么代碼實現(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ī)則，前中后序的遍歷結(jié)果應(yīng)該是：

• 前序遍歷：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) {
 // 先輸出當(dāng)前節(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());
 }
 // 輸出當(dāng)前節(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());
 }
 // 輸出當(dāng)前節(jié)點
 System.out.println(root.getElement());
}

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

三、二叉樹的刪除

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

• 如果二叉樹只有一個節(jié)點，直接將該節(jié)點設(shè)置為null即可；
• 判斷當(dāng)前節(jié)點的左子節(jié)點是否為要刪除的節(jié)點，如果是，就刪除當(dāng)前節(jié)點左子節(jié)點；
• 判斷當(dāng)前節(jié)點的右子節(jié)點是否為要刪除的節(jié)點，如果是，就刪除當(dāng)前節(jié)點右子節(jié)點；
• 如果上述操作沒有找到要刪除的節(jié)點，就向當(dāng)前節(jié)點左子樹遞歸；
• 如果向左子樹遞歸也沒找到要刪除的節(jié)點，就向當(dāng)前節(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開始依次標(biāo)上號，這些號得滿足：

• n號元素的左節(jié)點標(biāo)號為2n + 1；
• n號元素的右節(jié)點標(biāo)號為2n + 2；
• n號元素的父節(jié)點標(biāo)號為(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) {
 // 輸出當(dāng)前元素
 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)前序遍歷的代碼，中/后序遍歷就換一下輸出當(dāng)前元素的位置就可以了。

五、線索化二叉樹

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

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

「1. 中序線索化二叉樹：」

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

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

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

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

public class TreeNode {
 private Object element;
 private TreeNode left;
 private TreeNode right;
 private int leftType; // 0左子樹， 1前驅(qū)節(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());

        // 處理當(dāng)前節(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應(yīng)該是節(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é)果和預(yù)期一致，說明線索化成功。

六、遍歷線索化二叉樹

上面線索化了二叉樹，有什么用呢？其實就是為了可以更簡單地進行遍歷。線索化之后，各個節(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());
   // 如果當(dāng)前節(jié)點的右指針指向的是后繼節(jié)點，就直接輸出
   while(curNode.getRightType() == 1) {
    curNode = curNode.getRight();
    System.out.println(curNode.getElement());
   }
   // 遇到了不等于1的，替換遍歷的節(jié)點
   curNode = curNode.getRight();
  }
}

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