# 線索二叉樹
線索二叉樹是二叉樹線索化，實質是在遍歷二叉樹的過程中，檢查當前節點的左右指針域是否為空，若為空，則將它們改為指向前驅節點或后繼節點的線索。
## 定義
```C
typedef struct node
{
ElemType data;
int ltag, rtag; //增加線索標記，若為1，則表示指向前驅，否則指向孩子
struct node *lchild;
struct node *rchild;
}TBNode;
```
## 中序線索二叉樹
```C
TBTNode *pre;
void Thread(TBTNode *&p)
{
if(p!=NULL){
Thread(p->lchild);
// 建立當前節點的前驅線索
if(p->lchild==NULL){
p->lchild=pre;
p->ltag=1;
}
else p->ltag=0;
// 建立前驅節點的后繼線索
if(pre->rchild==NULL){
pre-rchild=p;
pre->rtag=1;
}
else pre->rtag=0;
pre=p;
Thread(p->rchild);
}
}
TBTNode *CreaThread(TBTNode *b)
{
// 創建頭結點
TBTNode *root;
root=(TBTNode *)malloc(sizeof(TBTNode));
root->ltag=0;
root->rtag=1;
root->rchild=b;
if(b==NUll)
root->lchild=root;
else{
root->lchild=b;
// pre 是 *p 的前驅節點，供加線索
pre=root;
Thread(b);
// 最后加入指向頭結點的線索和頭結點線索化
pre->rchild=root;
pre->rtag=1;
root->rchild=pre;
}
return root;
}
```
## 遍歷線索二叉樹
```C
void ThInOrder(TBTNode *tb)
{
TBTNode *p=tb->lchild;
while(p!=NULL){
while(p->ltag==0)
p=p->lchild;
printf("%c", p->data);
while(p->rtag==1 && p->rchild!=tb){
p=p->rchild;
printf("%c", p->data);
}
p=p->rchild;
}
}
```
