数据结构 课设二 唯一地确定一棵二叉树

版权声明：转载请注明出处。 https://blog.csdn.net/u014427196/article/details/40866187

唯一地确定一棵二叉树

【问题描述】
如果给出了遍历二叉树的前序序列和中序序列，则可以构造出唯
一的一棵二叉树。试编写实现上述功能的程序。

【基本要求】
已知一棵二叉树的前序和中序序列，试设计完成下列任务的一个
算法：
（1）构造一棵二叉树；
（2）以凹入表形式输出二叉树。
（3）证明构造正确（即分别以前序和中序遍历该树，将得到的结

果与给出的序列进行比较）。

【测试数据】
前序序列为ABDEGCFHIJ，中序序列为DBGEAHFIJC。

#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
#include<string.h>

typedef struct Node
{
    char data;
    struct Node *leftChild;
    struct Node *rightChild;
}BiTreeNode;

void Initiate(BiTreeNode **root)
{
    *root=(BiTreeNode *)malloc(sizeof(BiTreeNode));
    (*root)->leftChild=NULL;
    (*root)->rightChild=NULL;
}
BiTreeNode *InsertLeftNode(BiTreeNode *curr,char x)
{
    BiTreeNode *s,*t;
    if(curr==NULL) return NULL;
    t=curr->leftChild;
    s=(BiTreeNode *)malloc(sizeof(BiTreeNode));
    s->data=x;
    s->leftChild=t;
    s->rightChild=NULL;
    curr->leftChild=s;
    return curr->leftChild;
}
BiTreeNode *InsertRightNode(BiTreeNode *curr,char x)
{
    BiTreeNode *s,*t;
    if(curr==NULL) return NULL;
    t=curr->rightChild;
    s=(BiTreeNode *)malloc(sizeof(BiTreeNode));
    s->data=x;
    s->rightChild=t;
    s->leftChild=NULL;
    curr->rightChild=s;
    return curr->rightChild;
}
void PrintBiTree(BiTreeNode *bt,int n)
{
    int i;
    if(bt==NULL) return;
    PrintBiTree(bt->rightChild,n+1);
    for(i=0;i<n-1;i++) printf("   ");
    if(n>0)
    {
        printf("---");
        printf("%c\n",bt->data);
    }
    PrintBiTree(bt->leftChild,n+1);
}
void Visit(char item)
{
    printf("%c   ",item);
}
void PreOrder(BiTreeNode *t,void Visit(char item))
{
    if(t!=NULL)
    {
        Visit(t->data);
        PreOrder(t->leftChild,Visit);
        PreOrder(t->rightChild,Visit);
    }
}
void InOrder(BiTreeNode *t,void Visit(char item))
{
    if(t!=NULL)
    {
        InOrder(t->leftChild,Visit);
        Visit(t->data);
        InOrder(t->rightChild,Visit);
    }
}
int Search(char str[],char t)
{
    int i=0;
    while(str[i]!=t)
        i++;
    return i;
}
int SearchLeft(int Num[],int t)
{
    int i;
    i=t;
    while(Num[i]!=1&&i>=0)
        i--;
    if(Num[i]==1)
        return i;
    else return -1;
}
int SearchRight(int Num[],int t)
{
    int i;
    i=t;
    while(Num[i]!=1&&i<=10000)
        i++;
    if(Num[i]==1)
        return i;
    else return -1;
}

int main()
{
    int i;
    BiTreeNode *q[10000];
    BiTreeNode *root;
    int left,right,temp;

    int Num[10000]={0};
    char strA[10000];
    char strB[10000];
    char point;
    int n;

    printf("请输入前序遍历:");

    scanf("%s",strA);

    printf("请输入中序遍历:");
    scanf("%s",strB);

    n=strlen(strA);
    Initiate(&root);

    for(i=0;i<n;i++)
    {
        point=strA[i];
        temp=Search(strB,point);
        left=SearchLeft(Num,temp);
        right=SearchRight(Num,temp);
        if(left==-1&&right==-1)
        {
            q[temp]=InsertLeftNode(root,point);
            Num[temp]=1;
        }
        else if(left!=-1&&q[left]->rightChild==NULL)
        {
            q[temp]=InsertRightNode(q[left],point);
            Num[temp]=1;
        }
        else if(right!=-1&&q[right]->leftChild==NULL)
        {
            q[temp]=InsertLeftNode(q[right],point);
            Num[temp]=1;
        }
    }
    PrintBiTree(root,0);

    printf("前序遍历: \n\n");
    PreOrder(root->leftChild,Visit);

    printf("\n中序遍历:\n");
    InOrder(root->leftChild,Visit);

    printf("\n\n                  by :192132 孟凡强\n");

    return 0;


}