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

2、個中序 遍歷到的結點。也就是從*p的右孩子開始，沿該孩子的左鏈往下查找，直至找到一個沒有 左孩子的結點為止，該結點是*p的右子樹中最左下的結點，即*P的中序后繼結點。【例】上圖的中序線索二叉樹中：A的中序后繼是F,它有右孩子;F 的中序后繼是 H ，它無右孩子；B 的中序后繼是 D ，它是 B 的右孩子。在中序線索二叉樹中求中序后繼結點的過程可【參見動畫演示】，具體算法如下：BinThrNode *InorderSuccessor(BinThrNode *p)/在中序線索樹中找結點*卩的中序后繼，設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；/當 q 的左子樹為空時，它就是最左下結點 /end if該算法的時間復雜度不超過樹的高度h,即0(h)。在中序線索二叉樹中查找結點*卩的中序前趨結點中序是一種對稱序，故在中序線索二叉樹中查找結點*p的中序前趨結點與找中序后繼 結點的方法完全對稱。具體情形如下：若*p的左子樹為空，則p-lchild為左線索，直接指向*p的中序前趨結點；【例】上圖所示的中序線索二叉樹中，F結點的中

4、序前趨結點是A若*p的左子樹非空，則從*p的左孩子出發，沿右指針鏈往下查找，直到找到一個沒 有右孩子的結點為止。該結點是*p的左子樹中最右下的結點，它是*p的左子樹中最后一 個中序遍歷到的結點，即*p的中序前趨結點。【例】上圖所示中序線索二叉樹中，結點E左子樹非空，其中序前趨結點是I 在中序線索二叉樹中求中序前趨結點的過程可【參見動畫演示】，具體算法如下：BinThrNode *Inorderpre(BinThrNode *p)/在中序線索樹中找結點*卩的中序前趨，設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； /當 q 的右子樹為空時，它就是最右下結點 /end if由上述討論可知：對于非線索二叉樹，僅從*p出發無法找到其中序前趨(或中序后繼)， 而必須從根結點開始中序遍歷，才能找到*卩的中序前趨(或中序后繼)。線索二叉樹中的線索 使得查找中序前趨和中序后繼變得簡單有效。在后序線索二叉樹中，查找指定結點*卩的后序前趨結點在后序線索二叉樹中，查找指定結點*卩的后序前趨結點的具體規律是：若*p的左子樹為空，則p-lchil

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

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