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