C语言线索二叉树的前中后如何创建和遍历

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

1.结构

#include<stdio.h>#include<stdlib.h>#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<stdio.h>#include<stdlib.h>#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=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);}}

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