為了后續(xù)學(xué)習(xí)堆排序以及MySQL索引等知識(shí)，接下來會(huì)重溫一下樹這種數(shù)據(jù)結(jié)構(gòu)，包括二叉樹、赫夫曼樹、二叉排序樹(BST)、平衡二叉樹(AVL)、B樹和B+樹。本文只涉及二叉樹，其他樹后續(xù)再細(xì)說。
一、樹的介紹
「1. 為什么要有樹這種結(jié)構(gòu)？」
有了數(shù)組和鏈表，為什么還要有樹？先來看看數(shù)組和鏈表的優(yōu)缺點(diǎn)。
數(shù)組：因?yàn)橛兴饕?，所以可以快速地訪問到某個(gè)元素。但是如果要進(jìn)行插入或者刪除的話，被插入/刪除位置之后的元素都得移動(dòng)，如果插入后超過了數(shù)組容量，還得進(jìn)行數(shù)組擴(kuò)容。可見，數(shù)組查詢快，增刪慢。
鏈表：沒有索引，要查詢某個(gè)元素，得從第一個(gè)元素開始，一個(gè)一個(gè)往后遍歷。但是要進(jìn)行插入或者刪除，無(wú)需移動(dòng)元素，只要找到插入/刪除位置的前一個(gè)元素即可。所以鏈表查詢慢，增刪快。
說到這里，那肯定知道樹存在的意義了，沒錯(cuò)，它吸收了鏈表和數(shù)組的優(yōu)點(diǎn)，查詢快，增刪也快。
「2. 二叉樹：」
每個(gè)節(jié)點(diǎn)最多有兩個(gè)葉子節(jié)點(diǎn)的樹，叫做二叉樹。假如一棵樹有n層，所以的葉子節(jié)點(diǎn)都在第n層，并且節(jié)點(diǎn)總數(shù)為(2^n) - 1，那么就把這棵樹稱為「滿二叉樹」。如果最后一層的葉子節(jié)點(diǎn)左邊是連續(xù)的，倒數(shù)第二層右邊的葉子節(jié)點(diǎn)是連續(xù)的，那就稱為「完全二叉樹」。
二、二叉樹的遍歷
前序遍歷、后序遍歷和中序遍歷，這里的前中后指的是父節(jié)點(diǎn)的遍歷時(shí)機(jī)。
前序遍歷：根左右。先輸出當(dāng)前節(jié)點(diǎn)；如果左子節(jié)點(diǎn)不為空，則遞歸進(jìn)行前序遍歷；如果右子節(jié)點(diǎn)不為空，則繼續(xù)遞歸前序遍歷。
中序遍歷：左根右。如果左子節(jié)點(diǎn)不為空，則遞歸中序遍歷；輸出當(dāng)前節(jié)點(diǎn)；如果右子節(jié)點(diǎn)不為空，則遞歸中序遍歷。
后序遍歷：左右根。如果左子節(jié)點(diǎn)不為空，遞歸后序遍歷；如果右子節(jié)點(diǎn)不為空，遞歸后序遍歷；輸出當(dāng)前節(jié)點(diǎn)。
「1. 新建一個(gè)TreeNode類：」
這個(gè)是節(jié)點(diǎn)類，省略了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)建這樣一棵樹，那么代碼實(shí)現(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)該是：
「3. 代碼實(shí)現(xiàn)三種遍歷方式：」
/**
* 前序遍歷
*
* @param root
*/
public static void preOrder(TreeNode root) {
// 先輸出當(dāng)前節(jié)點(diǎn)
System.out.println(root.getElement());
// 判斷左子節(jié)點(diǎn)是否為空，不為空就遞歸
if (root.getLeft() != null) {
preOrder(root.getLeft());
}
// 判斷右子節(jié)點(diǎn)是否為空，不為空就遞歸
if (root.getRight() != null) {
preOrder(root.getRight());
}
}
/**
* 中序遍歷
*
* @param root
*/
public static void infixOrder(TreeNode root) {
// 判斷左子節(jié)點(diǎn)是否為空，不為空就遞歸
if (root.getLeft() != null) {
infixOrder(root.getLeft());
}
// 輸出當(dāng)前節(jié)點(diǎn)
System.out.println(root.getElement());
// 判斷右子節(jié)點(diǎn)是否為空，不為空就遞歸
if (root.getRight() != null) {
infixOrder(root.getRight());
}
}
/**
* 后序遍歷
* @param root
*/
public static void postOrder(TreeNode root) {
// 判斷左子節(jié)點(diǎn)是否為空，不為空就遞歸
if (root.getLeft() != null) {
postOrder(root.getLeft());
}
// 判斷右子節(jié)點(diǎn)是否為空，不為空就遞歸
if (root.getRight() != null) {
postOrder(root.getRight());
}
// 輸出當(dāng)前節(jié)點(diǎn)
System.out.println(root.getElement());
}
二叉樹的查找就不說了，都會(huì)遍歷了還不會(huì)查找嗎？
三、二叉樹的刪除
這里說的刪除先不考慮子節(jié)點(diǎn)上浮的情況，即如果刪除的非葉子節(jié)點(diǎn)，那就直接刪除整棵子樹。刪除的思路如下：
- 如果二叉樹只有一個(gè)節(jié)點(diǎn)，直接將該節(jié)點(diǎn)設(shè)置為null即可；
- 判斷當(dāng)前節(jié)點(diǎn)的左子節(jié)點(diǎn)是否為要?jiǎng)h除的節(jié)點(diǎn)，如果是，就刪除當(dāng)前節(jié)點(diǎn)左子節(jié)點(diǎn)；
- 判斷當(dāng)前節(jié)點(diǎn)的右子節(jié)點(diǎn)是否為要?jiǎng)h除的節(jié)點(diǎn)，如果是，就刪除當(dāng)前節(jié)點(diǎn)右子節(jié)點(diǎn)；
- 如果上述操作沒有找到要?jiǎng)h除的節(jié)點(diǎn)，就向當(dāng)前節(jié)點(diǎn)左子樹遞歸；
- 如果向左子樹遞歸也沒找到要?jiǎng)h除的節(jié)點(diǎn)，就向當(dāng)前節(jié)點(diǎn)右子樹遞歸；
「代碼實(shí)現(xiàn)：」
/**
* 刪除節(jié)點(diǎn)
* @param node
*/
public static void delNode(TreeNode root, Object ele) {
// 如果二叉樹為空，直接return
if (root == null) {
return;
}
// 如果只有一個(gè)節(jié)點(diǎn)，或者root就是要?jiǎng)h除的節(jié)點(diǎn)，直接置空
if ((root.getLeft() == null && root.getRight() == null) ||
root.getElement() == ele) {
root.setElement(null);
root.setLeft(null);
root.setRight(null);
return;
}
// 判斷左子節(jié)點(diǎn)是否為要?jiǎng)h除的節(jié)點(diǎn)
if (root.getLeft() != null && root.getLeft().getElement()== ele) {
root.setLeft(null);
return;
}
// 判斷右子節(jié)點(diǎn)是否為要?jiǎng)h除的節(jié)點(diǎn)
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);
}
}
四、順序存儲(chǔ)二叉樹
所謂順序存儲(chǔ)二叉樹，就是將二叉樹的元素用數(shù)組存起來，并且在數(shù)組中遍歷這些元素時(shí)依舊能體現(xiàn)出前/中/后序遍歷。為了達(dá)到這個(gè)目的，所以順序存儲(chǔ)二叉樹有一些要求：
我們給二叉樹的元素從上到下從左往右從0開始依次標(biāo)上號(hào)，這些號(hào)得滿足：
- n號(hào)元素的左節(jié)點(diǎn)標(biāo)號(hào)為
2n + 1； - n號(hào)元素的右節(jié)點(diǎn)標(biāo)號(hào)為
2n + 2； - n號(hào)元素的父節(jié)點(diǎn)標(biāo)號(hào)為
(n-1) / 2；
怎么將二叉樹用數(shù)組存起來就不說了，進(jìn)行層序遍歷就好了，從上到下從左往右將元素依次存進(jìn)數(shù)組。主要來看一看，用數(shù)組保存起來的二叉樹。如何遍歷，才能達(dá)到二叉樹前/中/后序遍歷的效果。
「代碼實(shí)現(xiàn)：」
/**
* 前序遍歷順序存儲(chǔ)的二叉樹
* @param arr
*/
public static void preOder(int[] arr) {
if (arr == null || arr.length == 0) {
return;
}
preOder(arr, 0);
}
/**
* 前序遍歷順序存儲(chǔ)的二叉樹
* @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));
}
}
這就是實(shí)現(xiàn)前序遍歷的代碼，中/后序遍歷就換一下輸出當(dāng)前元素的位置就可以了。
五、線索化二叉樹
二叉樹還是拿這棵二叉樹來說，3，2，1節(jié)點(diǎn)的left和right指針都沒用到，4節(jié)點(diǎn)的right指針沒有用到，也就是整棵二叉樹有7個(gè)指針是沒有用到的。其實(shí)我們可以充分利用這些指針，讓這些指針指向前/中/后序遍歷的前/后一個(gè)節(jié)點(diǎn)，這就叫「線索化二叉樹」。根據(jù)指針指向的不同節(jié)點(diǎn)，又可以分為前/中/后序線索化二叉樹。
注意，要線索化二叉樹，得滿足一個(gè)條件，假如總共有n個(gè)節(jié)點(diǎn)，那么未使用的指針數(shù)應(yīng)為n + 1。一個(gè)節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)稱為前驅(qū)節(jié)點(diǎn)，后一個(gè)節(jié)點(diǎn)稱為后繼節(jié)點(diǎn)。
「1. 中序線索化二叉樹：」
上面這棵二叉樹，中序遍歷的結(jié)果是：3, 5, 2, 6, 1, 4，我們讓有空閑指針的節(jié)點(diǎn)，left指針指向它的前驅(qū)，right指針指向它的后繼。首先從3開始，3沒有前驅(qū)，后繼是5，所以3的right指針指向5；然后是2，讓它left指向5，right指向6；1的left指向6，right指向4。中序線索化的二叉樹如下圖(綠色是左指針，黃色是右指針)：
中序線索化二叉樹- 線索化二叉樹后，
left指針可能指向的是左子樹，也可能指向前驅(qū)節(jié)點(diǎn)； right指針可能指向右子樹，也可能指向后繼節(jié)點(diǎn)；
「2. 代碼實(shí)現(xiàn)：」
首先，對(duì)于TreeNode節(jié)點(diǎn)類，得增加兩個(gè)屬性，用來表示左右節(jié)點(diǎn)的類型，約定用0表示子樹，用1表示前驅(qū)/后繼。改造后的節(jié)點(diǎn)類如下：
public class TreeNode {
private Object element;
private TreeNode left;
private TreeNode right;
private int leftType; // 0左子樹， 1前驅(qū)節(jié)點(diǎn)
private int rightType; // 0右子樹，1后繼節(jié)點(diǎn)
}
上面所有操作二叉樹的方法，我都封裝在TreeUtil中，要線索化二叉樹，還需要在TreeUtil中定義一個(gè)變量，用來保存前一個(gè)節(jié)點(diǎn)，如下：
private static TreeNode preNode; // 前一個(gè)節(jié)點(diǎn)
線索化二叉樹的代碼：
public static void inSeqLineTree(TreeNode curNode) {
if (curNode == null){
return;
}
// 處理左子樹
inSeqLineTree(curNode.getLeft());
// 處理當(dāng)前節(jié)點(diǎn)
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());
}
那么怎么驗(yàn)證有沒有線索化成功呢？如果成功的話，節(jié)點(diǎn)3的right應(yīng)該是節(jié)點(diǎn)5，并且節(jié)點(diǎn)3的型是1；節(jié)點(diǎn)2的left是5，并且節(jié)點(diǎn)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é)點(diǎn)3的right：%s, 類型：%s %n", node3.getRight().getElement(), node3.getRightType());
System.out.printf("節(jié)點(diǎn)2的left：%s, 類型：%s %n", node4.getLeft().getElement(), node4.getLeftType());
}
運(yùn)行結(jié)果結(jié)果和預(yù)期一致，說明線索化成功。
六、遍歷線索化二叉樹
上面線索化了二叉樹，有什么用呢？其實(shí)就是為了可以更簡(jiǎn)單地進(jìn)行遍歷。線索化之后，各個(gè)節(jié)點(diǎn)的指向有變化，所以原來的遍歷方式就用不了了，現(xiàn)在可以用非遞歸的方式進(jìn)行遍歷，可以提高效率。
遍歷線索化二叉樹的代碼：
public static void seqOrder(TreeNode root) {
TreeNode curNode = root;
while(curNode != null) {
// 找到leftType為1的節(jié)點(diǎn)
while(curNode.getLeftType() == 0) {
curNode = curNode.getLeft();
}
// 找到就輸出
System.out.println(curNode.getElement());
// 如果當(dāng)前節(jié)點(diǎn)的右指針指向的是后繼節(jié)點(diǎn)，就直接輸出
while(curNode.getRightType() == 1) {
curNode = curNode.getRight();
System.out.println(curNode.getElement());
}
// 遇到了不等于1的，替換遍歷的節(jié)點(diǎn)
curNode = curNode.getRight();
}
}
傳入root后，運(yùn)行結(jié)果是和中序遍歷的結(jié)果一致的，說明沒問題。
