数据结构：线索二叉树

目录

        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[Initsize],		//定义ThTree类型的指针数组存储根结点的地址
		   W = NULL;		//定义Thtree类型的指针W指向新建的结点的地址
	int i=0,				//定义int类型的变量i作为左右孩子树的标识
		j=0,				//定义int类型的变量j作为字符串遍历的指针
		top=-1;				//定义int类型的变量top作为结点数组的指针
	char E,R[Initsize];
	printf("请以括号法输入数据，并以此建立二叉树：");
	scanf_s("%s", R, Initsize);
	E = R[i];
	while (E != '\0') {
		switch (E) {
		case '(':
			top++;			 //入栈操作
			Q[top] = 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[top]->lchild = W;			//将栈内的根结点的lchild指向新建的地址
					break;
				case 2:
					Q[top]->rchild = W;			//将栈内的根结点的rchild指向新建的地址
					break;
				}
			}
		}
		j++;
		E = R[j];
	}
	printf("构建线索二叉树对应的二叉树成功\n");
}

void InitThTree(ThTree& A) {	//用于初始化线索二叉树
	A = NULL;
	printf("初始化线索二叉树成功\n");
}