使用C语言实现前，中，后序线索化二叉树

目录

1.线索二叉树

2.线索化二叉树相关操作

（1）数据结构定义

（2）创建二叉树和销毁

（3）前序，中序和后序线索化二叉树

（4）二叉树的高度

（5）统计叶子节点数，所有节点数和第k层节点数

（6）主函数

---

1.线索二叉树

使用C语言实现二叉树的存储

由于二叉树的根节点只有后继节点没有前驱节点，非叶子节点的前驱节点为双亲节点，叶子节点只有前驱节点，没有后继节点，可是我们这里的二叉树线索化的前驱和后继指的是前，中和后序遍历之后的节点前驱和后继节点：如下面的中序遍历结果中的D没有前驱，只有后继，其后继节点为G；而节点C只有前驱没有后继，其前驱节点为F。如果节点的数量不是很大的情况下的话，可以从根节点进行中序遍历访问即可得到中序遍历之后结果的前驱和后继，但是如果二叉树很庞大呢，那么可以使用到二叉树线索化了。

 

由于之前提到在使用二叉树存储节点的时候会出现n+1个指针域的浪费，我们可以使用这个（n+1）个空指针指向前，中和后序遍历之后的前驱和后继。

规定：若结点有左子树，则其lchild域指示其左孩子，否则让lchild域指示其前驱；若结点有右子树，则其rchild域指示其右子树，否则让rchild域指示其后继。

 Ltag=0：表示lchild域指示结点的左孩子；

 Ltag=1：表示lchild域指示结点的前驱；

 Rtag=0：表示rchild域指示结点的右孩子；

 Rtag=1：表示rchild域指示结点的后继。

如下图的中序二叉树线索化：

 

2.线索化二叉树相关操作

（1）数据结构定义

#include
#include
#include
#include
 
#define MAXSIZE 10
 
#define maxn 100
 
typedef char ElemType;
 
typedef struct ThreadNode{
	ElemType data;//节点中的数据元素 
	struct ThreadNode*lchild,*rchild;
	int ltag,rtag; 
}ThreadNode,*ThreadTree;
 
int depth=0;
void InitBitree(){
	printf("--------------1.创建二叉树------------\n");
	printf("--------------2.二叉树的前序遍历线索化\n");
	printf("--------------3.二叉树的中序遍历线索化\n");
	printf("--------------4.二叉树的后序遍历线索化\n");
	printf("--------------5.二叉树的高度----------\n");
	printf("--------------6.二叉树的叶子节点数----\n");
	printf("--------------7.二叉树的节点数--------\n");
	printf("--------------8.第k层节点数----------\n");
	printf("--------------9.重新初始化节点-------\n");
	printf("--------------10.二叉树的销毁操作-----\n");
	printf("--------------11.结束操作-------------\n");
}

（2）创建二叉树和销毁

void DestryBitree(ThreadTree&T){
	if(T==NULL){
		return;
	}
	DestryBitree(T->lchild);
	DestryBitree(T->rchild);
	free(T);
}
//创建二叉树 
void createBitree(ThreadTree&T,char list[maxn],int k,int mask,int length){
	if(list[k]=='\0')mask=0;
	if(k>=length)return;
	if(mask==1){
		T=(ThreadNode*)malloc(sizeof(ThreadNode));
		T->data=list[k];
		T->lchild=NULL;
		T->rchild=NULL;
		T->ltag=0;
		T->rtag=0;
		createBitree(T->lchild,list,2*k+1,mask,length);
		createBitree(T->rchild,list,2*k+2,mask,length);
	}
	return;
}

（3）前序，中序和后序线索化二叉树

ThreadNode*p;//指向目标节点
ThreadNode*pre=NULL;//指向当前访问的节点前驱
ThreadNode*final=NULL;//用于记录最终结果
 
void visit(ThreadNode*q){
//	if(q==p){//当前访问节点刚好是节点p 
//		final=pre;//指向当前节点的前驱 
//	}else{
//		pre=q;//pre指向当前访问的节点 
//	}
	if(q->lchild==NULL){
		q->lchild=pre;//前驱线索化 
		q->ltag=1;
	}
	if(pre!=NULL&&pre->rchild==NULL){
		pre->rchild=q;//后继线索化 
		pre->rtag=1;
	}
	pre=q;//前驱指针移到当前指针q 
} 
 
//中序遍历的同时进行线索化 
void InThread(ThreadTree T){
	if(T==NULL)return;
	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;
		}
	}
} 
//前序遍历的同时进行线索化 
void PreThread(ThreadTree T){
	if(T==NULL)return;
	visit(T);
	//防止出现一直循环 
	if(T->ltag==0){
		PreThread(T->lchild);
	}
	PreThread(T->rchild);
}
void CreatePreThread(ThreadTree T){
	pre=NULL;
	if(T!=NULL){
		PreThread(T);
		//处理最后一个节点 
		if(pre->rchild==NULL){
			pre->rtag=1;
		}
	}
} 
//后序遍历的同时进行线索化 
void PostThread(ThreadTree T){
	if(T==NULL)return;
	PostThread(T->lchild);
	PostThread(T->rchild);
	visit(T);
}
void CreatePostThread(ThreadTree T){
	pre=NULL;
	if(T!=NULL){
		PostThread(T);
		//处理最后一个节点 
		if(pre->rchild==NULL){
			pre->rtag=1;
		}
	}
} 

（4）二叉树的高度

//二叉树的高度
int HeightBitree(ThreadTree T){
	if(T==NULL){ 
		return 0;
	}else{
		int Lheight=HeightBitree(T->lchild);
		int Rheight=HeightBitree(T->rchild);
		depth=Lheight>Rheight?Lheight+1:Rheight+1;
	}
	return depth;
} 

（5）统计叶子节点数，所有节点数和第k层节点数

//统计叶子节点数
int CountLeaf(ThreadTree T){
	if(T==NULL)return 0;
	if(T&&T->lchild==NULL&&T->rchild==NULL){
		return 1;
	}
	return (CountLeaf(T->lchild)+CountLeaf(T->rchild));
} 
 
//二叉树的节点数
int count=0;
void CountNode(ThreadTree T){
	if(T==NULL)return ;
	if(T){
		count++;
	}
	CountNode(T->lchild);
	CountNode(T->rchild);
} 
//二叉树第k层节点数
int KLayerNode(ThreadTree T,int k){
	int a,b;
	if(T==NULL)return 0;
	if(k==1)return 1;
	a=KLayerNode(T,k-1);
	b=KLayerNode(T,k-1);
	return a+b;
} 

（6）主函数

int main(){
	//根节点初始化为NULL 
	ThreadTree T=NULL;
	ElemType list[maxn];
	int flag=0;
	while(1){
		InitBitree();
		printf("请输入操作: ");
		scanf("%d",&flag);
		int k=0;
		int mask=1;
		int depth=0;
		int length=0;
		count=0;
		switch(flag){
			case 1:
				printf("请输入字符序列: ");
				scanf("%s",&list);
				length=strlen(list);
				createBitree(T,list,k,mask,length);
				break;
			case 2:
				CreatePreThread(T);
				printf("\n");
				break;
			case 3:
				CreateInThread(T);
				printf("\n");
				break;
			case 4:
				CreatePostThread(T);
				printf("\n");
				break;
			case 5:
				//二叉树的高度 
				depth=HeightBitree(T);
				printf("二叉树的高度为 = %d\n",depth);
				break;
			case 6:
				//叶子节点数 
				count=CountLeaf(T);
				printf("叶子节点数 = %d\n",count);
				break; 
			case 7:
				//节点数
				CountNode(T); 
				printf("节点数 = %d\n",count);
				break;
			case 8:
				//第k层节点数 
				printf("请输入查找节点的第k层: ");
				scanf("%d",&k);
				depth=HeightBitree(T);
				if(k>depth){
					printf("输入的不合法!\n");
				}else{
					count=KLayerNode(T,k);
					printf("第k层节点数 = %d\n",count);
				}
				break; 
			case 9:
				//重新初始化 
				DestryBitree(T);
				T=NULL;
				break;  
			case 10:
				DestryBitree(T);
				break;
			default:
				if(T!=NULL){
					DestryBitree(T);
				}
				printf("结束操作!");
				break;
		}
		if(flag==11){
			break;
		} 
	}
	return 0;
}