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

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

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=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语言线索二叉树的前中后如何创建和遍历"这篇文章的内容，相信大家都有了一定的了解，希望小编分享的内容对大家有帮助，若想了解更多相关的知识内容，请关注行业资讯频道。