目录

  1、还原二叉树

  给定一棵二叉树的先序遍历序列和中序遍历序列，要求计算该二叉树的高度。

  输入格式:

  输入首先给出正整数N（≤50），为树中结点总数。下面两行先后给出先序和中序遍历序列，均是长度为N的不包含重复英文字母（区别大小写）的字符串。

  输出格式:

  输出为一个整数，即该二叉树的高度。

  输入样例:

   9

    ABDFGHIEC
    FDHGIBEAC

  输出样例:

  5

   #include

    #include
    typedef struct node{
        char data;
        struct node *lchild,*rchild;
    }Tree;
    Tree* CreatTree(char before[],char middle[],int n)
    {
        if(n==0)
            return NULL;
        int i;
        Tree *tree=(Tree*)malloc(sizeof(Tree));
        tree->data=before[0];
        for(i=0;ilchild=CreatTree(before+1,middle,i);
        tree->rchild=CreatTree(before+i+1,middle+i+1,n-i-1);
        return tree;
    }
    int CountTree(Tree* tree)
    {
        if(tree==NULL)
            return 0;
        int l,r,max;
            l=CountTree(tree->lchild);
            r=CountTree(tree->rchild);
            if(l>r)
                return l+1;
        return r+1;
    }
    int main()
    {
        int n,i,j;
        char before[101],middle[101];
        scanf("%d",&n);
        getchar();
        for(i=0;irchild);
    }
    int main()
    {
        Tree* tree=(Tree*)malloc(sizeof(Tree));
        Tree* swaptree=(Tree*)malloc(sizeof(Tree));
        tree=CreatTree();
        swaptree=tree;
        PrintTree(swaptree);
        printf("\n");
        SwapTree(tree);
        PrintTree(tree);

  11、 树的遍历

  给定一棵二叉树的后序遍历和中序遍历，请你输出其层序遍历的序列。这里假设键值都是互不相等的正整数。

  输入格式：

  输入第一行给出一个正整数N（≤30），是二叉树中结点的个数。第二行给出其后序遍历序列。第三行给出其中序遍历序列。数字间以空格分隔。

  输出格式：

  在一行中输出该树的层序遍历的序列。数字间以1个空格分隔，行首尾不得有多余空格。

  输入样例：

   7

    2 3 1 5 7 6 4
    1 2 3 4 5 6 7

  输出样例：

  4 1 6 3 5 7 2

<p><pre>#include

include

typedef struct node
{

int data;
struct node *lchild,*rchild;

}Tree;
Tree *queue[100];
Tree* CreatTree(int in[], int post[], int n)
{

if(!n) return NULL;
Tree *T = (Tree*) malloc(sizeof(Tree));
T->data = post[n-1]; //后序遍历的最后一个节点就是树的根节点
//从中序遍历中找到根节点的位置
int i;
for(i=0; ilchild = CreatTree(in, post, i);
T->rchild = CreatTree(in+i+1, post+i, n-i-1);
return T;

}
void PrintTree(Tree *T)
{

if(T)
{
    int l = 0, r = 0;
    queue[r++] = T;
    while (l < r)
    {
        Tree *bt = queue[l++];
        if(bt == T) printf("%d", bt->data); //为根节点时，无空格输出
        else printf(" %d", bt->data);
        if(bt->lchild) queue[r++] = bt->lchild;
        if(bt->rchild) queue[r++] = bt->rchild;
    }
}

}
int main()
{

int in[100]; //中序遍历
int post[100]; //后序遍历
int n;
scanf("%d", &n);
for(int i=0; i