已知中序遍历和后序遍历,还原二叉树 - dblank

已知中序遍历和后序遍历,还原二叉树

直接总结了一下前序遍历和中序遍历还原二叉树的方法,其实后序遍历和中序遍历还原二叉树是一样的道理,只是后序遍历的性质不同。后序遍历的最后一个信息是根节点,根节点的前面一个是根节点的右儿子节点,然后我们通过前面一样的方法划分中序遍历即可。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<map>
#include<cstring>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<cmath>
using namespace std;
const double eps = 1e-10;
const int inf = 0x3f3f3f3f, N = 100 + 10, Mod = 1000000009;
typedef long long ll;

struct treenode
{
    treenode *left;
    treenode *right;
    char data;
};
treenode build(char post, char *in, int len)
{
    if(len == 0)
    {
        return NULL;//子树建立完毕,返回空
    }
    treenode *node = new treenode;//新的节点
    int id  = 0;
    for(;id<len; id++)
    {
        if(in[id] == post[0])//在中序遍历中找到根节点的位置
            break;
    }
    node->data = post[0];
    cout<<node->data;//输出结果为前序
    node->left = build(post+len - id, in, id);//建立左子树
    node->right = build(post+1, in+id+1, len - (id+1));//建立右子树
    return node;//返回该节点
}
int main()
{
    char post[] =  "AEFDHZMG", in[] = "ADEFGHMZ";
    reverse(post, post+8);//倒转遍历结果,更加好处理
    build(post, in, 8);
    return 0;
}

 

相关文章

发表新评论