依据前序和中序遍历求后序 /后序和中序求前序

根据前序和中序遍历求后序 /后序和中序求前序

给出一二叉树的前序遍历的顺序和中序遍历的顺序我们可以由此得出后序遍历的顺序，根据它们的访问顺序，前序遍历的第一个结点肯定是根结点，与之对应在中序遍历找到对应的根结点的位置，那么在中序遍历中，根结点的左边的元素都属于左子树的元素，根结点右边的元素都属于右子树的元素，之后把左子树当成一个继续操作，就这样可以推出整个树，继而求出后序遍历：

#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#define MAX_SIZE 100+10
using namespace std;
typedef struct TREENODE
{
    char data;
    TREENODE *lchild;
    TREENODE *rchild;
}*treenode;
void postorder(treenode t)
{
    if(t)
    {
        postorder(t->lchild);
        postorder(t->rchild);
        cout << t->data;
    }
}
treenode creatpost(char *pre, char *in, int len)
{
    if(len <= 0)
        return NULL;    
    treenode t = (treenode)malloc(sizeof(treenode));
    t->data = *pre;
    char *p;
    for(p = in;p!=NULL;p++)
        if(*p == *pre)
            break;
    int k = p-in;
    t->lchild = creatpost(pre+1, in, k);
    t->rchild = creatpost(pre+k+1, p+1, len-k-1);
    return t;
}
int main()
{
    char pre[MAX_SIZE], in[MAX_SIZE];  //存储前序遍历和中序遍历
    treenode t;
    while(scanf("%s%s", pre, in) != EOF)
    {
        int len = strlen(pre);
        t = creatpost(pre, in, len);   //建树
        postorder(t);                  //后序遍历访问
        cout << endl;
    }

    return 0;
}

同理给出一二叉树的中序遍历的顺序和后序遍历的顺序我们可以由此得出前序遍历的顺序，后序遍历我们如果从遍历的最后一个元素逆向向前访问的话，那么我们得到结果就是先访问根结点，之后先遍历右子树，最后遍历左子树的结果，所以由中序遍历和后序遍历得到前序遍历的过程就是，先访问后序遍历的最后一个元素，它就是根结点，找到中序遍历中相同的元素，这个元素左边的便是左子树，右边的便是右子树，继而得到整个树，求出前序遍历：

#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#define MAX_SIZE 100+10
using namespace std;
typedef struct TREENODE
{
    char data;
    TREENODE *lchild;
    TREENODE *rchild;
}*treenode;
treenode creatpre(char *in,char *post,int len)
{
    if(len<=0)
        return NULL;
    treenode t;
    t = (treenode)malloc(sizeof(treenode));
    t->data = post[len-1];
    int p,i;
    for(i=0;i<len;i++)
        if(post[len-1]==in[i])
        {
            p=i;
            break;
        }
    t->lchild = creatpre(in , post, p);
    t->rchild = creatpre(in+p+1, post+p, len-p-1);
    return t;
};
void preorder(treenode t)
{
    if(t)
    {
        printf("%c", t->data);
        preorder(t->lchild);
        preorder(t->rchild);
    }
}
int main()
{
    char in[MAX_SIZE], post[MAX_SIZE];
    while(scanf("%s%s", in, post))
    {
       treenode t;
       int len = strlen(in);
       t = creatpre(in, post, len);
       preorder(t);
       printf("\n");
    }
    return 0;
}

那么可以通过前序遍历和后序遍历得出中序遍历么？这是不可以的，

D
/
E
前序遍历： DE, 后序遍历： ED
则下面树的结构也满足前序和后序遍历的序列。
D
\
E
即这种情况，不能唯一确定一棵树。

如果在一个二叉树中，只存在度为0和度为2的结点，那么可以通过前序遍历和后序遍历确定惟一的一颗树，否则这个二叉树就不能被唯一确定。

依据前序和中序遍历求后序 /后序和中序求前序

相关推荐