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

Mercia ·

更新时间:2024-09-20

· 1075 次阅读

1.结构

1.1初始化tag

2.基本操作

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