这篇“C语言线索二叉树的前中后如何创建和遍历”文章的知识点大部分人都不太理解，所以小编给大家总结了以下内容，内容详细，步骤清晰，具有一定的借鉴价值，希望大家阅读完这篇文章能有所收获，下面我们一起来看看这篇“C语言线索二叉树的前中后如何创建和遍历”文章吧。

1.结构

#include<stdio.h>#include<stdlib.h>#definefalse0#definetrue1usingnamespacestd;typedefstructBTnode{intdata;structBTnode*lchild,*rchild;intltag,rtag;}*BTree,BTnode;1.1初始化tag

#include<stdio.h>#include<stdlib.h>#definefalse0#definetrue1usingnamespacestd;typedefstructBTnode{intdata;structBTnode*lchild,*rchild;intltag,rtag;}*BTree,BTnode;2.基本操作2.1 先序创建二叉树

intj=0;//创建二叉树的全局变量//先序创建二叉树intCreateBTree(BTree&T){intstr[]={1,2,3,NULL,4,NULL,NULL,NULL,5,6,NULL,7,NULL,NULL,8,NULL,NULL};if(str[j]=='#')returnfalse;if(str[j]==NULL){T=NULL;j++;}else{T=(BTnode*)malloc(sizeof(BTnode));T->data=str[j];j++;CreateBTree(T->lchild);CreateBTree(T->rchild);}}

输出函数：

inlineboolvisit(inte){//此处使用内敛函数，提高运行效率printf("%d",e);returntrue;}2.2.先序线索化

//先序线索化.voidprehread(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.先序遍历

//寻找先序后继BTreepreNext(BTreeT){if(T->rtag==1){returnT->rchild;}else{if(T->ltag==0){returnT->lchild;}else{returnT->rchild;}}}//先序线索二叉树的遍历voidprebianli(BTreeT){BTreep;p=T;while(p){visit(p->data);p=preNext(p);}}

2.3.中序线索化

//中序线索化BTreepre=NULL;//中序线索化的全局变量voidInthread(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 中序遍历

//求中序首结点BTreeInFirst(BTreeT){BTreep=T;if(p==NULL)returnNULL;while(p->ltag==0){p=p->lchild;}returnp;}//求中序后继BTreeInNext(BTreeT){BTreenext=NULL;if(T->rtag==1){next=T->rchild;}else{T=T->rchild;while(T->ltag==0){T=T->lchild;}next=T;}returnnext;}//中序线索二叉树的遍历voidInbianli(BTreeT){BTreep;p=InFirst(T);while(p){visit(p->data);p=InNext(p);}}

2.4.后序线索化

//后续线索化voidPostthread(BTree&root){BTreepre=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 后序遍历

//求后序前驱BTreepostnext(BTreeT){if(T->ltag==0){if(T->rtag==0){returnT->rchild;}else{returnT->lchild;}}else{returnT->lchild;}}//后序遍历voidpostbianli(BTreeT){BTreep;p=T;while(p){p=postnext(p);visit(p->data);}}

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