一、定義

1.線索樹是一種二叉樹，它在每個(gè)節(jié)點(diǎn)上增加了兩個(gè)指針，分別指向其前驅(qū)和后繼。

2.這些指針稱為“線索”，因此線索樹也叫做“線索化二叉樹”。

3.在線索樹中，所有的葉子節(jié)點(diǎn)都被線索化，使得遍歷樹的過程可以更加高效地進(jìn)行。

4.同時(shí)，線索樹可以在O(1)的時(shí)間復(fù)雜度內(nèi)找到任意節(jié)點(diǎn)的前驅(qū)和后繼，而不需要遍歷整個(gè)樹。

二、存儲結(jié)構(gòu)（鏈?zhǔn)酱鎯?#xff09;

typedef struct BiNode{int data;struct BiNode *lchild,*rchild;
}BiTNode,*BiTree;typedef struct ThreadNode{int data;struct ThreadNode *lchild,*rchild;int ltag,rtag;//左右線索標(biāo)志
}ThreadNode,*ThreadTree;

ltag==1時(shí)，表示lchild指向前驅(qū);

ltag==0時(shí)，表示lchild指向左孩子;

rtag==1時(shí)，表示rchild指向后繼;

rtag==0時(shí)，表示rchild指向右孩子;

三、三種線索二叉樹

1、手算線索二叉樹

（1）中序線索二叉樹

1.首先使用中序遍歷為每個(gè)結(jié)點(diǎn)標(biāo)上序號

2.我們跟著序號來畫線索，首先判斷D結(jié)點(diǎn)，它的沒有前驅(qū)結(jié)點(diǎn)，所以它的前驅(qū)線索指向NULL，后繼指針指向G

3.接著判斷序號為2的結(jié)點(diǎn)G,它的前驅(qū)是D，后繼是B

4.結(jié)點(diǎn)B的前驅(qū)是G，后繼是E，但是在步驟三3中已經(jīng)找到了它的前驅(qū)，而且結(jié)點(diǎn)B的指針已經(jīng)有指向的結(jié)點(diǎn)了，所以不能再分配線索指針。

5.依此類推得到中序線索二叉樹

（2）先序線索二叉樹

1.步驟和中序相同，最重要的就是給結(jié)點(diǎn)打上序號，而且要把每個(gè)結(jié)點(diǎn)的左右孩子指針用完

（3）后序線索二叉樹

1.直接上答案，同時(shí)要記住一個(gè)原則，左孩子指針指向該節(jié)點(diǎn)的前驅(qū),右孩子指針指向后繼。

（左前驅(qū),右后繼）

2、代碼實(shí)現(xiàn)線索二叉樹

（1）中序線索二叉樹

#include "stdio.h"
#include "stdlib.h"typedef struct ThreadNode {char data;struct ThreadNode *lchild, *rchild;int ltag, rtag; // 左右線索標(biāo)志
} ThreadNode, *ThreadTree;ThreadTree pre = NULL; // 使用單一指針void visit(ThreadNode *q) {if (q->lchild == NULL) {q->lchild = pre;q->ltag = 1;}if (pre != NULL && pre->rchild == NULL) {pre->rchild = q;pre->rtag = 1;}pre = q; // 直接賦值給 pre，不需要解引用
}// 中序遍歷二叉樹，一邊遍歷一邊線索化
void InThread(ThreadTree T) {if (T != NULL) {InThread(T->lchild); // 中序遍歷左子樹visit(T); // 訪問根節(jié)點(diǎn)InThread(T->rchild); // 中序遍歷右子樹}
}void CreateInThread(ThreadTree T) {pre = NULL;if (T != NULL) {InThread(T);if (pre->rchild == NULL) {pre->rtag = 1;}}
}

（2）先序線索二叉樹

#include "stdio.h"
#include "stdlib.h"typedef struct ThreadNode {char data;struct ThreadNode *lchild, *rchild;int ltag, rtag; // 左右線索標(biāo)志
} ThreadNode, *ThreadTree;ThreadTree pre = NULL; // 使用單一指針void visit(ThreadNode *q) {if (q->lchild == NULL) {q->lchild = pre;q->ltag = 1;}if (pre != NULL && pre->rchild == NULL) {pre->rchild = q;pre->rtag = 1;}pre = q; // 直接賦值給 pre，不需要解引用
}// 先序遍歷二叉樹，一邊遍歷一邊線索化
void InThread(ThreadTree T) {if (T != NULL) {visit(T); // 訪問根節(jié)點(diǎn)if(T->ltag == 0)                                    //判斷是否為前驅(qū)線索InThread(T->lchild); // 中序遍歷左子樹InThread(T->rchild); // 中序遍歷右子樹}
}void CreateInThread(ThreadTree T) {pre = NULL;if (T != NULL) {InThread(T);if (pre->rchild == NULL) {pre->rtag = 1;}}
}

（3）后序線索二叉樹

#include "stdio.h"
#include "stdlib.h"typedef struct ThreadNode {char data;struct ThreadNode *lchild, *rchild;int ltag, rtag; // 左右線索標(biāo)志
} ThreadNode, *ThreadTree;ThreadTree pre = NULL; // 使用單一指針void visit(ThreadNode *q) {if (q->lchild == NULL) {q->lchild = pre;q->ltag = 1;}if (pre != NULL && pre->rchild == NULL) {pre->rchild = q;pre->rtag = 1;}pre = q; // 直接賦值給 pre，不需要解引用
}// 后序遍歷二叉樹，一邊遍歷一邊線索化
void InThread(ThreadTree T) {if (T != NULL) {InThread(T->lchild); // 中序遍歷左子樹InThread(T->rchild); // 中序遍歷右子樹visit(T); // 訪問根節(jié)點(diǎn)}
}void CreateInThread(ThreadTree T) {pre = NULL;if (T != NULL) {InThread(T);if (pre->rchild == NULL) {pre->rtag = 1;}}
}