C语言线索二叉树的前中后如何创建和遍历

发布时间:2022-02-21 13:40:45 作者:iii
来源:亿速云 阅读:157

这篇“C语言线索二叉树的前中后如何创建和遍历”文章的知识点大部分人都不太理解,所以小编给大家总结了以下内容,内容详细,步骤清晰,具有一定的借鉴价值,希望大家阅读完这篇文章能有所收获,下面我们一起来看看这篇“C语言线索二叉树的前中后如何创建和遍历”文章吧。

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);
	}
}

C语言线索二叉树的前中后如何创建和遍历

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);
	}
}

C语言线索二叉树的前中后如何创建和遍历

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);
	}
}

C语言线索二叉树的前中后如何创建和遍历

以上就是关于“C语言线索二叉树的前中后如何创建和遍历”这篇文章的内容,相信大家都有了一定的了解,希望小编分享的内容对大家有帮助,若想了解更多相关的知识内容,请关注亿速云行业资讯频道。

推荐阅读:
  1. 二叉树的创建和遍历
  2. 树的创建和遍历

免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。

c语言

上一篇:C#中如何使用NPOI将List数据导出到Excel文档

下一篇:VSCode如何开发TypeScript

相关阅读

您好,登录后才能下订单哦!

密码登录
登录注册
其他方式登录
点击 登录注册 即表示同意《亿速云用户服务条款》