在有n個結點的二叉鏈表中必定存在n+1個空指針域，因此可以利用這些空指針域存放指向結點的某種遍歷次序下的前趨和後繼結點的指針，這種指向前趨和後繼結點的指針稱為“線索”，加上線索的二叉鏈表稱為線索鏈表，相應的二叉樹被稱為線索二叉樹。
有了二叉樹不就足夠了嗎？那為什麼還要弄個線索二叉樹出來呢？
在原來的二叉鏈表中，查找結點的左，右孩子可以直接實現，可是如果要找該結點的前趨和後繼結點呢？這就變得非常困難，所以為了實現這個常見的需求，我們要在每個結點中增加兩個指針域來存放遍歷時得到的前趨和後繼結點，這樣就可以通過該指針直接或間接訪問其前趨和後繼結點。
按某種次序遍歷二叉樹，在遍歷過程中用線索取代空指針即可。
下面是線索二叉樹和線索二叉鏈表示意圖，它可以幫助我們更好地理解線索二叉樹。
代碼如下:
/** 線索二叉樹 **/
#include<stdio.h>
#include<stdlib.h>
typedef char ElemType; //數據類型
typedef enum {Link,Thread} childTag; //Link表示結點,Thread表示線索
typedef struct threadBiTree{
ElemType data;
struct threadBiTree *lchild,*rchild;
int ltag,rtag; //標志位,區分枚舉類型中的節點或線索兩種取值
}threadBiTree,*ptrThreadBiTree;
/**
* 創建一顆普通的二叉樹
*/
void create_BiTree(ptrThreadBiTree &TNode,char* &str){
char ch;
sscanf(str,"%c",&ch);
str++;
if(ch == '#'){ //空節點
TNode = NULL;
}else{
TNode = (ptrThreadBiTree)malloc(sizeof(threadBiTree));
TNode->data = ch;
TNode->ltag = Link;
TNode->rtag = Link;
create_BiTree(TNode->lchild,str);
create_BiTree(TNode->rchild,str);
}
}
/**
* 訪問結點信息
*/
void visit(ptrThreadBiTree &TNode){
printf("%d-%c-%d\n",TNode->ltag,TNode->data,TNode->rtag);
}
/**
* 前序遍歷訪問二叉樹
*/
void pre_order_traverse(ptrThreadBiTree &TNode,int level){
if(TNode){
visit(TNode);
pre_order_traverse(TNode->lchild,level+1);
pre_order_traverse(TNode->rchild,level+1);
}
}
/**
* 中序線索化二叉樹
*/
void in_order_threading(ptrThreadBiTree &preNode,ptrThreadBiTree &root){
if(root){
in_order_threading(preNode,root->lchild);
if(!root->lchild){ //左孩子為空,使其線索指向直接前驅
root->lchild = preNode;
root->ltag = Thread;
}
if(!preNode->rchild){ //如果上一個結點的右孩子為空,則將其指向直接後繼(注意:只有訪問到下一個結點時,才會知道本結點的後繼是誰)
preNode->rchild = root;
preNode->rtag = Thread;
}
preNode = root;
in_order_threading(preNode,root->rchild);
}
}
/**
* 加入一個頭結點,使二叉線索樹成一個封閉環
* 帶有頭結點的二叉樹,頭結點的左孩子指向二叉樹T; 右孩子指向T樹中的最後一個葉子結點
* 不帶有頭結點的二叉樹
*/
void in_thread(ptrThreadBiTree &head,ptrThreadBiTree &root){
head = (ptrThreadBiTree)malloc(sizeof(threadBiTree)); //新增頭節點
head->ltag = Link;
head->rtag = Thread;
head->rchild = head; //初始時使其右線索指向自身
if(!root){ //二叉樹為空,使其左孩子指針指向自身
head->lchild = head;
}else{
head->lchild = root;
ptrThreadBiTree preNode = head; //記錄上次訪問的結點
in_order_threading(preNode,root);
head->rchild = preNode; //將頭結點右孩子指向最後一個葉子結點
preNode->rtag = Thread;
preNode->rchild = head; //將最後一個葉子結點的右孩子指向頭結點,環路就形成了
}
}
/**
* 中序線索二叉樹
*/
void mid_order_traverse(ptrThreadBiTree &head){
ptrThreadBiTree root = head->lchild;
while(root!=head){ //判斷是否空樹
while(root->ltag == Link){
root = root->lchild;
}
visit(root);
while(root->rtag == Thread && root->rchild!=head){ //根據線索,訪問後繼結點,並且後繼結點不是指向頭結點的
root=root->rchild;
visit(root);
}
root=root->rchild;
}
}
int main(){
ptrThreadBiTree head,biTree=NULL;
char *ch = "ab#d##ce###";
create_BiTree(biTree,ch);
//printf("前序遍歷輸出普通二叉樹:\n");
//pre_order_traverse(biTree,1);
//printf("=======================\n");
in_thread(head,biTree);
printf("中序線索二叉樹:\n");
mid_order_traverse(head);
return 0;
}
運行結果截圖:
