C语言实现线索二叉树的前中后创建和遍历
犀牛超人 人气:01.结构
#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); } }
总结
tag最好另起函数进行初始化,并且在遍历中,牢抓前中后的遍历次序进行分析。
本篇文章就到这里了,希望能够给你带来帮助,也希望您能够多多关注的更多内容!
加载全部内容