線索二叉樹原理
遍歷二叉樹的其實就是以一定規(guī)則將二叉樹中的結(jié)點排列成一個線性序列，得到二叉樹中結(jié)點的先序序列、中序序列或后序序列。這些線性序列中的每一個元素都有且僅有一個前驅(qū)結(jié)點和后繼結(jié)點。
但是當(dāng)我們希望得到二叉樹中某一個結(jié)點的前驅(qū)或者后繼結(jié)點時，普通的二叉樹是無法直接得到的，只能通過遍歷一次二叉樹得到。每當(dāng)涉及到求解前驅(qū)或者后繼就需要將二叉樹遍歷一次，非常不方便。
于是是否能夠改變原有的結(jié)構(gòu)，將結(jié)點的前驅(qū)和后繼的信息存儲進來。
觀察二叉樹的結(jié)構(gòu)，我們發(fā)現(xiàn)指針域并沒有充分的利用，有很多“NULL”，也就是存在很多空指針。
對于一個有n個結(jié)點的二叉鏈表，每個節(jié)點都有指向左右孩子的兩個指針域，一共有2n個指針域。而n個結(jié)點的二叉樹又有n-1條分支線數(shù)(除了頭結(jié)點，每一條分支都指向一個結(jié)點)，也就是存在2n-(n-1)=n+1個空指針域。這些指針域只是白白的浪費空間。因此, 可以用空鏈域來存放結(jié)點的前驅(qū)和后繼。線索二叉樹就是利用n+1個空鏈域來存放結(jié)點的前驅(qū)和后繼結(jié)點的信息。
如圖以中序二叉樹為例，我們可以把這顆二叉樹中所有空指針域的lchild，改為指向當(dāng)前結(jié)點的前驅(qū)（灰色箭頭），把空指針域中的rchild，改為指向結(jié)點的后繼（綠色箭頭）。我們把指向前驅(qū)和后繼的指針叫做線索 ，加上線索的二叉樹就稱之為線索二叉樹。
線索二叉樹結(jié)點結(jié)構(gòu)
如果只是在原二叉樹的基礎(chǔ)上利用空結(jié)點，那么就存在著這么一個問題：我們?nèi)绾沃滥骋唤Y(jié)點的lchild是指向他的左孩子還是指向前驅(qū)結(jié)點？rchild是指向右孩子還是后繼結(jié)點？顯然我們要對他的指向增設(shè)標志來加以區(qū)分。
因此，我們在每一個結(jié)點都增設(shè)兩個標志域LTag和RTag，它們只存放0或1的布爾型變量，占用的空間很小。于是結(jié)點的結(jié)構(gòu)如圖所示。
其中：
LTag為0是指向該結(jié)點的左孩子，為1時指向該結(jié)點的前驅(qū)
RTag為0是指向該結(jié)點的右孩子，為1時指向該結(jié)點的后繼
因此實際的二叉鏈表圖為
線索二叉樹的結(jié)構(gòu)實現(xiàn)
二叉樹的線索存儲結(jié)構(gòu)定義如下：
typedef char TElemType;
typedef enum { Link, Thread } PointerTag; //Link==0,表示指向左右孩子指針
//Thread==1,表示指向前驅(qū)或后繼的線索
//二叉樹線索結(jié)點存儲結(jié)構(gòu)
typedef struct BiThrNode {
TElemType data; //結(jié)點數(shù)據(jù)
struct BiThrNode *lchild, *rchild; //左右孩子指針
PointerTag LTag;
PointerTag RTag; //左右標志
}BiThrNode, *BiThrTree;
二叉樹線索化
對普通二叉樹以某種次序遍歷使其成為線索二叉樹的過程就叫做線索化。因為前驅(qū)和后繼結(jié)點只有在二叉樹的遍歷過程中才能得到，所以線索化的具體過程就是在二叉樹的遍歷中修改空指針。
線索化具體實現(xiàn)
以中序二叉樹的線索化為例，線索化的具體實現(xiàn)就是將中序二叉樹的遍歷進行修改，把原本打印函數(shù)的代碼改為指針修改的代碼就可以了。
我們設(shè)置一個pre指針，永遠指向遍歷當(dāng)前結(jié)點的前一個結(jié)點。若遍歷的當(dāng)前結(jié)點左指針域為空，也就是無左孩子，則把左孩子的指針指向pre(相對當(dāng)前結(jié)點的前驅(qū)結(jié)點)。
右孩子同樣的，當(dāng)pre的右孩子為空，則把pre右孩子的指針指向當(dāng)前結(jié)點(相對pre結(jié)點為后繼結(jié)點)。
最后把當(dāng)前結(jié)點賦給pre，完成后續(xù)的遞歸遍歷線索化。
中序遍歷線索化的遞歸函數(shù)代碼如下：
void InThreading(BiThrTree B,BiThrTree *pre) {
if(!B) return;
InThreading(B->lchild,pre);
//--------------------中間為修改空指針代碼---------------------
if(!B->lchild){ //沒有左孩子
B->LTag = Thread; //修改標志域為前驅(qū)線索
B->lchild = *pre; //左孩子指向前驅(qū)結(jié)點
}
if(!(*pre)->rchild){ //沒有右孩子
(*pre)->RTag = Thread; //修改標志域為后繼線索
(*pre)->rchild = B; //前驅(qū)右孩子指向當(dāng)前結(jié)點
}
*pre = B; //保持pre指向p的前驅(qū)
//---------------------------------------------------------
InThreading(B->rchild,pre);
}
增設(shè)頭結(jié)點
線索化后的二叉樹，就如同操作一個雙向鏈表。于是我們想到為二叉樹增設(shè)一個頭結(jié)點，這樣就和雙向鏈表一樣，即能夠從第一個結(jié)點正向開始遍歷，也可以從最后一個結(jié)點逆向遍歷。
如上圖，在線索二叉鏈表上添加一個head結(jié)點，并令其lchild域的指針指向二叉樹的根結(jié)點(A)，其rchild域的指針指向中序遍歷訪問的最后一個結(jié)點(G)。同樣地，二叉樹中序序列的第一個結(jié)點中，lchild域指針指向頭結(jié)點，中序序列的最后一個結(jié)點rchild域指針也指向頭結(jié)點。
于是從頭結(jié)點開始，我們既可以從第一個結(jié)點順后繼結(jié)點遍歷，也可以從最后一個結(jié)點起順前驅(qū)遍歷。就和雙鏈表一樣。
增設(shè)頭結(jié)點并線索化的代碼實現(xiàn)
//為線索二叉樹添加頭結(jié)點，使之可以雙向操作
Status InOrderThreading(BiThrTree *Thrt,BiThrTree T){
if(!(*Thrt = (BiThrTree)malloc(sizeof(BiThrNode)))) exit(OVERFLOW); //開辟結(jié)點
(*Thrt)->LTag = Link;
(*Thrt)->RTag = Thread; //設(shè)置標志域
(*Thrt)->rchild = (*Thrt); //右結(jié)點指向本身
if(!T) {
(*Thrt)->lchild = (*Thrt);
return OK; //若根結(jié)點不存在,則該二叉樹為空,讓該頭結(jié)點指向自身.
}
BiThrTree pre; //設(shè)置前驅(qū)結(jié)點
//令頭結(jié)點的左指針指向根結(jié)點
pre = (*Thrt);
(*Thrt)->lchild = T;
//開始遞歸輸入線索化
InThreading(T,&pre);
//此時結(jié)束了最后一個結(jié)點的線索化了,下面的代碼把頭結(jié)點的后繼指向了最后一個結(jié)點.
//并把最后一個結(jié)點的后繼也指向頭結(jié)點,此時樹成為了一個類似雙向鏈表的循環(huán).
pre->rchild = *Thrt;
pre->RTag = Thread;
(*Thrt)->rchild = pre;
return OK;
}
遍歷線索二叉樹
線索二叉樹的遍歷就可以通過之前建立好的線索，沿著后繼線索依依訪問下去就行。
//非遞歸遍歷線索二叉樹
Status InOrderTraverse(BiThrTree T) {
BiThrNode *p = T->lchild;
while(p!=T){
while(p->LTag==Link) p = p->lchild; //走向左子樹的盡頭
printf("%c",p->data );
while(p->RTag==Thread && p->rchild!=T) { //訪問該結(jié)點的后續(xù)結(jié)點
p = p->rchild;
printf("%c",p->data );
}
p = p->rchild;
}
return OK;
}
完整代碼
#include <stdio.h>
#include <stdlib.h>
//函數(shù)狀態(tài)結(jié)果代碼
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
//Status是函數(shù)的類型，其值是函數(shù)結(jié)果狀態(tài)代碼
typedef int Status;
typedef char TElemType;
typedef enum { Link, Thread } PointerTag;
typedef struct BiThrNode {
TElemType data;
struct BiThrNode *lchild, *rchild;
PointerTag LTag;
PointerTag RTag;
}BiThrNode, *BiThrTree;
//線索二叉樹初始化
Status CreateBiThrNode(BiThrTree * B) {
char ch;
scanf("%c", &ch);
if(ch=='#') *B = NULL;
else{
if(!((*B) = (BiThrNode *)malloc(sizeof(BiThrNode)))) exit(OVERFLOW);
(*B)->data = ch;
(*B)->LTag = Link;
(*B)->RTag = Link;
CreateBiThrNode(&(*B)->lchild);
CreateBiThrNode(&(*B)->rchild);
}
return OK;
}
//線索二叉樹線索化
void InThreading(BiThrTree B,BiThrTree *pre) {
if(!B) return;
InThreading(B->lchild,pre);
if(!B->lchild){
B->LTag = Thread;
B->lchild = *pre;
}
if(!(*pre)->rchild){
(*pre)->RTag = Thread;
(*pre)->rchild = B;
}
*pre = B;
InThreading(B->rchild,pre);
}
//為線索二叉樹添加頭結(jié)點，使之可以雙向操作
Status InOrderThreading(BiThrTree *Thrt,BiThrTree T){
if(!(*Thrt = (BiThrTree)malloc(sizeof(BiThrNode)))) exit(OVERFLOW);
(*Thrt)->LTag = Link;
(*Thrt)->RTag = Thread;
(*Thrt)->rchild = (*Thrt);
if(!T) {
(*Thrt)->lchild = (*Thrt);
return OK; //若根結(jié)點不存在,則該二叉樹為空,讓該頭結(jié)點指向自身.
}
BiThrTree pre;
//令頭結(jié)點的左指針指向根結(jié)點
pre = (*Thrt);
(*Thrt)->lchild = T;
//開始遞歸輸入線索化
InThreading(T,&pre);
//此時結(jié)束了最后一個結(jié)點的線索化了,下面的代碼把頭結(jié)點的后繼指向了最后一個結(jié)點.
//并把最后一個結(jié)點的后繼也指向頭結(jié)點,此時樹成為了一個類似雙向鏈表的循環(huán).
pre->rchild = *Thrt;
pre->RTag = Thread;
(*Thrt)->rchild = pre;
return OK;
}
//非遞歸遍歷線索二叉樹
Status InOrderTraverse(BiThrTree T) {
BiThrNode *p = T->lchild;
while(p!=T){
while(p->LTag==Link) p = p->lchild; //走向左子樹的盡頭
printf("%c",p->data );
while(p->RTag==Thread && p->rchild!=T) { //訪問該結(jié)點的后續(xù)結(jié)點
p = p->rchild;
printf("%c",p->data );
}
p = p->rchild;
}
return OK;
}
int main() {
BiThrTree B,T;
CreateBiThrNode(&B);
InOrderThreading(&T,B);
printf("中序遍歷二叉樹的結(jié)果為：");
InOrderTraverse(T);
printf("\n");
}
//測試數(shù)據(jù):abc##de#g##f###
參考資料
- 線索二叉樹的建立與遍歷C語言實現(xiàn)過程詳解
- Threaded Binary Tree
- 動畫：中序線索化二叉樹
- 《大話數(shù)據(jù)結(jié)構(gòu)》
- 《數(shù)據(jù)結(jié)構(gòu)》—嚴蔚敏
