如何用扩展中序序列创建一个二叉树

如何用扩展中序序列创建一个二叉树

前几天刚回答过一个，以下代码供参考
你要的按先序扩展序列建立二叉树的函数在CreateBiTree里：
#include "stdio.h"
#include "stdlib.h"
#define OK 1
#define ERROR 0
#define OVERFLOW -2

typedef char TElemType;
typedef int Status;
typedef struct BiTNode { // 结点结构
TElemType data;
struct BiTNode *lchild, *rchild;
// 左右孩子指针
} BiTNode, *BiTree;

//以下是建立二叉树存储结构
Status CreateBiTree(BiTree &T) {
char ch;
scanf("%c",&ch);
if(ch=='#') T=NULL;
else{
if(!(T=(BiTNode*)malloc(sizeof(BiTNode))))
exit(OVERFLOW);
T->data=ch;
CreateBiTree(T->lchild);
CreateBiTree(T->rchild);
}
return OK;

} // CreateBiTree
void Preorder(BiTree T)
{
if(T)
{
printf("%c",T->data);
Preorder(T->lchild);
Preorder(T->rchild);
}
}

void Inorder(BiTree T)
{ // 中序遍历二叉树
if(T)
{
Inorder(T->lchild);
printf("%c",T->data);
Inorder(T->rchild);
}
}
void Postorder(BiTree T)
{ // 后序遍历二叉树
if(T)
{
Postorder(T->lchild);
Postorder(T->rchild);
printf("%c",T->data);
}
}

//以下是求叶子结点数
void CountLeaf(BiTree T,int& count){
if(T){
if((!T->lchild)&&(!T->rchild))
count++;
CountLeaf(T->lchild,count);
CountLeaf(T->rchild,count);
}
}

//以下是求二叉树的深度
int Depth(BiTree T ){
int depthval,depthLeft,depthRight;
if(!T) depthval=0;
else{
depthLeft = Depth(T->lchild);
depthRight = Depth(T->rchild);
if(depthLeft>depthRight)depthval = 1+depthLeft;
else depthval = 1+depthRight;
}
return depthval;
}

void main(){
BiTree T;
int s=0,d;
printf("\n creat of the bitree:\n");
CreateBiTree(T);
printf("\n output result of Preorder:\n");
Preorder(T);
CountLeaf(T,s);
d=Depth(T);
printf("\n leaves=%d\n",s);
printf("\n depth=%d\n",d);
}

#include     #include     typedef enum{link,thread} pointertag;      typedef char datatype;    typedef struct bithretree{                           pointertag ltag,rtag;            datatype data;            struct bithretree *lchild,*rchild;            }bithretree;    bithretree *pre;                       bithretree *createtree()                {            bithretree *t;            datatype ch;            scanf("%c",&ch);            if(ch=='#')               t=null;            else               {t=(bithretree *)malloc(sizeof(bithretree));                t->data=ch;                t->ltag=link;                          t->rtag=link;                t->lchild=createtree();                t->rchild=createtree();               }            return t;    }    void inthread(bithretree *t)    {         bithretree *p;         p=t;         if(p)        {         inthread(p->lchild);         if(!p->lchild)            { p->ltag=thread;              p->lchild=pre;            }         if(!pre->rchild)            { pre->rtag=thread;              pre->rchild=p;            }         pre=p;         inthread(p->rchild);        }    }    bithretree *inorderthrtree(bithretree *t)     {         bithretree *thre;                          thre=(bithretree *)malloc(sizeof(bithretree));         thre->lchild=t;         thre->rchild=thre;         pre=thre;         inthread(t);         pre->rtag=thread;         pre->rchild=thre;         thre->rchild=pre;         return thre;    }    void inthrtravel(bithretree *thre)        {         bithretree *p;         p=thre->lchild;         while(p!=thre)                           {           while(p->ltag==link)              p=p->lchild;           printf("%4c",p->data);           while(p->rtag==thread&&p->rchild!=thre)             {p=p->rchild;              printf("%4c",p->data);             }           p=p->rchild;         }    }    void  main()    {        bithretree *t,*thre;        printf("先序创建二叉树:\n");       t=createtree();        thre=inorderthrtree(t);        printf("\n中序线索化二叉树并中序遍历:\n");       inthrtravel(thre);    }