数据结构例程——线索化二叉树(中序)

本文主要是介绍数据结构例程——线索化二叉树(中序)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

本文是数据结构基础系列(6)：树和二叉树中第14课时线索二叉树的例程。

#include <stdio.h>
#include <malloc.h>#define MaxSize 100
typedef char ElemType;
typedef struct node
{ElemType data;int ltag,rtag;      //增加的线索标记struct node *lchild;struct node *rchild;
} TBTNode;void CreateTBTNode(TBTNode * &b,char *str)
{TBTNode *St[MaxSize],*p=NULL;int top=-1,k,j=0;char ch;b=NULL;             //建立的二叉树初始时为空ch=str[j];while (ch!='\0')    //str未扫描完时循环{switch(ch){case '(':top++;St[top]=p;k=1;break;      //为左结点case ')':top--;break;case ',':k=2;break;                          //为右结点default:p=(TBTNode *)malloc(sizeof(TBTNode));p->data=ch;p->lchild=p->rchild=NULL;if (b==NULL)                    //*p为二叉树的根结点b=p;else                            //已建立二叉树根结点{switch(k){case 1:St[top]->lchild=p;break;case 2:St[top]->rchild=p;break;}}}j++;ch=str[j];}
}void DispTBTNode(TBTNode *b)
{if (b!=NULL){printf("%c",b->data);if (b->lchild!=NULL || b->rchild!=NULL){printf("(");DispTBTNode(b->lchild);if (b->rchild!=NULL) printf(",");DispTBTNode(b->rchild);printf(")");}}
}TBTNode *pre;                       //全局变量void Thread(TBTNode *&p)
{if (p!=NULL){Thread(p->lchild);          //左子树线索化if (p->lchild==NULL)        //前驱线索{p->lchild=pre;          //建立当前结点的前驱线索p->ltag=1;}else p->ltag=0;if (pre->rchild==NULL)      //后继线索{pre->rchild=p;          //建立前驱结点的后继线索pre->rtag=1;}else pre->rtag=0;pre=p;Thread(p->rchild);          //右子树线索化}
}TBTNode *CreaThread(TBTNode *b)     //中序线索化二叉树
{TBTNode *root;root=(TBTNode *)malloc(sizeof(TBTNode));  //创建根结点root->ltag=0;root->rtag=1;root->rchild=b;if (b==NULL)                //空二叉树root->lchild=root;else{root->lchild=b;pre=root;               //pre是*p的前驱结点,供加线索用Thread(b);              //中序遍历线索化二叉树pre->rchild=root;       //最后处理,加入指向根结点的线索pre->rtag=1;root->rchild=pre;       //根结点右线索化}return root;
}void ThInOrder(TBTNode *tb)
{TBTNode *p=tb->lchild;      //指向根结点while (p!=tb){while (p->ltag==0) p=p->lchild;printf("%c ",p->data);while (p->rtag==1 && p->rchild!=tb){p=p->rchild;printf("%c ",p->data);}p=p->rchild;}
}int main()
{TBTNode *b,*tb;CreateTBTNode(b,"A(B(D(,G)),C(E,F))");printf(" 二叉树:");DispTBTNode(b);printf("\n");tb=CreaThread(b);printf(" 线索中序序列:");ThInOrder(tb);printf("\n");return 0;
}

这篇关于数据结构例程——线索化二叉树(中序)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---