利用二叉链表构造二叉树的每一个结点

typedef struct TNode
{
    char data;
    struct TNode *lchild,*rchild;
}*Tree;

先序遍历顺序建立二叉链表

#include<stdio.h>
#include<stdlib.h>
typedef struct TNode
{
    char data;
    struct TNode *lchild,*rchild;
}TNode,*Tree;
void Create(TNode *T)
{
    char ch;
    scanf("%c",&ch);
    if(ch=='#')
        *T=NULL;
    else
    {
        T=(TNode *)malloc(sizeof(TNode));
        if(!*T)
            exit(-1);
        T->data=ch;
        Create(T->lchild);
        Create(T->rchild);
    }
}
int main()
{
    TNode *T;
    printf("输入树(#代表空节点):");
    Create(T);
    //我是省略号//
} 

遍历二叉树

//二叉树的先序遍历//
void travel_pre(TNode T)
{
    if(T==NULL)
        return ;
    printf("%c ",T->data);
    travel_pre(T->lchild);
    travel_pre(T->rchild);
}
//二叉树的中序遍历//
void travel_in(TNode T)
{
   if(T==NULL)
       return ;
   travel_in(T->lchild);
   printf("%C ",T->data);
   travel_in(T->rchild);
}
//二叉树的后序遍历//
void travel_post(TNode T)
{
    if(T==NULL)
        return;
    travel_post(T->lchild);
    travel_post(T->rchild);
    printf("%c ",T->data);
}

先序+中序构造二叉树

这是一道OJ题，请移步HDU1710

因为还原二叉树是一个递归的问题，将复杂地问题简化为一个个小问题，所以就拿三个结点的二叉树举栗。

先序：ABC；

中序：BAC；

我们都知道先序遍历是根左右，而中序遍历是左根右，我们可以通过先序找到根节点，根据中序中根节点的位置，就可以找到根节点的左子树（左孩子），和右子树（右孩子）；根据这个规则就可以还原一颗二叉树了。

例如下面的例子。

不难发现根节点是A，那么中序中的1~k就为左子树，k~尾就为右子树。同理，先序中pre+1~pre+k为左子树，pre+k+1~尾为右子树。其他以此类推。

#include<stdlib.h>
#include<stdio.h>
struct TNode
{
    int data;
    TNode * lchild,* rchild;
}*Tree;
int a[1000],b[1000];
int n;
//代码的核心之处//
TNode * Creat(int *a,int *b,int n)
{
    TNode * T;
    for(int i =0;i < n ; ++i)
    {
        if(a[0]==b[i])
        {
            T = (TNode *)malloc(sizeof(TNode));
            T->data = b[i];
            T->lchild = Creat(a+1,b,i);
            T->rchild = Creat(a+i+1,b+i+1,n-i-1);
            return T; 
        }
    }
    return NULL;
}
//后序遍历二叉树
void travel_post(TNode *R)
{
    if(R!=NULL)
    {
        travel_post(R->lchild);
        travel_post(R->rchild);
        if(R==Tree)
        {
            printf("%dn",R->data);
        }
        else{
            printf("%d ",R->data);
        }
    }
}
int main()
{
    int n;
    while(~scanf("%d",&n))
    {
        Tree = NULL;
        //先序
        for(int i =0;i<n;++i)
        {
            scanf("%d",&a[i]);
        }
        //中序
        for(int i =0;i<n;++i)
        {
            scanf("%d",&b[i]);
        }
        Tree = Creat(a,b,n);
        travel_post(Tree);
    }
    return 0;
}

中序+后序构造二叉树

#include<stdio.h>
#include<stdlib.h>
struct TNode
{
    int data;
    TNode *lchild,*rchild;
}*Tree;
int a[1000],b[1000];
int n;
//核心区
TNode * Creat(int *a,int *b,int n)
{
    TNode * T;
    T = (TNode *)malloc(sizeof(TNode));
    if(n<=0)
        return NULL;
    else
    {
        T->data = b[n-1];
        int * p;
        for(p = a;p<a+n;p++)
        {
            if(*p==b[n-1])
                break;
        }
        int t = p-a;
        T->lchild = Creat(a,b,t);
        T->rchild = Creat(a+t+1,b+t,n-t-1);
        return T;
    }
}
//先序遍历
void travel_pre(TNode * R)
{
    if(R!=NULL)
    {
        if(R==Tree)
            printf("%d",R->data);
        else
            printf(" %d",R->data);
        travel_pre(R->lchild);
        travel_pre(R->rchild);
    }
}
int main()
{
    while(~scanf("%d",&n))
    {
        Tree =NULL;
        for(int i =0;i<n;++i)
        {
            scanf("%d",&a[i]);
        }
        for(int i =0;i<n;++i)
        {
            scanf("%d",&b[i]); 
        }
        Tree = Creat(a,b,n);
        travel_pre(Tree);    
        printf("n"); 
     } 
     return 0;
}