本文共 4822 字，大约阅读时间需要 16 分钟。

• 数据结构课程设计

• 二叉树的构造

任务：已知二叉树的层序和中序遍历序列，或已知二叉树的先序序列、中序序列，试编写算法建立该二叉树（ 用递归或非递归的方法都可以）。

要求：能够输入树的各个结点，并能够输出用不同方法遍历的遍历序列；分别建立建立二叉树存储结构的的输入函数、输出层序遍历序列的函数、输出先序遍历序列的函数；

• 分析

本题考察树和二叉树

第二顺序为前序和后序的创建方法类似，递归创建：

 第二顺序为层序的创建，递归创建：

类似，代码有注释，自认为很明白了。

测试数据已给出在最后

• 首先判断有无左右子树
• 然后确定当前子树的根节点（必然是先序序列的下一个字符）
• 确定根在中序序列位置
• 开始递归创建当前子树的左右子树

• Code，环境codeblocks17 通过

#include 
   
    #include 
    
     #include 
     
      #define ElemType char#define MAXSIZE 999using namespace std;typedef struct BiTNode{    ElemType data;    struct BiTNode *lchild, *rchild;}BiTNode, *BiTree;char A[MAXSIZE],B[MAXSIZE];//A是PreOrder或者是PostOrder,B是InOrderint n;void Input()//输入两种遍历方式，后序遍历后输入{    scanf("%s%s",A,B);}//l1,r1是A的区间;l2,r2是B的区间BiTNode* PreInCreate(int l1,int r1,int l2,int r2)//根据先序以及中序遍历建树{    if(l2>r2)        return NULL;//要根据中序序列l1,r2而不是l1,r1，来判断是否有无左右子树    BiTNode *root=new BiTNode;//确定当前的根，必然是先序序列的下一个字符    root->data = A[l1]; // 赋值    int i;    for(i=l2;B[i]!=A[l1];i++);//确定根在中序序列位置    int llen = i-l2;//计算左子树的长度    root->lchild = PreInCreate(l1+1,l1+llen,l2,i-1);//左子树    root->rchild = PreInCreate(l1+llen+1,r1,i+1,r2);//右子树    return root;//别忘记返回节点}/*教科书上写法的先序和中序转树，也是正确的//l1,r1是A的区间;l2,r2是B的区间，Node* PreInCreate(int l1,int r1,int l2,int r2){    Node *root=new Node(A[l1]);    int i;    for(i=l2;B[i]!=A[l1];i++);//要根据中序序列l1,r2而不是l1,r1，来判断是否有无左右子树    int llen=i-l2;//计算左子树的长度    int rlen=r2-i;//计算右子树的长度    if(llen)//左子树        root->left=PreInCreate(l1+1,l1+llen,l2,i-1);    else root->left=NULL;  //教科书喜欢把判断放在函数中，我个人喜欢把剪枝和终止放在函数头    if(rlen)//右子树        root->right=PreInCreate(l1+llen+1,r1,i+1,r2);    else root->right=NULL;    return root;//别忘记返回节点}*///l1,r1是A的区间;l2,r2是B的区间BiTNode* PostInCreate(int l1,int r1,int l2,int r2)//根据后序以及中序遍历建树{    if(l2>r2)return NULL;//要根据中序序列l1,r2而不是l1,r1，来判断是否有无左右子树    BiTree root=new BiTNode;//确定当前的根，必然是后序序列的最后一个字符    root->data = A[r1]; // 赋值    int i;    for(i=l2;B[i]!=A[r1];i++);//要根据中序序列l1,r2而不是l1,r1，来判断是否有无左右子树    int llen=i-l2;//计算左子树的长度    root->lchild = PostInCreate(l1,l1+llen-1,l2,i-1);//左子树    root->rchild = PostInCreate(l1+llen,r1-1,i+1,r2);//右子树    return root;//别忘记返回节点}BiTNode* LayerInCreate(char* layer, char* in, int n){    if(n == 0) return NULL;    char Llayer[MAXSIZE], Rlayer[MAXSIZE];    char Lin[MAXSIZE], Rin[MAXSIZE];    BiTree root = new BiTNode;    root->data = layer[0];    //find the place of the root    int i;    for(i = 0; i < n; i++)        if(in[i] == layer[0])            break;    //in order    int cnt = 0;    for(int j = 0; j < i ; j++)        Lin[cnt++] = in[j];    cnt = 0;    for(int j = i+1; j < n; j++)        Rin[cnt++] = in[j];    cnt--;    //layer order    int Llayercnt = 0;    int Rlayercnt = 0;    for(int j = 0; j < n ; j++)        for(int k = 0 ; k < i ; k++)            if(layer[j] == in[k])                Llayer[Llayercnt++] = layer[j];    for(int j = 0; j < n; j++)        for(int k = i+1; k < n; k++)            if(layer[j] == in[k])                Rlayer[Rlayercnt++] = layer[j];    root->lchild = LayerInCreate(Llayer,Lin,Llayercnt);    root->rchild = LayerInCreate(Rlayer,Rin,Rlayercnt);    return root;}void PreOrderTravse(BiTree T)//先序遍历，根左右{    if(T==NULL)return;    printf("%c",T->data);//根    PreOrderTravse(T->lchild);//左    PreOrderTravse(T->rchild);//右}void InOrderTravse(BiTree T)//中序遍历，左根右{    if(T==NULL)return;    InOrderTravse(T->lchild);//左    printf("%c",T->data);//根    InOrderTravse(T->rchild);//右}void PostOrderTraverse(BiTree T)//后序遍历，左右根{    if(T==NULL)return;    PostOrderTraverse(T->lchild);//左    PostOrderTraverse(T->rchild);//右    printf("%c",T->data);//根}int main(){    BiTree T = NULL;    printf("please input 2 kind of traverse sequence:\n");    Input();    printf("len :");//长度    scanf("%d",&n);    printf("mode :");//0为先序，1为后序，2为层序    int tag;    scanf("%d",&tag);    printf("\n");    if(tag==0)    {        T=PreInCreate(0,n-1,0,n-1);        printf("the output is (Pre In Post)\n");        PreOrderTravse(T);        printf("\n");        InOrderTravse(T);        printf("\n");        PostOrderTraverse(T);        printf("\n");    }    else if(tag==1)    {        T=PostInCreate(0,n-1,0,n-1);        printf("the output is (Pre In Post)\n");        PreOrderTravse(T);        printf("\n");        InOrderTravse(T);        printf("\n");        PostOrderTraverse(T);        printf("\n");    }    else if(tag==2)    {        T = LayerInCreate(A,B,n);        printf("the output is (Pre In Post)\n");        PreOrderTravse(T);        printf("\n");        InOrderTravse(T);        printf("\n");        PostOrderTraverse(T);        printf("\n");    }    else    {        printf("error input!");    }    system("pause");    return 0;}/*TEST DATA:ABCDEFGHIBCAEDGHFI90CBEHGIFDABCAEDGHFI91ABDCEFGIHBCAEDGHFI92ABDECFGDBEAFCG70ABCDEFGDBEAFCG72*//*struct Node//节点{    char c;    Node *left,*right;    Node(char t)    {        c=t;    }};*/
     
    
   

转载地址：http://sjoen.baihongyu.com/