今天刷題的時(shí)候發(fā)現(xiàn)結(jié)構(gòu)算法1800上的題關(guān)于線索二叉樹(shù)的沒(méi)有考很深，但是如果對(duì)整個(gè)基礎(chǔ)算法沒(méi)有很好地把握的話做題還是有幾個(gè)點(diǎn)有點(diǎn)疑惑，于是把整個(gè)完整線索化整理了一下刹衫，包括前中后序的差別，以中序?yàn)槔ó吘惯f歸只是換換執(zhí)行順序）脾歧，把過(guò)程整個(gè)推了一遍終于把遞歸的邏輯理通了讨便。
線索化的本質(zhì)是把非線性結(jié)構(gòu)變成線性結(jié)構(gòu)充甚，利用二叉鏈表的空鏈域存放指向直接前驅(qū)和后繼的指針。
熟悉了這個(gè)結(jié)構(gòu)以后解決對(duì)應(yīng)得問(wèn)題也變得很輕松了
幾個(gè)經(jīng)典問(wèn)題：關(guān)于某結(jié)點(diǎn)的前驅(qū)后繼問(wèn)題霸褒，空的鏈域有幾個(gè)伴找，線索數(shù)，類似后序非遞歸遍歷的废菱，后序線索樹(shù)的遍歷仍需要棧的支持技矮，聯(lián)考還考過(guò)符合后續(xù)線索樹(shù)定義的圖像，如果對(duì)過(guò)程很熟悉可以用來(lái)驗(yàn)證答案殊轴。
需要注意的是后序線索二叉樹(shù)不能有效解決求后續(xù)后繼的問(wèn)題衰倦，仍應(yīng)按常規(guī)辦法尋找。
存儲(chǔ)結(jié)構(gòu)
typedef struct ThreadNode{
int data;//數(shù)據(jù)
struct ThreadNode *lchild,rchild;
int ltag, rtag;
}ThreadNode, *ThreadTree;
其中引入了標(biāo)志域：
Ltag 為0表示lchild域指向左孩子
Ltag 為1表示lchild域指向直接前驅(qū)
Rtag 為0表示rchild域指向右孩子
Rtag 為1表示rchild域指向直接后繼
void InThread(ThreadTree &p, ThreadTree &pre)
{
//inorder so we start from left tree :)
if(p!=NULL)
{
InThread(p->lchild, pre);
//when first iterator pre =null
if(p->lchild == NULL){
p->lchild = pre;
p->ltag = 1;
}
if(pre!=NULL && pre->rchild == NULL){
pre->rchild = p;
pre->rtag = 1;
}
pre = p;
InThread(p->rchild, pre);
//Then we finished right side
}
}
遞歸的算法看起來(lái)很簡(jiǎn)單但是如果真的走一遍還是會(huì)發(fā)現(xiàn)很多問(wèn)題的旁理，所以畫了個(gè)圖
讓我們進(jìn)入第一次迭代樊零，遞歸的執(zhí)行左移的操作，此時(shí)pre始終為空孽文，終于我們來(lái)到了最左邊的結(jié)點(diǎn)~
最左結(jié)點(diǎn)的lchild肯定為空啦驻襟，所以將他的前驅(qū)lchild設(shè)為pre，但此時(shí)pre為NULL芋哭，于是lchild域置空塑悼，ltag為1，標(biāo)記它是一條線索楷掉。
而此時(shí)pre為NULL跳過(guò)第二段判定厢蒜，令pre = p
進(jìn)入當(dāng)前循環(huán)的右子樹(shù)部分，p右移到最右烹植，此時(shí)的p左子樹(shù)為空斑鸦，pre指向我們剛才搞完的B結(jié)點(diǎn)，所以把p的直接前驅(qū)=pre所指結(jié)點(diǎn)草雕，pre !=null 但 pre的rchild != null所以pre 指向 D結(jié)點(diǎn) 結(jié)束
此時(shí)第一次迭代中的第一條語(yǔ)句才執(zhí)行完巷屿，p仍指向root
其lchild不為空，但此時(shí)pre墩虹！=null && pre->rchild == null了
于是我們將pre所指向結(jié)點(diǎn)的rchild指向當(dāng)前的p嘱巾，
繼續(xù)pre = p，并開(kāi)始遞歸線索化右子樹(shù)诫钓！
p右移到最右結(jié)點(diǎn)（這圖好簡(jiǎn)單）旬昭，先進(jìn)入到他的最左結(jié)點(diǎn)，此時(shí)pre仍在根節(jié)點(diǎn)哦菌湃，因?yàn)楫?dāng)前結(jié)點(diǎn)沒(méi)有l(wèi)child问拘，所以前驅(qū)設(shè)為pre指向結(jié)點(diǎn)，即根節(jié)點(diǎn)，然后pre就可以名正言順的指向E結(jié)點(diǎn)了
此時(shí)C結(jié)點(diǎn)的左子樹(shù)結(jié)束
lchild不為空跳過(guò)骤坐，此時(shí)pre绪杏！=null && rchild == null，pre->rchild = p; pre 指向C結(jié)點(diǎn)纽绍，因?yàn)镃無(wú)右子樹(shù)蕾久，這個(gè)時(shí)候A結(jié)點(diǎn)的右子樹(shù)也結(jié)束了。
再執(zhí)行完整個(gè)InThread之后拌夏，我們應(yīng)把pre指向結(jié)點(diǎn)的后繼置空腔彰，表示整個(gè)線索的結(jié)束。
