数据结构：线索二叉树
目录1.线索二叉树是什么？
2.包含头文件
3.结点设计
4.接口函数定义
5.接口函数实现
线索二叉树是什么？
线索二叉树（Threaded Binary Tree）是一种对普通二叉树的扩展，它通过在树的某些空指针上添加线索来实现更高效的遍历操作。线索二叉树的目的是减少查找特定节点（如前驱或后继节点）所需的时间，从而提高树的搜索效率。以下是线索二叉树的特点：
1.普通二叉树的扩展：线索二叉树是基于普通二叉树的，它保留了二叉树的所有性质。
2.线索：在二叉树的空指针（左子树或右子树的指针）上添加线索，这些线索可以指导我们找到节点的前驱或后继。
3.前驱和后继：每个节点的前驱是其在中序遍历中直接前的一个节点，后继是直接后的节点。线索二叉树允许我们通过线索快速找到这些节点。
包含头文件
#include<stdio.h>
#include<stdlib.h> 结点设计
#define Initsize 100
typedef char Elemtype;
typedef struct ThreadTree {
Elemtype data; //定义Elemtype类型的变量存储结点值
struct ThreadTree* lchild; //定义ThreadTree类型的指针变量lchild存储左子树的地址
struct ThreadTree* rchild; //定义ThreadTree类型的指针变量rchild存储右子树的地址
int Lvalue, Rvalue; //定义int类型的变量Lvalue和Rvalue分别标识线索
}ThreadTree,* ThTree;
ThTree Pre = NULL; //定义ThTree类型的全局变量Pre指向此次结点的前驱结点 接口函数定义
void InitThTree(ThTree& A); //用于初始化线索二叉树
void InsertTree(ThTree& A); //用于输入数据建立二叉树
void InOrder(ThTree A); //用于在二叉树中执行中序遍历
void InOrderVisit(ThTree& A); //用于在结点中进行中序线索化
void InOrderThread(ThTree& A); //用于中序遍历线索化二叉树
void PreOrder(ThTree A); //用于在二叉树中执行先序遍历
void PreOrderVisit(ThTree& A); //用于先序遍历线索化二叉树
void PreOrderThread(ThTree& A); //用于先序遍历线索化二叉树
void PostOrder(ThTree A); //用于执行后序遍历
void PostOrderVisit(ThTree& A); //用于后序遍历线索化二叉树
void PostOrderThread(ThTree& A); //用于后序遍历线索化二叉树 接口函数实现
void PostOrderThread(ThTree& A) { //用于后序遍历线索化二叉树
Pre = NULL;
if (A != NULL) {
PostOrder(A);
if (A->rchild == NULL){
Pre->Rvalue = 1;
}
}
}
void PostOrderVisit(ThTree& A) { //用于后序遍历线索化二叉树
if (A->lchild == NULL) { //若传入的结点的左子树为空，则将该结点的左子树线索化
A->Lvalue = 1;
A->lchild = Pre;
}
if (A->rchild == NULL && Pre != NULL) {
//若传入的结点的空子树为空，且前驱结点不为空，则将该结点的左子树线索化
Pre->rchild = A;
Pre->Rvalue = 1;
}
Pre = A;
}
void PostOrder(ThTree A) { //用于执行后序遍历
if (A != NULL) {
PostOrder(A->lchild);
PostOrder(A->rchild);
PostOrderVisit(A);
}
}
void PreOrderThread(ThTree& A) { //用于先序遍历线索化二叉树
Pre = NULL;
if (A != NULL) {
PreOrder(A);
if (Pre->rchild == NULL) {
Pre->Rvalue = 1;
}
}
}
void PreOrderVisit(ThTree& A) { //用于先序遍历线索化二叉树
if (A->lchild == NULL) { //若传入的结点的左子树为空，则将该结点的左子树线索化
A->Lvalue = 1;
A->lchild = Pre;
}
if (A->rchild == NULL && Pre != NULL) {
//若传入的结点的空子树为空，且前驱结点不为空，则将该结点的左子树线索化
Pre->Rvalue = 1;
Pre->rchild = A;
}
Pre = A;
}
void PreOrder(ThTree A) { //用于在二叉树中执行先序遍历
if (A != NULL) {
PreOrderVisit(A);
if (A->Lvalue==0) {
PreOrder(A->lchild);
}
PreOrder(A->rchild);
}
}
void InOrderThread(ThTree& A) { //用于中序遍历线索化二叉树
Pre = NULL; //遍历第一个结点时，第一个结点无前驱结点，故Pre为NULL
if (A != NULL) {
InOrder(A); //进行中序遍历
if (Pre->rchild == NULL) { //将中序遍历的最后一个结点的右子树线索化
Pre->Rvalue = 1; //因为其结点无后继，故不更新指向
}
}
}
void InOrderVisit(ThTree& A) { //用于在结点中进行线索化
if (A->lchild == NULL) { //左子树若为空，则将其左子树线索化
A->Lvalue = 1;
A->lchild = Pre;
}
if (A->rchild == NULL && Pre != NULL) {//右子树若为空，则将其右子树线索化
Pre->rchild = A;
Pre->Rvalue = 1;
}
Pre = A; //更新指向前驱结点的指针pre
}
void InOrder(ThTree A) { //用于在二叉树执行中序遍历
if (A!= NULL) {
InOrder(A->lchild);
InOrderVisit(A);
InOrder(A->rchild);
}
}
void InsertTree(ThTree& A) { //用于输入数据建立二叉树
ThTree Q, //定义ThTree类型的指针数组存储根结点的地址
W = NULL; //定义Thtree类型的指针W指向新建的结点的地址
int i=0, //定义int类型的变量i作为左右孩子树的标识
j=0, //定义int类型的变量j作为字符串遍历的指针
top=-1; //定义int类型的变量top作为结点数组的指针
char E,R;
printf("请以括号法输入数据，并以此建立二叉树：");
scanf_s("%s", R, Initsize);
E = R;
while (E != '\0') {
switch (E) {
case '(':
top++; //入栈操作
Q = W;
i = 1; //对新结点做标识，1为左子树的标识
break;
case ',':
i = 2; //对新结点做标识，2为右子树的标识
break;
case ')':
top--; //出栈操作
break;
default:
W = (ThreadTree*)malloc(sizeof(ThreadTree)); //新建结点
W->data = E; //更新结点的数据域data的指向
W->rchild = W->lchild = NULL;
if (A == NULL) { //当传入的结点为空时，则新建的结点为树的根结点
A = W;
}
else {
switch (i) { //判断传入的结点为左子树还是右子树
case 1:
Q->lchild = W; //将栈内的根结点的lchild指向新建的地址
break;
case 2:
Q->rchild = W; //将栈内的根结点的rchild指向新建的地址
break;
}
}
}
j++;
E = R;
}
printf("构建线索二叉树对应的二叉树成功\n");
}
void InitThTree(ThTree& A) { //用于初始化线索二叉树
A = NULL;
printf("初始化线索二叉树成功\n");
}
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]