您好,登录后才能下订单哦!
密码登录
登录注册
点击 登录注册 即表示同意《亿速云用户服务条款》
这篇“C语言线索二叉树的前中后如何创建和遍历”文章的知识点大部分人都不太理解,所以小编给大家总结了以下内容,内容详细,步骤清晰,具有一定的借鉴价值,希望大家阅读完这篇文章能有所收获,下面我们一起来看看这篇“C语言线索二叉树的前中后如何创建和遍历”文章吧。
#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;
#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;
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; }
//先序线索化. 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); } } }
//寻找先序后继 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); } }
//中序线索化 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); } }
//求中序首结点 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); } }
//后续线索化 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; } }
//求后序前驱 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语言线索二叉树的前中后如何创建和遍历”这篇文章的内容,相信大家都有了一定的了解,希望小编分享的内容对大家有帮助,若想了解更多相关的知识内容,请关注亿速云行业资讯频道。
免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。