作者：nnngu
GitHub：https://github.com/nnngu
博客園：http://www.cnblogs.com/nnngu
簡書：http://www.reibang.com/users/1df20d76ea5c
知乎：https://www.zhihu.com/people/nnngu/posts
上一篇總結(jié)了二叉樹拣帽，這一篇要總結(jié)的是線索二叉樹，我想從以下幾個方面進行總結(jié)棋返。
1、什么是線索二叉樹礼搁？
2钓猬、為什么要建立線索二叉樹普舆？
3誊锭、如何將二叉樹線索化表悬？
4、線索二叉樹的常見操作及實現(xiàn)思路丧靡？
5蟆沫、算法實現(xiàn)代碼？
1温治、什么是線索二叉樹
線索二叉樹：
按照某種方式對二叉樹進行遍歷饭庞，可以把二叉樹中所有節(jié)點排序為一個線性序列，在該序列中熬荆，除第一個節(jié)點外每個節(jié)點有且僅有一個直接前驅(qū)節(jié)點舟山；除最后一個節(jié)點外每一個節(jié)點有且僅有一個直接后繼節(jié)點；
在N個節(jié)點的二叉樹中卤恳，每個節(jié)點有2個指針累盗，所以一共有2N個指針，除了根節(jié)點以外纬黎，每一個節(jié)點都有一個指針從它的父節(jié)點指向它幅骄，所以一共使用了N-1個指針劫窒，所以剩下2N-(N-1)也就是N+1個空指針本今；
如果能利用這些空指針域來存放指向該節(jié)點的直接前驅(qū)或是直接后繼的指針，則可由此信息直接找到在該遍歷次序下的前驅(qū)節(jié)點或后繼節(jié)點主巍，從而比遞歸遍歷提高了遍歷速度冠息，節(jié)省了建立系統(tǒng)遞歸棧所使用的存儲空間；
這些被重新利用起來的空指針就被稱為線索（Thread）孕索，加上了線索的二叉樹就是線索二叉樹逛艰；如圖：
2、為什么要建立線索二叉樹
有了二叉樹不就足夠了嗎搞旭？那為什么還要弄個線索二叉樹出來呢散怖？
在原來的二叉鏈表中，查找節(jié)點的左肄渗，右孩子可以直接實現(xiàn)镇眷，可是如果要找該節(jié)點的前驅(qū)和后繼節(jié)點呢？這就變得非常困難翎嫡，所以為了實現(xiàn)這個常見的需求欠动，我們要在每個節(jié)點中增加兩個指針域來存放遍歷時得到的前驅(qū)和后繼節(jié)點，這樣就可以通過該指針直接或間接訪問其前驅(qū)和后繼節(jié)點。
3具伍、如何將二叉樹線索化
按某種次序遍歷二叉樹翅雏，在遍歷過程中用線索取代空指針即可。
下面是線索二叉樹和線索二叉鏈表的示意圖人芽，它可以幫助我們更好地理解線索二叉樹望几。
4、線索二叉樹的常見操作及實現(xiàn)思路
4-1萤厅、二叉樹線索化
實現(xiàn)思路：按某種次序遍歷二叉樹橄妆，在遍歷過程中用線索取代空指針即可。
4-2祈坠、遍歷
實現(xiàn)思路：以中序遍歷為例害碾，首先找到中序遍歷的開始節(jié)點，然后利用線索依次查找后繼節(jié)點即可赦拘。
5慌随、實現(xiàn)代碼
代碼：
Node.java
public class Node {
private int data;
private Node left;
private boolean leftIsThread; // 左孩子是否為線索
private Node right;
private boolean rightIsThread; // 右孩子是否為線索
public Node(int data) {
this.data = data;
this.left = null;
this.leftIsThread = false;
this.right = null;
this.rightIsThread = false;
}
public int getData() {
return data;
}
public void setData(int data) {
this.data = data;
}
public Node getLeft() {
return left;
}
public void setLeft(Node left) {
this.left = left;
}
public boolean isLeftIsThread() {
return leftIsThread;
}
public void setLeftIsThread(boolean leftIsThread) {
this.leftIsThread = leftIsThread;
}
public Node getRight() {
return right;
}
public void setRight(Node right) {
this.right = right;
}
public boolean isRightIsThread() {
return rightIsThread;
}
public void setRightIsThread(boolean rightIsThread) {
this.rightIsThread = rightIsThread;
}
@Override
public boolean equals(Object obj) {
if (obj instanceof Node) {
Node temp = (Node) obj;
if (temp.getData() == this.data) {
return true;
}
}
return false;
}
@Override
public int hashCode() {
return super.hashCode() + this.data;
}
}
ThreadTree.java
public class ThreadTree {
private Node root; // 根節(jié)點
private int size; // 大小
private Node pre = null; // 線索化的時候保存前驅(qū)
public ThreadTree() {
this.root = null;
this.size = 0;
this.pre = null;
}
public ThreadTree(int[] data) {
this.pre = null;
this.size = data.length;
this.root = createTree(data, 1); // 創(chuàng)建二叉樹
}
/**
* 創(chuàng)建二叉樹
*
* @param data
* @param index
* @return
*/
public Node createTree(int[] data, int index) {
if (index > data.length) {
return null;
}
Node node = new Node(data[index - 1]);
Node left = createTree(data, 2 * index);
Node right = createTree(data, 2 * index + 1);
node.setLeft(left);
node.setRight(right);
return node;
}
/**
* 將以root為根節(jié)點的二叉樹線索化
*/
public void inThread(Node root) {
if (root != null) {
inThread(root.getLeft()); // 線索化左孩子
if (null == root.getLeft()) { // 左孩子為空
root.setLeftIsThread(true); // 將左孩子設(shè)置為線索
root.setLeft(pre);
}
if (pre != null && null == pre.getRight()) { // 右孩子為空
pre.setRightIsThread(true);
pre.setRight(root);
}
pre = root;
inThread(root.getRight()); // 線索化右孩子
}
}
/**
* 中序遍歷線索二叉樹
*/
public void inThreadList(Node root) {
if (root != null) {
while (root != null && !root.isLeftIsThread()) {
// 如果左孩子不是線索
root = root.getLeft();
}
do {
System.out.print(root.getData() + " ");
if (root.isRightIsThread()) {
// 如果右孩子是線索
root = root.getRight();
} else {
// 有右孩子
root = root.getRight();
while (root != null && !root.isLeftIsThread()) {
root = root.getLeft();
}
}
} while (root != null);
}
}
/**
* 中序遞歸遍歷
*/
public void inList(Node root) {
if (root != null) {
inList(root.getLeft());
System.out.print(root.getData() + " ");
inList(root.getRight());
}
}
public Node getRoot() {
return root;
}
public void setRoot(Node root) {
this.root = root;
}
public int getSize() {
return size;
}
public void setSize(int size) {
this.size = size;
}
}
ThreadTreeTest.java
public class ThreadTreeTest {
public static void main(String[] args) {
int[] data = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
ThreadTree threadTree = new ThreadTree(data); // 創(chuàng)建普通二叉樹
System.out.println("中序遞歸遍歷二叉樹");
threadTree.inList(threadTree.getRoot()); // 中序遞歸遍歷二叉樹
System.out.println();
threadTree.inThread(threadTree.getRoot()); // 采用中序遍歷將二叉樹線索化
System.out.println("中序遍歷線索化二叉樹");
threadTree.inThreadList(threadTree.getRoot()); // 中序遍歷線索化二叉樹
}
}
運行結(jié)果：
6、總結(jié)
由于它充分利用了空指針域的空間（等于節(jié)省了空間）躺同，又保證了創(chuàng)建時的一次遍歷就可以終生受用前驅(qū)阁猜、后繼的信息（這意味著節(jié)省了時間），所以在實際問題中蹋艺，如果所使用的二叉樹需要經(jīng)常遍歷或查找節(jié)點時需要某種遍歷中的前驅(qū)和后繼剃袍，那么采用線索二叉鏈表的存儲結(jié)構(gòu)就是不錯的選擇。
