您當(dāng)前位置：首頁 > 數(shù)據(jù)庫 > 數(shù)據(jù)庫應(yīng)用 > 數(shù)據(jù)結(jié)構(gòu) - 線索二叉樹

數(shù)據(jù)結(jié)構(gòu) - 線索二叉樹

來源：程序員人生發(fā)布時間：2015-08-14 08:38:14 閱讀次數(shù)：6160次

線索樹

  遍歷2叉樹是按1定的規(guī)則將樹中的結(jié)點(diǎn)排列成1個線性序列，即是對非線性結(jié)構(gòu)的線性化操作。

如何找到遍歷進(jìn)程中動態(tài)得到的每一個結(jié)點(diǎn)的直接先驅(qū)和直接后繼(第1個和最后1個除外)?如何保存這些信息?

問：1棵有n個結(jié)點(diǎn)的2叉樹，有多少個空閑指針域未用？

    若1棵2叉樹有n個結(jié)點(diǎn)，則有n⑴條指針連線 ， 而n個結(jié)點(diǎn)共有2n個指針域(Lchild和Rchild) ，所以有n+1個空閑指針域未用。
可以利用這些空閑的指針域來寄存結(jié)點(diǎn)的直接先驅(qū)和直接后繼信息。

對結(jié)點(diǎn)的指針域做以下規(guī)定：
◆ 若結(jié)點(diǎn)有左孩子，則Lchild指向其左孩子，否則，指向其直接先驅(qū)；
◆ 若結(jié)點(diǎn)有右孩子，則Rchild指向其右孩子，否則，指向其直接后繼；

線索2叉樹的結(jié)點(diǎn)結(jié)構(gòu)

用這類結(jié)點(diǎn)結(jié)構(gòu)構(gòu)成的2叉樹存儲結(jié)構(gòu)；叫做線索鏈表；指向結(jié)點(diǎn)先驅(qū)和后繼的指針叫做線索；依照某種次序遍歷，加上線索的2叉樹稱之為線索2叉樹。

線索2叉樹的結(jié)點(diǎn)結(jié)構(gòu)與示例
typedef struct BiTreeNode
{   ElemType  data;
struct BiTreeNode *Lchild , *Rchild ; 
int  Ltag , Rtag ;
}BiThrNode ;

如何在線索樹中找結(jié)點(diǎn)的直接后繼?以圖 ，所示的中序線索樹為例：

這里寫圖片描述

◆ 若樹中結(jié)點(diǎn)的右鏈?zhǔn)蔷€索（Rtag=1），則右鏈直接唆使了結(jié)點(diǎn)的直接后繼，如結(jié)點(diǎn)G的直接后繼是結(jié)點(diǎn)E。
◆ 若樹中結(jié)點(diǎn)的右鏈?zhǔn)侵羔槪?Rtag=0）。根據(jù)中序遍歷的規(guī)律， Rtag=0的結(jié)點(diǎn)的直接后繼是遍歷其右子樹時訪問的第1個結(jié)點(diǎn)，即右子樹中最左下位置的(葉子)結(jié)點(diǎn)。如結(jié)點(diǎn)C的直接后繼：沿右指針找到右子樹的根結(jié)點(diǎn)F，然后沿左鏈往下直到Ltag=1的結(jié)點(diǎn)即為C的直接后繼結(jié)點(diǎn)H。

后序遍歷線索樹

在后序遍歷的線索樹中找結(jié)點(diǎn)的直接后繼比較復(fù)雜，可分以下3種情況：

若結(jié)點(diǎn)是2叉樹的根結(jié)點(diǎn)：其直接后繼為空；
若結(jié)點(diǎn)是其父結(jié)點(diǎn)的左孩子且其父結(jié)點(diǎn)沒有右子樹：直接后繼為其父結(jié)點(diǎn)；
若結(jié)點(diǎn)是其父結(jié)點(diǎn)的左孩子且其父結(jié)點(diǎn)有右子樹：直接后繼是對其父結(jié)點(diǎn)的右子樹按后序遍歷的第1個結(jié)點(diǎn)。

線索化2叉樹

2叉樹的線索化指的是依照某種遍歷次序使2叉樹成為線索2叉樹的進(jìn)程。

線索化的進(jìn)程就是在遍歷進(jìn)程中修改空指針使其指向直接先驅(qū)或直接后繼的進(jìn)程。
   下面主要討論按中序遍歷次序線索化2叉樹。
   仿照線性表的存儲結(jié)構(gòu)，在2叉樹的線索鏈表上也添加1個頭結(jié)點(diǎn)head，頭結(jié)點(diǎn)的指針域的安排是：

◆ Lchild域：指向2叉樹的根結(jié)點(diǎn)；
◆ Rchild域：指向中序遍用時的最后1個結(jié)點(diǎn)；
◆ 2叉樹中序序列中的第1個結(jié)點(diǎn)Lchild指針域和最后1個結(jié)點(diǎn)Rchild指針域均指向頭結(jié)點(diǎn)head。

  添加了頭結(jié)點(diǎn)的線索2叉樹，猶如為2叉樹建立了1個雙向線索鏈表，對1棵線索2叉樹既可從頭結(jié)點(diǎn)也可從最后1個結(jié)點(diǎn)開始按尋覓直接后繼進(jìn)行遍歷。明顯，這類遍歷不需要堆棧。

#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;

按先序序列構(gòu)造2叉線索樹

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; /* 生成根結(jié)點(diǎn)(前序) */
        CreateBiThrTree(&(*T)->lchild); /* 遞歸構(gòu)造左子樹 */
        if((*T)->lchild)    (*T)->LTag=Link; /* 有左孩子 */
        CreateBiThrTree(&(*T)->rchild); /* 遞歸構(gòu)造右子樹 */
        if((*T)->rchild)   (*T)->RTag=Link; /* 有右孩子 */
    }
    return OK;
}

中序遍歷線索化的遞歸函數(shù)

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

先驅(qū)結(jié)點(diǎn)的線索化：if(!T->lchild)表示如果某結(jié)點(diǎn)的左指針域?yàn)榭眨捎谄湎闰?qū)結(jié)點(diǎn)剛剛訪問過，賦值給了pre，所以可將pre賦值給T->lchild，并修改T->LTag=Thread（即定義為1）以完成先驅(qū)結(jié)點(diǎn)的線索化；

后繼結(jié)點(diǎn)的線索化：因此時后繼結(jié)點(diǎn)還沒有訪問到，因此只能對它的先驅(qū)結(jié)點(diǎn)pre的右指針rchild做判斷， if(!pre->rchild)表示如果先驅(qū)的右指針域?yàn)榭眨瑒tT就是pre的后繼，因而pre->rchild=T，并且設(shè)置pre->RTag=Thread，完成后繼結(jié)點(diǎn)的線索化。

完成先驅(qū)和后繼的判斷后，要將當(dāng)前結(jié)點(diǎn)T賦值給pre，以便于下次使用。

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

線索2叉樹遍歷

    線索2叉樹的創(chuàng)建雖然比較復(fù)雜，但在線索2叉樹中，由于有線索存在，在某些情況下可以方便地找到指定結(jié)點(diǎn)在某種遍歷序列中的直接先驅(qū)或直接后繼。

   另外，在線索2叉樹上進(jìn)行某種遍歷比在1般的2叉樹上進(jìn)行這類遍歷要容易很多，不需要設(shè)置堆棧，且算法10分簡潔。

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