數據結構-線索二叉樹

如何在線索樹中找結點的直接後繼?以圖 ，所示的中序線索樹為例：

◆ 若樹中結點的右鏈是線索（Rtag=1），則右鏈直接指示了結點的直接後繼，如結點G的直接後繼是結點E。
◆ 若樹中結點的右鏈是指針（ Rtag=0）。根據中序遍歷的規律， Rtag=0的結點的直接後繼是遍歷其右子樹時訪問的第一個結點，即右子樹中最左下位置的(葉子)結點。如結點C的直接後繼：沿右指針找到右子樹的根結點F，然後沿左鏈往下直到Ltag=1的結點即為C的直接後繼結點H。

後序遍歷線索樹

在後序遍歷的線索樹中找結點的直接後繼比較復雜，可分以下三種情況：

若結點是二叉樹的根結點：其直接後繼為空；
若結點是其父結點的左孩子且其父結點沒有右子樹：直接後繼為其父結點；
若結點是其父結點的左孩子且其父結點有右子樹：直接後繼是對其父結點的右子樹按後序遍歷的第一個結點。

線索化二叉樹

二叉樹的線索化指的是依照某種遍歷次序使二叉樹成為線索二叉樹的過程。

線索化的過程就是在遍歷過程中修改空指針使其指向直接前驅或直接後繼的過程。
   下面主要討論按中序遍歷次序線索化二叉樹。
   仿照線性表的存儲結構，在二叉樹的線索鏈表上也添加一個頭結點head，頭結點的指針域的安排是：

◆ Lchild域：指向二叉樹的根結點；
◆ Rchild域：指向中序遍歷時的最後一個結點；
◆ 二叉樹中序序列中的第一個結點Lchild指針域和最後一個結點Rchild指針域均指向頭結點head。

  添加了頭結點的線索二叉樹，如同為二叉樹建立了一個雙向線索鏈表，對一棵線索二叉樹既可從頭結點也可從最後一個結點開始按尋找直接後繼進行遍歷。顯然，這種遍歷不需要堆棧。

#define  MAX_NODE   50
typedef enmu{ Link , Thread} PointerTag ;
/*  Link=0表示指針， Thread=1表示線索   */
typedef struct BiThrNode
{   ElemType  data;
struct BiTreeNode *Lchild , *Rchild ; 
PointerTag  Ltag , Rtag ;
}BiThrNode, *BiThrTree;

ElemType Nil=‘#’;   /*以#為空 */
Status CreateBiThrTree(BiThrTree *T)
{      ElemType ch;
       scanf("%c",&ch);
    if(h==Nil)  *T=NULL;
    else
    {   *T=(BiThrTree)malloc(sizeof(BiThrNode));
        if(!*T) return ERROR;
        (*T)->data=ch; /* 生成根結點(前序) */
        CreateBiThrTree(&(*T)->lchild); /* 遞歸構造左子樹 */
        if((*T)->lchild)    (*T)->LTag=Link; /* 有左孩子 */
        CreateBiThrTree(&(*T)->rchild); /* 遞歸構造右子樹 */
        if((*T)->rchild)   (*T)->RTag=Link; /* 有右孩子 */
    }
    return OK;
}

BiThrNode *pre//全局變量，始終指向剛剛訪問過的結點
void  InThreading (BiThrNode *T)
{   if(T)
    {  Inorder_Threading(T->lchild) /* 遞歸左子樹線索化 */
    if(!T->lchild) /* 沒有左孩子 */
    {      T->LTag=Thread; /* 前驅線索 */
        T->lchild=pre; /* 左孩子指針指向前驅 */
     }
    if(!pre->rchild) /* 前驅沒有右孩子 */
    {       pre->RTag=Thread; /* 後繼線索 */
         pre->rchild=T; /* 前驅右孩子指針指向後繼(當前結點T) */
      }
      pre=T; /* 保持pre指向T的前驅 */
      Inorder_Threading(T->rchild); /* 遞歸右子樹線索化 */
    }
}

/* 中序遍歷二叉樹T,並將其中序線索化,Thrt指向頭結點 */
Status InOrderThreading(BiThrTree *Thrdhead, BiThrTree T)
{   * Thrdhead =(BiThrTree)malloc(sizeof(BiThrNode));
     if(!* Thrdhead )  return ERROR;
    (* Thrdhead )->LTag=Link; /* 建頭結點 */
    (* Thrdhead )->RTag=Thread;
    (* Thrdhead )->rchild= NULL; //右指針此時為空
    if(!T)   (* Thrdhead )->lchild= * Thrdhead; //若二叉樹空,則左指針回指
    else
    {
        (* Thrdhead )->lchild=T; //非空，指向根節點
        pre=(* Thrdhead );
        InThreading(T); /* 中序遍歷進行中序線索化 */
        pre->rchild=* Thrdhead; //pre是中序遍歷的最後一個結點
        pre->RTag=Thread; /* 最後一個結點線索化 */
        (* Thrdhead )->rchild=pre;
    }
    return OK;
}

    線索二叉樹的創建雖然比較復雜，但在線索二叉樹中，由於有線索存在，在某些情況下可以方便地找到指定結點在某種遍歷序列中的直接前驅或直接後繼。

   此外，在線索二叉樹上進行某種遍歷比在一般的二叉樹上進行這種遍歷要容易得多，不需要設置堆棧，且算法十分簡潔。

/* 中序遍歷二叉線索樹T(頭結點)的非遞歸算法 */
Status InOrderTraverse_Thr(BiThrTree T)
{ 
    BiThrTree p;
    p=T->lchild;   /* p指向根結點 */
    while(p!=T)  /* 空樹或遍歷結束時,p==T */
    {      while(p->LTag==Link)
            p=p->lchild; //當LTag==0時循環到中序序列第一個結點
        visit(p->data);
        while(p->RTag==Thread&&p->rchild!=T)
        {
            p=p->rchild;
            visit(p->data); /* 訪問後繼結點 */
        }
        p=p->rchild;
    }
    return OK;
}