() 在後序線索二叉樹中查找指定結點*p的後序前趨結點
在後序線索二叉樹中查找指定結點*p的後序前趨結點的具體規律是
① 若*p的左子樹為空則p>lchild是前趨線索指示其後序前趨結點
【例】在下圖所示的後序線索二叉樹中H的後序前趨是BF的後序前趨是C
② 若*p的左子樹非空則p>lchild不是前趨線索由於後序遍歷時根是在遍歷其左右子樹之後被訪問的故*p的後序前趨
必是兩子樹中最後一個遍歷結點
當*p的右子樹非空時*p的右孩子必是其後序前趨
【例】在上圖所示的後序線索二叉樹中A的後序前趨是E;
當*p無右子樹時*p的後序前趨必是其左孩子
【例】在上圖所示的後序線索二叉樹中E的後序前趨是F
() 在後序線索二叉樹中查找指定結點*p的後序後繼結點
具體的規律
① 若*p是根則*p是該二叉樹後序遍歷過程中最後一個訪問到的結點*p的後序後繼為空
② 若*p是其雙親的右孩子則*p的後序後繼結點就是其雙親結點
【例】上圖所示的後序線索二叉樹中E的後序後繼是A
③ 若*p是其雙親的左孩子但*P無右兄弟*p的後序後繼結點是其雙親結點
【例】上圖所示的後序線索二叉樹中F的後序後繼是E
④ 若*p是其雙親的左孩子但*p有右兄弟則*p的後序後繼是其雙親的右子樹中第一個後序遍歷到的結點它是該子樹中最
左下的葉結點
【例】上圖所示的後序線索二叉樹中B的後序後繼是雙親A的右子樹中最左下的葉結點H
注意
F是孩子樹中最左下結點但它不是葉子
由上述討論中可知在後序線索樹中僅從*p出發就能找到其後序前趨結點;要找*p的後序後繼結點僅當*p的右子樹為空時
才能直接由*p的右線索p>rchild得到否則必須知道*p的雙親結點才能找到其後序後繼因此如果線索二叉樹中的結點沒有指
向其雙親結點的指針就可能要從根開始進行後序遍歷才能找到結點*P的後序後繼由此線索對查找指定結點的後序後繼並無多大
幫助
() 在前序線索二叉樹中查找指定結點*p的前序後繼結點
【參見練習】
() 在前序線索二叉樹中查找指定結點*p的前序前趨結點
【參見參考書】
在前序線索二叉樹中找某一點*p的前序後繼也很簡單僅從*p出發就可以找到;但找其前序前趨也必須知道*p的雙親結點
當樹中結點未設雙親指針時同樣要進行從根開始的前序遍歷才能找到結點*p的前序前趨
遍歷線索二叉樹
遍歷某種次序的線索二叉樹只要從該次序下的開始結點開發反復找到結點在該次序下的後繼直至終端結點
遍歷中序線索二叉樹算法
void TraverseInorderThrTree(BinThrTree p)
{ //遍歷中序線索二叉樹
if(p){//樹非空
while(p>ltag==Link)
p=p>lchild; //從根往下找最左下結點即中序序列的開始結點
do{
printf(%cp>data); //訪問結點
p=InorderSuccessor(p); //找*p的中序後繼
}while(p)
}//endif
}//TraverselnorderThrTree
分析
① 中序序列的終端結點的右線索為空所以do語句的終止條件是p==NULL
② 該算法的時間復雜性為O(n)因為是非遞歸算法常數因子上小於遞歸的遍歷算法因此若對一棵二叉樹要經常遍歷或
查找結點在指定次序下的前趨和後繼則應采用線索鏈表作為存儲結構為宜
③ 以上介紹的線索二叉樹是一種全線索樹(即左右線索均要建立)許多應用中只要建立左右線索中的一種
④ 若在線索鏈表中增加一個頭結點令頭結點的左指針指向根右指針指向其遍歷序列的開始或終端結點會更方便
From:http://tw.wingwit.com/Article/program/sjjg/201311/23874.html
