C语言实现线索二叉树的前中后创建和遍历详解

2024-04-02 19:04:59 244人浏览安东尼

摘要

目录1.结构1.1初始化tag2.基本操作2.1 先序创建二叉树2.2.先序线索化2.2.1.先序遍历2.3.中序线索化2.3.1 中序遍历2.4.后序线索化2.4.1 后序遍历总结

1.结构

#include<stdio.h>
#include<stdlib.h>
#define false 0
#define true 1
using namespace std;
typedef struct BTnode{
 	int data;
 	struct BTnode *lchild,*rchild;
 	int ltag,rtag;
 }*BTree,BTnode;

1.1初始化tag

#include<stdio.h>
#include<stdlib.h>
#define false 0
#define true 1
using namespace std;
typedef struct BTnode{
 	int data;
 	struct BTnode *lchild,*rchild;
 	int ltag,rtag;
 }*BTree,BTnode;

2.基本操作

2.1 先序创建二叉树

int j=0;  //创建二叉树的全局变量 
 //先序创建二叉树
 int CreateBTree(BTree &T){
 	int str[]={1,2,3,NULL,4,NULL,NULL,NULL,5,6,NULL,7,NULL,NULL,8,NULL,NULL};
 	if(str[j]=='#') return false;
 	if(str[j]==NULL){
 		T=NULL;
 		j++;
	 }else{
	 	T=(BTnode *)malloc(sizeof(BTnode));
	 	T->data=str[j];
	 	j++;
	 	CreateBTree(T->lchild);
	 	CreateBTree(T->rchild);
	 }
 }

输出函数：

inline bool visit(int e){   //此处使用内敛函数，提高运行效率 
 	printf("%d",e);
 	return true;
 }

2.2.先序线索化

//先序线索化.
 void prehread(BTree &root){
	if(root!=NULL){
		if(root->lchild==NULL){
			root->ltag=1;
			root->lchild=pre;
		}else{
			root->ltag=0;
		}
		if(pre){
			if(pre->rchild==NULL){
				pre->rtag=1;
				pre->rchild=root;
			}else{
				pre->rtag=0;
			}
		}
		pre=root;
		if(root->ltag==0){
		prehread(root->lchild);	
		}
		if(root->rtag==0){
			prehread(root->rchild);
		}
	}
}

2.2.1.先序遍历

//寻找先序后继 
BTree preNext(BTree T){
 	if(T->rtag==1){
		return T->rchild;
	 }else{
	 	if(T->ltag==0){
	 		return T->lchild;
		 }else{
		 	return T->rchild;
		 }
	 }
	 }
//先序线索二叉树的遍历
void prebianli(BTree T){
	BTree p;
	p=T;
	while(p){
		visit(p->data);
		p=preNext(p);
	}
}

2.3.中序线索化

//中序线索化
BTree pre=NULL ;  //中序线索化的全局变量 
void Inthread(BTree &root){
	if(root!=NULL){
		Inthread(root->lchild);
		if(root->lchild==NULL){
			root->ltag=1;
			root->lchild=pre;
		}else{
			root->ltag=0;
		}
		if(pre){
			if(pre->rchild==NULL){
				pre->rtag=1;
				pre->rchild=root;
			}else{
				pre->rtag=0;
			}
		}
		pre=root;
		Inthread(root->rchild);
	}
}

2.3.1 中序遍历

//求中序首结点 
BTree InFirst(BTree T){
	BTree p=T;
	if(p==NULL) return NULL;
	while(p->ltag==0){
		p=p->lchild; 
	}
	return p;
} 
//求中序后继
 BTree InNext(BTree T) {
 	BTree next=NULL;
 	if(T->rtag==1){
 		next=T->rchild;
	 }else {
		T = T->rchild;
		while (T->ltag==0 ) {
			T = T->lchild;
		}
		next=T;
	 }
	 return next;
 }
 //中序线索二叉树的遍历
void Inbianli(BTree T){
	BTree p;
	p=InFirst(T);
	while(p){
		visit(p->data);
		p=InNext(p);
	}
}

2.4.后序线索化

//后续线索化
  void Postthread(BTree &root){
	BTree pre=NULL;
	if(root){
		Postthread(root->lchild);
		Postthread(root->rchild);
		if(root->lchild==NULL){
			root->ltag=1;
			root->lchild=pre;
		}
		if(pre&&pre->rchild==NULL){
			pre->rtag=1;
			pre->rchild=root;
		}
		pre=root;
		}
}

2.4.1 后序遍历

//求后序前驱 
BTree postnext(BTree T){
	if(T->ltag==0){
		if(T->rtag==0){
			return T->rchild;
		}else{
			return T->lchild;
		}
	}else {
		return T->lchild;
	}
}
//后序遍历
void postbianli(BTree T){
	BTree p;
	p=T;
	while(p){
		p=postnext(p);
		visit(p->data);
	}
}