二叉樹前驅(qū)后繼的查找

1、線索二叉樹的運算1査找某結(jié)點*p在指定次序下的前趨和后繼結(jié)點（1）在中序線索二叉樹中，查找結(jié)點*卩的中序后繼結(jié)點在中序線索二叉樹中，查找結(jié)點*p的中序后繼結(jié)點分兩種情形：若*p的右子樹空（即p-rtag為Thread），則p-rchild為右線索，直接指向*p的中序后繼?！纠肯聢D的中序線索二叉樹中，結(jié)點D的中序后繼是A。AI-：M.LL000o0（心中序戰(zhàn)盍二義郴【例】下圖的中序線索二叉樹中，結(jié)點D的中序后繼是A。AI-：M.LL000o0（心中序戰(zhàn)盍二義郴屮序線索二冥樹及叭有儲嵇構(gòu)M/LL0 E0/匚11H1若*p的右子樹非空（即p-rtag為Link），則*卩的中序后繼必是其右子樹中第一

2、個中序 遍歷到的結(jié)點。也就是從*p的右孩子開始，沿該孩子的左鏈往下查找，直至找到一個沒有 左孩子的結(jié)點為止，該結(jié)點是*p的右子樹中最左下的結(jié)點，即*P的中序后繼結(jié)點?！纠可蠄D的中序線索二叉樹中：A的中序后繼是F,它有右孩子;F 的中序后繼是 H ，它無右孩子；B 的中序后繼是 D ，它是 B 的右孩子。在中序線索二叉樹中求中序后繼結(jié)點的過程可【參見動畫演示】，具體算法如下：BinThrNode *InorderSuccessor(BinThrNode *p)/在中序線索樹中找結(jié)點*卩的中序后繼，設(shè)p非空BinThrNode *q；if (p-rtag=Thread) *p 的右子樹為空Ret

3、urn p-rchild； /返回右線索所指的中序后繼elseq=p-rchild；/從*p的右孩子開始查找while (q-ltag=Link)q=q-lchild； /左子樹非空時，沿左鏈往下查找return q；/當(dāng) q 的左子樹為空時，它就是最左下結(jié)點 /end if該算法的時間復(fù)雜度不超過樹的高度h,即0(h)。在中序線索二叉樹中查找結(jié)點*卩的中序前趨結(jié)點中序是一種對稱序，故在中序線索二叉樹中查找結(jié)點*p的中序前趨結(jié)點與找中序后繼 結(jié)點的方法完全對稱。具體情形如下：若*p的左子樹為空，則p-lchild為左線索，直接指向*p的中序前趨結(jié)點；【例】上圖所示的中序線索二叉樹中，F(xiàn)結(jié)點的中

4、序前趨結(jié)點是A若*p的左子樹非空，則從*p的左孩子出發(fā)，沿右指針鏈往下查找，直到找到一個沒 有右孩子的結(jié)點為止。該結(jié)點是*p的左子樹中最右下的結(jié)點，它是*p的左子樹中最后一 個中序遍歷到的結(jié)點，即*p的中序前趨結(jié)點。【例】上圖所示中序線索二叉樹中，結(jié)點E左子樹非空，其中序前趨結(jié)點是I 在中序線索二叉樹中求中序前趨結(jié)點的過程可【參見動畫演示】，具體算法如下：BinThrNode *Inorderpre(BinThrNode *p)/在中序線索樹中找結(jié)點*卩的中序前趨，設(shè)p非空BinThrNode *q；if (p-ltag=Thread) *p 的左子樹為空return p-lchild； /返

5、回左線索所指的中序前趨elseq=p-lchild；從*p的左孩子開始查找while (q-rtag=Link)q=q-rchild；/右子樹非空時，沿右鏈往下查找return q； /當(dāng) q 的右子樹為空時，它就是最右下結(jié)點 /end if由上述討論可知：對于非線索二叉樹，僅從*p出發(fā)無法找到其中序前趨(或中序后繼)， 而必須從根結(jié)點開始中序遍歷，才能找到*卩的中序前趨(或中序后繼)。線索二叉樹中的線索 使得查找中序前趨和中序后繼變得簡單有效。在后序線索二叉樹中，查找指定結(jié)點*卩的后序前趨結(jié)點在后序線索二叉樹中，查找指定結(jié)點*卩的后序前趨結(jié)點的具體規(guī)律是：若*p的左子樹為空，則p-lchil

6、d是前趨線索，指示其后序前趨結(jié)點?！纠吭谙聢D所示的后序線索二叉樹中，H的后序前趨是B， F的后序前趨是C。BEFDGH需序線窘二艾樹NULL若BEFDGH需序線窘二艾樹NULL若*p的左子樹非空，則p-lchild不是前趨線索。由于后序遍歷時，根是在遍歷其左右子樹之后被訪問的，故*p的后序前趨必是兩子樹中最后一個遍歷結(jié)點。當(dāng)*卩的右子樹非空時，*p的右孩子必是其后序前趨【例】在上圖所示的后序線索二叉樹中，A的后序前趨是E；當(dāng)*卩無右子樹時，*p的后序前趨必是其左孩子【例】在上圖所示的后序線索二叉樹中，E的后序前趨是F在后序線索二叉樹中，查找指定結(jié)點*卩的后序后繼結(jié)點具體的規(guī)律：若*p是根，則

7、*p是該二叉樹后序遍歷過程中最后一個訪問到的結(jié)點。*p的后序后繼 為空若*p是其雙親的右孩子，則*p的后序后繼結(jié)點就是其雙親結(jié)點【例】上圖所示的后序線索二叉樹中，E的后序后繼是A。若*p是其雙親的左孩子，但*P無右兄弟，*卩的后序后繼結(jié)點是其雙親結(jié)點【例】上圖所示的后序線索二叉樹中，F(xiàn)的后序后繼是E。若*p是其雙親的左孩子，但*p有右兄弟，則*卩的后序后繼是其雙親的右子樹中第一 個后序遍歷到的結(jié)點，它是該子樹中最左下的葉結(jié)點【例】上圖所示的后序線索二叉樹中，B的后序后繼是雙親A的右子樹中最左下的葉 結(jié)點 HF 是孩子樹中最左下結(jié)點，但它不是葉子。由上述討論中可知：在后序線索樹中，僅從*p出發(fā)就能找到其后序前趨結(jié)點；要找*p 的后序后繼結(jié)點，僅當(dāng)*卩的右子樹為空時，才能直接由*卩的右線索p-