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

1.结构

1.1初始化tag

2.基本操作

2.1先序创建二叉树
2.2.先序线索化

2.2.1.先序遍历

2.3.中序线索化

2.3.1中序遍历

2.4.后序线索化

2.4.1后序遍历

总结

1.结构

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

1.1初始化tag

#include#include#define false 0#define true 1using 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=https://www.it610.com/article/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); }}