數(shù)據(jù)結(jié)構(gòu)與算法--線索二叉樹及其前序、中序遍歷
二叉樹如果某個(gè)結(jié)點(diǎn)沒(méi)有左孩子或右孩子，則這個(gè)域就為空持际。如node.lChild = null沃琅，
而葉子結(jié)點(diǎn)兩個(gè)指針域都是null。我們知道n個(gè)結(jié)點(diǎn)的二叉樹共有2n個(gè)指針域选酗，樹只有n-1條分支阵难，也就是說(shuō)還有2n - (n -1) = n + 1個(gè)域是空指針岳枷。為了充分利用這些空指針芒填，可以存一些有用的信息——比如某結(jié)點(diǎn)的前驅(qū)和后繼結(jié)點(diǎn)（按某種次序遍歷后的順序）。這種指向前序后繼的指針?lè)Q為線索空繁，具有前驅(qū)后繼關(guān)系的二叉樹叫線索二叉樹殿衰。線索二叉樹的好處是：不僅節(jié)約了空間，而且一旦按照某種次序（中序盛泡、前序或后序）遍歷一次后闷祥，線索信息就已經(jīng)初始化好，下次想要獲取某個(gè)結(jié)點(diǎn)的前驅(qū)后繼就不用再遍歷整棵樹了傲诵。
具體來(lái)說(shuō)凯砍，對(duì)于所有空指針域，lChild指向該結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)拴竹；rChild指向該結(jié)點(diǎn)的后繼結(jié)點(diǎn)悟衩。但是lChild和rChild同時(shí)也表示某結(jié)點(diǎn)的左孩子和右孩子，一個(gè)指針有兩種意思栓拜，對(duì)某個(gè)結(jié)點(diǎn)究竟指代的哪種意思座泳？顯然需要一個(gè)標(biāo)志加以區(qū)分，我們給每個(gè)結(jié)點(diǎn)的孩子加上標(biāo)志幕与，如果是false則表示左/右孩子挑势，如果是true則表示前驅(qū)/后繼。這棵二叉樹中序遍歷的結(jié)果是HDIBEAFCG啦鸣，按照遍歷所得順序潮饱，H的后繼就是D，h.rChild本來(lái)是null诫给，現(xiàn)在讓其指向D饼齿，由于這表示后繼，所以相應(yīng)的標(biāo)志位應(yīng)該設(shè)置為true蝙搔。這幅圖將所有rChild為空的指針域都指向了其后繼缕溉。
那么前驅(qū)呢？自然是將所有l(wèi)Child為空的指針域指向該結(jié)點(diǎn)的前驅(qū)吃型。如下圖证鸥。
如果將這兩幅圖結(jié)合起來(lái)，則每個(gè)空指針域都已用上了。這棵二叉樹就成了下面這個(gè)樣子
虛線表示右孩子或者后繼枉层，實(shí)線表示左孩子或者前驅(qū)泉褐，具體怎么區(qū)分也就是看給結(jié)點(diǎn)左右孩子設(shè)置的標(biāo)志位了。仔細(xì)觀察鸟蜡，把這顆樹兩頭拉直膜赃，就成了雙向鏈表！（但又和普通的雙向鏈表不同揉忘，這里前驅(qū)后繼的含義指代比較模糊）
現(xiàn)在來(lái)試著實(shí)現(xiàn)一下跳座。
package Chap6;
public class ThreadTree<Item> {
public static class Node<T> {
private T data;
private Node<T> lchild;
private Node<T> rchild;
private boolean isleftThead;
private boolean isRightThead;
public Node(T data) {
this.data = data;
isleftThead = false;
isRightThead = false;
}
public T getData() {
return data;
}
public Node<T> getLchild() {
return lchild;
}
public Node<T> getRchild() {
return rchild;
}
@Override
public String toString() {
String lchildInfo = lchild == null ? null : lchild.getData().toString();
String rchildInfo = rchild == null ? null : rchild.getData().toString();
return "Node{" +
"data=" + data +
", lchild=" + lchildInfo +
", rchild=" + rchildInfo +
'}';
}
}
private Node<Item> root;
private Node<Item> preNode;
private int nodesNum;
public void setRoot(Item data) {
root = new Node<>(data);
nodesNum++;
}
public void addLeftChild(Item data, Node<Item> parent) {
parent.lchild = new Node<>(data);
nodesNum++;
}
public void addRightChild(Item data, Node<Item> parent) {
parent.rchild = new Node<>(data);
nodesNum++;
}
public Node<Item> root() {
return root;
}
/**
* 中序遍歷線索化二叉樹
*/
public void inOrderThread(Node<Item> node) {
if (node == null) {
return;
}
inOrderThread(node.lchild);
if (node.lchild == null) {
node.lchild = preNode;
node.isleftThead = true;
}
if (preNode != null && preNode.rchild == null) {
preNode.rchild = node;
preNode.isRightThead = true;
}
// preNode始終表示上一個(gè)訪問(wèn)的結(jié)點(diǎn)
preNode = node;
inOrderThread(node.rchild);
}
public void inOrderThread() {
inOrderThread(root);
}
public void inOrderTraversal(Node<Item> node) {
// 不斷深入左子樹,只要某個(gè)結(jié)點(diǎn)左孩子為空，則標(biāo)志位肯定為true
while (node != null) {
while (!node.isleftThead) {
node = node.lchild;
}
System.out.print(node.getData() + " ");
while (node.isRightThead && node.rchild != null) {
node = node.rchild;
System.out.print(node.getData() + " ");
}
node = node.rchild;
}
}
public void inOrderTraversal() {
inOrderTraversal(root);
}
/**
* 前序遍歷線索化二叉樹
*/
public void preOrderThread(Node<Item> node) {
if (node == null) {
return;
}
if (node.lchild == null) {
node.lchild = preNode;
node.isleftThead = true;
}
if (preNode != null && preNode.rchild == null) {
preNode.rchild = node;
preNode.isRightThead = true;
}
// preNode始終表示上一個(gè)訪問(wèn)的結(jié)點(diǎn)
preNode = node;
// 這里需要判斷泣矛，因?yàn)閚ode.lchild和node.rchild可能已經(jīng)被設(shè)置了標(biāo)志疲眷。若還遞歸就會(huì)打亂了已設(shè)置好的標(biāo)志位，而且還會(huì)StackOverflow
// 而中序遍歷遞歸是您朽，標(biāo)志位均未被設(shè)置狂丝，所以無(wú)需判斷
if (!node.isleftThead) {
preOrderThread(node.lchild);
}
if (!node.isRightThead) {
preOrderThread(node.rchild);
}
}
public void preOrderThread() {
preOrderThread(root);
}
public void preOrderTraversal(Node<Item> node) {
while (node != null) {
while (!node.isleftThead) {
System.out.print(node.getData() + " ");
node = node.lchild;
}
System.out.print(node.getData() + " ");
node = node.rchild;
}
}
public void preOrderTraversal() {
preOrderTraversal(root);
}
public static void main(String[] args) {
ThreadTree<String> tree = new ThreadTree<>();
tree.setRoot("A");
Node<String> root = tree.root();
tree.addLeftChild("B", root);
tree.addRightChild("C", root);
tree.addLeftChild("D", root.getLchild());
tree.addLeftChild("E", root.getRchild());
tree.addRightChild("F", root.getRchild());
tree.addLeftChild("G", root.getLchild().getLchild());
tree.addRightChild("H", root.getLchild().getLchild());
tree.addRightChild("I", root.getRchild().getLchild());
System.out.println("中序線索化并遍歷");
tree.inOrderThread();
tree.inOrderTraversal();
// 線索化只能調(diào)用一次！；┳堋几颜！一旦設(shè)置好，就不要去打亂了讯屈。所以想運(yùn)行上面的需要注釋掉下面的
// System.out.println("前序線索化并遍歷");
// tree.preOrderThread();
// tree.preOrderTraversal();
}
}
首先是Node類增加了標(biāo)志位isleftThead和isRightThread蛋哭，含義上面解釋過(guò)了。然后是ThreadTree類除了有個(gè)root成員耻煤，還新增了preNode成員具壮，專門表示在線索化中上一個(gè)剛訪問(wèn)過(guò)的結(jié)點(diǎn)。部分方法直接使用了普通二叉樹的代碼哈蝇。這里著重說(shuō)一下線索化的代碼棺妓。前序和后序線索化及遍歷都比較簡(jiǎn)單，后序復(fù)雜一點(diǎn)我也懶得去實(shí)現(xiàn)了炮赦。
中序線索化及中序遍歷
之所以稱為中序線索化怜跑，是因?yàn)樗推胀ǘ鏄渲行虮闅v的遞歸實(shí)現(xiàn)，代碼結(jié)構(gòu)幾乎一樣吠勘⌒苑遥看單獨(dú)抽取出來(lái)的中序線索化實(shí)現(xiàn)，只要把中序遍歷遞歸實(shí)現(xiàn)中的打印操作換成注釋了begin和end之間的代碼就OK了剧防。
public void inOrderThread(Node<Item> node) {
if (node == null) {
return;
}
inOrderThread(node.lchild);
// begin
if (node.lchild == null) {
node.lchild = preNode;
node.isleftThead = true;
}
if (preNode != null && preNode.rchild == null) {
preNode.rchild = node;
preNode.isRightThead = true;
}
// preNode始終表示上一個(gè)訪問(wèn)的結(jié)點(diǎn)
preNode = node;
// end
inOrderThread(node.rchild);
}
中間的代碼做的事主要是：
- 某結(jié)點(diǎn)的左孩子為空植锉，設(shè)置標(biāo)志位為true，且讓上一個(gè)結(jié)點(diǎn)成為當(dāng)前結(jié)點(diǎn)的前驅(qū)峭拘。
- 某結(jié)點(diǎn)的右孩子為空俊庇，設(shè)置標(biāo)志位為true狮暑，且讓當(dāng)前結(jié)點(diǎn)成為前一個(gè)結(jié)點(diǎn)的后繼。這里因?yàn)橐{(diào)用preNode的方法辉饱，所以要進(jìn)行判空操作搬男。
- 當(dāng)前結(jié)點(diǎn)訪問(wèn)完，即將訪問(wèn)下一個(gè)結(jié)點(diǎn)了彭沼，于是當(dāng)前結(jié)點(diǎn)也就成了上一個(gè)結(jié)點(diǎn)preNode缔逛。
這里設(shè)置某結(jié)點(diǎn)的后繼之所以使用preNode，理由很簡(jiǎn)單姓惑，當(dāng)前結(jié)點(diǎn)的后繼還沒(méi)訪問(wèn)到呢褐奴，只能用已經(jīng)訪問(wèn)過(guò)的前一個(gè)結(jié)點(diǎn)，它的后繼可能是當(dāng)前結(jié)點(diǎn)挺益。
再來(lái)看中序遍歷歉糜。
public void inOrderTraversal(Node<Item> node) {
// 不斷深入左子樹,直到遇見第一個(gè)線索
while (node != null) {
while (!node.isleftThead) {
node = node.lchild;
}
System.out.print(node.getData() + " ");
while (node.isRightThead && node.rchild != null) {
node = node.rchild;
System.out.print(node.getData() + " ");
}
node = node.rchild;
}
}
先是從根結(jié)點(diǎn)開始按照左子樹深入乘寒，直到遇見第一個(gè)左孩子是線索的結(jié)點(diǎn)望众，緊接著就打印它，這次打印的其實(shí)是鏈表頭伞辛。接下來(lái)看它的右孩子是不是后繼烂翰，如果是就繼續(xù)打印蚤氏；直到右孩子不是線索甘耿，此時(shí)轉(zhuǎn)到右子樹，開始和根結(jié)點(diǎn)一樣的循環(huán)...最后一個(gè)while中需要判斷node.rchild不為空竿滨，如果為空佳恬，我們打印出來(lái)就是null，這不是我們想要看得結(jié)果于游。
前序線索化
把設(shè)置標(biāo)志那一團(tuán)代碼放到遞歸左右子樹之前毁葱，就成了前序線索化。特別注意贰剥，在遞歸前判斷了是否為線索結(jié)點(diǎn)倾剿。因?yàn)榍靶蚓€索化中，遞歸發(fā)生在設(shè)置標(biāo)志位之后蚌成，所以node.lchild和node.rchild可能已經(jīng)被設(shè)置了標(biāo)志前痘。若還遞歸就會(huì)打亂了已設(shè)置好的標(biāo)志位，而且還會(huì)發(fā)生StackOverflow担忧。而中序線索化中無(wú)需判斷是因?yàn)榍鄣蓿f歸左子樹發(fā)生在設(shè)置左孩子的線索之前，而右孩子的線索的設(shè)置是針對(duì)上一個(gè)結(jié)點(diǎn)的瓶盛，當(dāng)前結(jié)點(diǎn)的右孩子并沒(méi)有線索化最欠，所以對(duì)當(dāng)前結(jié)點(diǎn)的右子樹node.rchild的遞歸并沒(méi)有影響坡锡。
if (!node.isleftThead) {
preOrderThread(node.lchild);
}
if (!node.isRightThead) {
preOrderThread(node.rchild);
}
接著看前序遍歷的。還是根結(jié)點(diǎn)開始窒所，深入左子樹鹉勒，只要沒(méi)遇到左孩子是線索的結(jié)點(diǎn)，就立即打印吵取。然后跳出while循環(huán)打印第一個(gè)左孩子是線索的結(jié)點(diǎn)禽额。然后轉(zhuǎn)向其后繼或者是右子樹，繼續(xù)大循壞...
如果我們經(jīng)常需要遍歷二叉樹皮官，并且要知道某結(jié)點(diǎn)的前驅(qū)后繼信息脯倒，那么使用線索二叉樹是個(gè)不錯(cuò)的選擇。特別注意一點(diǎn)捺氢，線索化只能執(zhí)行一次藻丢，已經(jīng)設(shè)置好的標(biāo)志信息就不要再設(shè)置第二次了（除非清空標(biāo)志位），否則會(huì)導(dǎo)致標(biāo)志位的混亂摄乒，導(dǎo)致遍歷失敗悠反。
by @sunhaiyu
2017.9.14
