已知中序遍历、前序遍历还原二叉树 - 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 pre, char *in, int len)
{
    if(len == 0)
    {
        return NULL;//子树建立完毕,返回空
    }
    treenode *node = new treenode;//新的节点
    int id  = 0;
    for(;id<len; id++)
    {
        if(in[id] == pre[0])//在中序遍历中找到根节点的位置
            break;
    }
    node->data = pre[0];
    node->left = build(pre+1, in, id);//建立左子树
    node->right = build(pre+id+1, in+id+1, len - (id+1));//建立右子树
    cout<<node->data;//输出结果为后序遍历结果
    return node;//返回该节点
}
int main()
{
    char pre =  "GDAFEMHZ", in = "ADEFGHMZ";
    build(pre, in, 8);
    return 0;
}

 

相关文章

发表新评论