一、 概念

二叉樹按照先序昌阿、中序饥脑、后續(xù)遍歷的方法形成一個線性序列后恳邀，每個結(jié)點（除第一個和最后一個外），都有且僅有一個直接前驅(qū)和直接后繼灶轰。但是谣沸，當(dāng)二叉鏈表作為存儲結(jié)構(gòu)時，只能找到結(jié)點的左右孩子的信息笋颤，而不能直接得到結(jié)點在任一序列中的前驅(qū)和后繼信息乳附，這個信息只在遍歷的過程中才能得到。因此引入線索二叉樹來保存這些在遍歷過程中得到的前驅(qū)和后繼的信息伴澄。

雖然可以在每個結(jié)點中增加兩個指針域來存放在遍歷時得到的有關(guān)前驅(qū)和后繼信息赋除，但這樣做使得存儲密度大大降低。由于有n個結(jié)點的二叉鏈表中必定存在n+1個空鏈域非凌，因此可以充分利用這些空鏈域來存放結(jié)點的前驅(qū)和后繼信息贤重。

Tip：
證明：n個結(jié)點的二叉鏈表中必定存在n+1個空鏈域
含有n個結(jié)點的二叉鏈表中，每個結(jié)點都有兩個鏈域清焕，因此一共有2n個鏈域并蝗。
除了根結(jié)點以外的每個點都有一個父結(jié)點，所以一共有n-1結(jié)點需要使用一個鏈域來指向父結(jié)點秸妥。
所以一共有2n-(n-1)=n+1個鏈域是空的滚停。

為此做如下規(guī)定：當(dāng)結(jié)點的左指針為空（即無左子樹）時，令該指針指向該結(jié)點的前驅(qū)結(jié)點粥惧；當(dāng)結(jié)點的右指針為空（即無右子樹）時键畴，令該指針指向該結(jié)點的后繼結(jié)點；為了避免混淆突雪，還需要增加兩個標(biāo)志位來區(qū)分指針指向的是其孩子還是前驅(qū)及后繼起惕。

image.png

typedef struct BiThrNode  
{  
   TelemTpye data;  
   struct BiThrNode *lchild,*rchild;      /*左右孩子指針*/  
   int LTag,RTag;               /*左右標(biāo)志*/  
} BiThrNode,*BiThrTree; 

以這種結(jié)點結(jié)構(gòu)構(gòu)成的二叉鏈表作為二叉樹的存儲結(jié)構(gòu)，叫做線索鏈表咏删，其中指向結(jié)點前驅(qū)和后繼的指針叫做線索惹想。加上線索的二叉樹稱之為線索二叉樹。

對二叉樹以某種次序遍歷使其變成線索二叉樹的過程叫做線索化督函。

二嘀粱、建立線索二叉樹

線索化的過程就是遍歷二叉樹的過程。在遍歷的過程中辰狡，檢查當(dāng)前結(jié)點的左锋叨、右指針域是否為空，若為空宛篇，將它們改為指向前驅(qū)結(jié)點或后繼結(jié)點的線索娃磺。

二叉樹的中序序列a+b*c-d-e/f，形成的中序線索鏈表叫倍，如下圖所示：

image.png

以結(jié)點為根的中序線索化算法：

void InThreading(BiThrTree p) {  
    //pre是全局變量偷卧，初始化時其右孩子指針為空嘿般，便于在樹的最左點開始建線索
    if (p) {  
        InThreading(p->lchild);            /*左子樹遞歸線索化*/  
        if(!p->lchild) {                      /*p的左孩子為空*/  
            p->LTag=1;                     /*給p加上左線索*/  
            p->lchild=pre;                 /*p的左孩子指針指向pre(前驅(qū))*/  
        }  
        else {  
            p->LTag=0;  
        }  
        if(!pre->rchild) {                  /*pre的右孩子為空*/  
            pre->RTag=1;                  /*給pre加上右線索*/  
            pre->rchild=p;                /*pre的右孩子指針指向p(后繼)*/  
        }  
        else {
            pre->RTag=0;  
        }  
        pre=p;                            /*保持pre指向p的前驅(qū)*/  
        InThreading(p->rchild);           /*右子樹遞歸線索化*/  
     }  
}  

三、遍歷線索二叉樹

由于有了結(jié)點的前驅(qū)和后繼信息涯冠，線索二叉樹的遍歷和在指定次序下查找結(jié)點的前驅(qū)和后繼算法都變得簡單。因此逼庞，若需經(jīng)常查找結(jié)點的前驅(qū)和后繼蛇更，就可以采用線索鏈表作為存儲結(jié)構(gòu)。

1赛糟、 在中序線索二叉樹中查找
A派任、 查找p指針?biāo)附Y(jié)點的前驅(qū)：
若p->LTag = 1，則p的左鏈指示其前驅(qū)（/ 的前驅(qū)是e）
若p->LTag = 0璧南，則說明p有左子樹掌逛，結(jié)點的前驅(qū)是遍歷左子樹時最后訪問的一個結(jié)點（* 的前驅(qū)是b）
B、 查找p指針?biāo)附Y(jié)點的后繼：
若p->RTag = 1司倚，則p的右鏈指示其后繼豆混。（b的后繼為）
若p->RTag = 0，則說明p有右子樹动知。結(jié)點的后繼應(yīng)是遍歷其右子樹時訪問的第一個結(jié)點皿伺，即右子樹中最左下的結(jié)點。（查找的后繼時盒粮，首先沿右指針找到其右子樹的根結(jié)點-鸵鸥，然后順其左指針往下直至其左標(biāo)志為1的結(jié)點，即為結(jié)點*的后繼丹皱，是結(jié)點c妒穴。）

2、 在先序線索二叉樹中查找（以下圖為例：先序遍歷為1 2 4 8 9 5 10 11 3 6 12 7）
A摊崭、 查找p指針?biāo)附Y(jié)點的前驅(qū)：
若p->LTag = 0讼油，則說明p有左子樹，此時p的前驅(qū)有兩種情況：若p是其雙親的左孩子呢簸，則其前驅(qū)為其雙親結(jié)點（4結(jié)點汁讼，因為有左孩子8，所以p->LTag = 0阔墩，而4又是雙親2的左孩子嘿架，所以4的前驅(qū)是其雙親2），否則應(yīng)是其雙親的左子樹上先序遍歷最后訪問到的結(jié)點（5結(jié)點啸箫，因為有左孩子10耸彪，所以p->LTag = 0，而5又是其雙親2的右孩子忘苛，所以他的前驅(qū)為雙親2的左子樹先序遍歷最后訪問的結(jié)點9）
B蝉娜、 查找p指針?biāo)附Y(jié)點的后繼：
若p->RTag = 0唱较，則說明p有右子樹， p的后繼必為其左子樹根(若存在)或右子樹根召川。（2結(jié)點有右子樹南缓，所以p->RTag = 0，而2又有左子樹荧呐，所以2的后繼為左子樹的根4汉形，如果沒有6,12這兩個結(jié)點，3結(jié)點有右子樹倍阐，所以p->RTag = 0概疆，但3沒有左子樹，所以3的后繼為右子樹的根7）

image.png

3峰搪、 在后序線索二叉樹中查找 （以上圖為例：后序遍歷為8 9 4 10 11 5 2 12 6 7 3 1）
A岔冀、 查找p指針?biāo)附Y(jié)點的前驅(qū)：
若p->LTag = 0，當(dāng)p->RTag也為0時概耻，則p的右鏈指示其前驅(qū)（結(jié)點4有左右兩個孩子使套，因此p->LTag = 0， p->RTag = 0鞠柄，4的前驅(qū)為右鏈9）童漩；若p->LTag=0，而p->RTag=1春锋，則p的左鏈指示其前驅(qū)（結(jié)點6只有左孩子矫膨，因此p->LTag = 0， p->RTag = 1期奔，6的前驅(qū)為左鏈12）侧馅。
B、 查找p指針?biāo)附Y(jié)點的后繼情況比較復(fù)雜呐萌，分以下情況討論：
以下圖為例：后序遍歷為：A B C D E F G H
若p是二叉樹的根馁痴，則后繼為空。
若p是其雙親的右孩子肺孤，則后繼為雙親結(jié)點罗晕。（B的后繼為C，結(jié)點C的后繼為D）
若p是其雙親的左孩子赠堵，且p沒有右兄弟小渊，則其后繼為雙親結(jié)點。（結(jié)點F的后繼為G）
若p是其雙親的左孩子茫叭，且p有右兄弟酬屉，則其后繼為雙親的右子樹上按后序遍歷列出的第一個結(jié)點(即右子樹中“最左下”的葉結(jié)點) 。（結(jié)點D的后繼為E）

image.png