線索二叉樹的運算

線索二叉樹的運算

． 查找某結點*p在指定次序下的前趨和後繼結點
（）在中序線索二叉樹中查找結點*p的中序後繼結點
　　在中序線索二叉樹中查找結點*p的中序後繼結點分兩種情形
　　① 若*p的右子樹空(即p>rtag為Thread)則p>rchild為右線索直接指向*p的中序後繼
　　【例】下圖的中序線索二叉樹中結點D的中序後繼是A
       
　　② 若*p的右子樹非空(即p>rtag為Link)則*p的中序後繼必是其右子樹中第一個中序遍歷到的結點也就是從*p的右孩子開始沿該孩子的左鏈往下查找直至找到一個沒有左孩子的結點為止該結點是*p的右子樹中最左下的結點即*P的中序後繼結點
　　【例】上圖的中序線索二叉樹中
　　　A的中序後繼是F它有右孩子
　　　F的中序後繼是H它無右孩子
　　　B的中序後繼是D它是B的右孩子  
　　在中序線索二叉樹中求中序後繼結點的過程可【參見動畫演示】具體算法如下
　　BinThrNode *InorderSuccessor(BinThrNode *p)
      {//在中序線索樹中找結點*p的中序後繼設p非空
         BinThrNode *q
         if (p>rtag==Thread) //*p的右子樹為空
               Return p>rchild //返回右線索所指的中序後繼
         else{
               q=p>rchild //從*p的右孩子開始查找
               while (q>ltag==Link)
                    q=q>lchild //左子樹非空時沿左鏈往下查找
               return q //當q的左子樹為空時它就是最左下結點
             } //end if
      }
    該算法的時間復雜度不超過樹的高度h即O(h)

（）在中序線索二叉樹中查找結點*p的中序前趨結點
　　中序是一種對稱序故在中序線索二叉樹中查找結點*p的中序前趨結點與找中序後繼結點的方法完全對稱具體情形如下
　　① 若*p的左子樹為空則p>child為左線索直接指向*p的中序前趨結點
　　【例】上圖所示的中序線索二叉樹中F結點的中序前趨結點是A
　　② 若*p的左子樹非空則從*p的左孩子出發沿右指針鏈往下查找直到找到一個沒有右孩子的結點為止該結點是*p的左子樹中最右下的結點它是*p的左子樹中最後一個中序遍歷到的結點即*p的中序前趨結點
　　【例】上圖所示中序線索二叉樹中結點E左子樹非空其中序前趨結點是I
　　在中序線索二叉樹中求中序前趨結點的過程可【參見動畫演示】具體算法如下
    BinThrNode *Inorderpre(BinThrNode *p)
      {//在中序線索樹中找結點*p的中序前趨設p非空
         BinThrNode *q
        if (p>ltag==Thread) //*p的左子樹為空
               return p>lchild //返回左線索所指的中序前趨
         else{
               q=p>lchild //從*p的左孩子開始查找
               while (q>rtag==Link)
                    q=q>rchild //右子樹非空時沿右鏈往下查找
               return q //當q的右子樹為空時它就是最右下結點
             } //end if
      }
　　由上述討論可知對於非線索二叉樹僅從*p出發無法找到其中序前趨(或中序後繼)而必須從根結點開始中序遍歷才能找到*p的中序前趨(或中序後繼)線索二叉樹中的線索使得查找中序前趨和中序後繼變得簡單有效

（） 在後序線索二叉樹中查找指定結點*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/22667.html