線索二叉樹原理
遍歷二叉樹的其實(shí)就是以一定規(guī)則將二叉樹中的結(jié)點(diǎn)排列成一個(gè)線性序列异袄，得到二叉樹中結(jié)點(diǎn)的先序序列、中序序列或后序序列蝠嘉。這些線性序列中的每一個(gè)元素都有且僅有一個(gè)前驅(qū)結(jié)點(diǎn)和后繼結(jié)點(diǎn)瑰妄。
但是當(dāng)我們希望得到二叉樹中某一個(gè)結(jié)點(diǎn)的前驅(qū)或者后繼結(jié)點(diǎn)時(shí)蕉鸳，普通的二叉樹是無法直接得到的送滞，只能通過遍歷一次二叉樹得到侠草。每當(dāng)涉及到求解前驅(qū)或者后繼就需要將二叉樹遍歷一次，非常不方便犁嗅。
于是是否能夠改變?cè)械慕Y(jié)構(gòu)边涕，將結(jié)點(diǎn)的前驅(qū)和后繼的信息存儲(chǔ)進(jìn)來。
觀察二叉樹的結(jié)構(gòu)褂微，我們發(fā)現(xiàn)指針域并沒有充分的利用功蜓，有很多“NULL”，也就是存在很多空指針宠蚂。
對(duì)于一個(gè)有n個(gè)結(jié)點(diǎn)的二叉鏈表式撼，每個(gè)節(jié)點(diǎn)都有指向左右孩子的兩個(gè)指針域，一共有2n個(gè)指針域求厕。而n個(gè)結(jié)點(diǎn)的二叉樹又有n-1條分支線數(shù)(除了頭結(jié)點(diǎn)著隆，每一條分支都指向一個(gè)結(jié)點(diǎn))，也就是存在2n-(n-1)=n+1個(gè)空指針域呀癣。這些指針域只是白白的浪費(fèi)空間美浦。因此, 可以用空鏈域來存放結(jié)點(diǎn)的前驅(qū)和后繼。線索二叉樹就是利用n+1個(gè)空鏈域來存放結(jié)點(diǎn)的前驅(qū)和后繼結(jié)點(diǎn)的信息项栏。
如圖以中序二叉樹為例浦辨，我們可以把這顆二叉樹中所有空指針域的lchild，改為指向當(dāng)前結(jié)點(diǎn)的前驅(qū)（灰色箭頭）沼沈，把空指針域中的rchild流酬，改為指向結(jié)點(diǎn)的后繼（綠色箭頭）。我們把指向前驅(qū)和后繼的指針叫做線索 列另，加上線索的二叉樹就稱之為線索二叉樹芽腾。
線索二叉樹結(jié)點(diǎn)結(jié)構(gòu)
如果只是在原二叉樹的基礎(chǔ)上利用空結(jié)點(diǎn)，那么就存在著這么一個(gè)問題：我們?nèi)绾沃滥骋唤Y(jié)點(diǎn)的lchild是指向他的左孩子還是指向前驅(qū)結(jié)點(diǎn)页衙？rchild是指向右孩子還是后繼結(jié)點(diǎn)摊滔？顯然我們要對(duì)他的指向增設(shè)標(biāo)志來加以區(qū)分。
因此拷姿，我們?cè)诿恳粋€(gè)結(jié)點(diǎn)都增設(shè)兩個(gè)標(biāo)志域LTag和RTag，它們只存放0或1的布爾型變量旱函，占用的空間很小响巢。于是結(jié)點(diǎn)的結(jié)構(gòu)如圖所示。
其中：
LTag為0是指向該結(jié)點(diǎn)的左孩子棒妨，為1時(shí)指向該結(jié)點(diǎn)的前驅(qū)
RTag為0是指向該結(jié)點(diǎn)的右孩子踪古，為1時(shí)指向該結(jié)點(diǎn)的后繼
因此實(shí)際的二叉鏈表圖為
線索二叉樹的結(jié)構(gòu)實(shí)現(xiàn)
二叉樹的線索存儲(chǔ)結(jié)構(gòu)定義如下：
typedef char TElemType;
typedef enum { Link, Thread } PointerTag; //Link==0,表示指向左右孩子指針
//Thread==1,表示指向前驅(qū)或后繼的線索
//二叉樹線索結(jié)點(diǎn)存儲(chǔ)結(jié)構(gòu)
typedef struct BiThrNode {
TElemType data; //結(jié)點(diǎn)數(shù)據(jù)
struct BiThrNode *lchild, *rchild; //左右孩子指針
PointerTag LTag;
PointerTag RTag; //左右標(biāo)志
}BiThrNode, *BiThrTree;
二叉樹線索化
對(duì)普通二叉樹以某種次序遍歷使其成為線索二叉樹的過程就叫做線索化含长。因?yàn)榍膀?qū)和后繼結(jié)點(diǎn)只有在二叉樹的遍歷過程中才能得到，所以線索化的具體過程就是在二叉樹的遍歷中修改空指針伏穆。
線索化具體實(shí)現(xiàn)
以中序二叉樹的線索化為例拘泞，線索化的具體實(shí)現(xiàn)就是將中序二叉樹的遍歷進(jìn)行修改，把原本打印函數(shù)的代碼改為指針修改的代碼就可以了枕扫。
我們?cè)O(shè)置一個(gè)pre指針陪腌，永遠(yuǎn)指向遍歷當(dāng)前結(jié)點(diǎn)的前一個(gè)結(jié)點(diǎn)。若遍歷的當(dāng)前結(jié)點(diǎn)左指針域?yàn)榭昭糖疲簿褪菬o左孩子诗鸭，則把左孩子的指針指向pre(相對(duì)當(dāng)前結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn))。
右孩子同樣的参滴，當(dāng)pre的右孩子為空强岸，則把pre右孩子的指針指向當(dāng)前結(jié)點(diǎn)(相對(duì)pre結(jié)點(diǎn)為后繼結(jié)點(diǎn))。
最后把當(dāng)前結(jié)點(diǎn)賦給pre砾赔，完成后續(xù)的遞歸遍歷線索化蝌箍。
中序遍歷線索化的遞歸函數(shù)代碼如下：
void InThreading(BiThrTree B,BiThrTree *pre) {
if(!B) return;
InThreading(B->lchild,pre);
//--------------------中間為修改空指針代碼---------------------
if(!B->lchild){ //沒有左孩子
B->LTag = Thread; //修改標(biāo)志域?yàn)榍膀?qū)線索
B->lchild = *pre; //左孩子指向前驅(qū)結(jié)點(diǎn)
}
if(!(*pre)->rchild){ //沒有右孩子
(*pre)->RTag = Thread; //修改標(biāo)志域?yàn)楹罄^線索
(*pre)->rchild = B; //前驅(qū)右孩子指向當(dāng)前結(jié)點(diǎn)
}
*pre = B; //保持pre指向p的前驅(qū)
//---------------------------------------------------------
InThreading(B->rchild,pre);
}
增設(shè)頭結(jié)點(diǎn)
線索化后的二叉樹，就如同操作一個(gè)雙向鏈表暴心。于是我們想到為二叉樹增設(shè)一個(gè)頭結(jié)點(diǎn)妓盲，這樣就和雙向鏈表一樣，即能夠從第一個(gè)結(jié)點(diǎn)正向開始遍歷酷勺，也可以從最后一個(gè)結(jié)點(diǎn)逆向遍歷本橙。
如上圖，在線索二叉鏈表上添加一個(gè)head結(jié)點(diǎn)脆诉，并令其lchild域的指針指向二叉樹的根結(jié)點(diǎn)(A)甚亭，其rchild域的指針指向中序遍歷訪問的最后一個(gè)結(jié)點(diǎn)(G)。同樣地击胜，二叉樹中序序列的第一個(gè)結(jié)點(diǎn)中亏狰，lchild域指針指向頭結(jié)點(diǎn)，中序序列的最后一個(gè)結(jié)點(diǎn)rchild域指針也指向頭結(jié)點(diǎn)偶摔。
于是從頭結(jié)點(diǎn)開始暇唾，我們既可以從第一個(gè)結(jié)點(diǎn)順后繼結(jié)點(diǎn)遍歷，也可以從最后一個(gè)結(jié)點(diǎn)起順前驅(qū)遍歷辰斋。就和雙鏈表一樣策州。
增設(shè)頭結(jié)點(diǎn)并線索化的代碼實(shí)現(xiàn)
//為線索二叉樹添加頭結(jié)點(diǎn)，使之可以雙向操作
Status InOrderThreading(BiThrTree *Thrt,BiThrTree T){
if(!(*Thrt = (BiThrTree)malloc(sizeof(BiThrNode)))) exit(OVERFLOW); //開辟結(jié)點(diǎn)
(*Thrt)->LTag = Link;
(*Thrt)->RTag = Thread; //設(shè)置標(biāo)志域
(*Thrt)->rchild = (*Thrt); //右結(jié)點(diǎn)指向本身
if(!T) {
(*Thrt)->lchild = (*Thrt);
return OK; //若根結(jié)點(diǎn)不存在,則該二叉樹為空,讓該頭結(jié)點(diǎn)指向自身.
}
BiThrTree pre; //設(shè)置前驅(qū)結(jié)點(diǎn)
//令頭結(jié)點(diǎn)的左指針指向根結(jié)點(diǎn)
pre = (*Thrt);
(*Thrt)->lchild = T;
//開始遞歸輸入線索化
InThreading(T,&pre);
//此時(shí)結(jié)束了最后一個(gè)結(jié)點(diǎn)的線索化了,下面的代碼把頭結(jié)點(diǎn)的后繼指向了最后一個(gè)結(jié)點(diǎn).
//并把最后一個(gè)結(jié)點(diǎn)的后繼也指向頭結(jié)點(diǎn),此時(shí)樹成為了一個(gè)類似雙向鏈表的循環(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é)點(diǎn)的后續(xù)結(jié)點(diǎn)
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é)點(diǎn)藕夫，使之可以雙向操作
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é)點(diǎn)不存在,則該二叉樹為空,讓該頭結(jié)點(diǎn)指向自身.
}
BiThrTree pre;
//令頭結(jié)點(diǎn)的左指針指向根結(jié)點(diǎn)
pre = (*Thrt);
(*Thrt)->lchild = T;
//開始遞歸輸入線索化
InThreading(T,&pre);
//此時(shí)結(jié)束了最后一個(gè)結(jié)點(diǎn)的線索化了,下面的代碼把頭結(jié)點(diǎn)的后繼指向了最后一個(gè)結(jié)點(diǎn).
//并把最后一個(gè)結(jié)點(diǎn)的后繼也指向頭結(jié)點(diǎn),此時(shí)樹成為了一個(gè)類似雙向鏈表的循環(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é)點(diǎn)的后續(xù)結(jié)點(diǎn)
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");
}
//測(cè)試數(shù)據(jù):abc##de#g##f###
參考資料
- 線索二叉樹的建立與遍歷C語言實(shí)現(xiàn)過程詳解
- Threaded Binary Tree
- 動(dòng)畫：中序線索化二叉樹
- 《大話數(shù)據(jù)結(jié)構(gòu)》
- 《數(shù)據(jù)結(jié)構(gòu)》—嚴(yán)蔚敏
