第五章 树与二叉树 四、线索树(手算与代码实现)

一、定义

1.线索树是一种二叉树，它在每个节点上增加了两个指针，分别指向其前驱和后继。

2.这些指针称为“线索”，因此线索树也叫做“线索化二叉树”。

3.在线索树中，所有的叶子节点都被线索化，使得遍历树的过程可以更加高效地进行。

4.同时，线索树可以在O(1)的时间复杂度内找到任意节点的前驱和后继，而不需要遍历整个树。

二、存储结构（链式存储）

typedef struct BiNode{int data;struct BiNode *lchild,*rchild;
}BiTNode,*BiTree;typedef struct ThreadNode{int data;struct ThreadNode *lchild,*rchild;int ltag,rtag;//左右线索标志
}ThreadNode,*ThreadTree;

ltag==1时，表示lchild指向前驱;

ltag==0时，表示lchild指向左孩子;

rtag==1时，表示rchild指向后继;

rtag==0时，表示rchild指向右孩子;

三、三种线索二叉树

1、手算线索二叉树

（1）中序线索二叉树

1.首先使用中序遍历为每个结点标上序号

2.我们跟着序号来画线索，首先判断D结点，它的没有前驱结点，所以它的前驱线索指向NULL，后继指针指向G

3.接着判断序号为2的结点G,它的前驱是D，后继是B

4.结点B的前驱是G，后继是E，但是在步骤三3中已经找到了它的前驱，而且结点B的指针已经有指向的结点了，所以不能再分配线索指针。

5.依此类推得到中序线索二叉树

（2）先序线索二叉树

1.步骤和中序相同，最重要的就是给结点打上序号，而且要把每个结点的左右孩子指针用完

（3）后序线索二叉树

1.直接上答案，同时要记住一个原则，左孩子指针指向该节点的前驱,右孩子指针指向后继。

（左前驱,右后继）

2、代码实现线索二叉树

（1）中序线索二叉树

#include "stdio.h"
#include "stdlib.h"typedef struct ThreadNode {char data;struct ThreadNode *lchild, *rchild;int ltag, rtag; // 左右线索标志
} 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); // 访问根节点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; // 左右线索标志
} 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); // 访问根节点if(T->ltag == 0)                                    //判断是否为前驱线索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; // 左右线索标志
} 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); // 访问根节点}
}void CreateInThread(ThreadTree T) {pre = NULL;if (T != NULL) {InThread(T);if (pre->rchild == NULL) {pre->rtag = 1;}}
}