二叉树重建

导读:本篇文章讲解 二叉树重建,希望对大家有帮助,欢迎收藏,转发!站点地址:www.bmabk.com

给定二叉树的先序遍历序列和中序遍历序列,进行二叉树的重建以及后序遍历队列。
突然看到这个问题。。发现之前的想法都忘记了=_=||,果然算法题一日不写手生啊,还是得好好坚持练习才行啊。

代码:

#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;

struct node{
    char ch;
    node *left;
    node *right;
};
char pre[100];
char in[100];

node *rec(int s1, int e1, int s2, int e2){
    node *tree = new node;
    char ch = pre[s1];
    tree->ch = ch;
    tree->left = NULL;
    tree->right = NULL;
    int rootidx;       //找到每一颗子树的根节点 划分左右子树
    for(int i=s2; i<=e2; i++){
        if(in[i] == ch){
            rootidx = i;
            break;
        }
    }
    if(rootidx != s2)        // 有左子树的话 那么这个字符在中序序列中肯定不是最左边的
        tree->left = rec(s1+1, s1+(rootidx-s2), s2, rootidx-1);
    if(rootidx != e2)
        tree->right = rec(s1+(rootidx-s2)+1, e1, rootidx+1, e2);
    return tree;

}

void postOrder(node *t){
    if(t){
        if(t->left)
            postOrder(t->left);
        if(t->right)
            postOrder(t->right);
        printf("%c", t->ch);
    }
}
int main(){
    while(~scanf("%s", pre)){
        scanf("%s", in);
        int l = strlen(pre);
        node *tree;
        tree = rec(0, l-1, 0, l-1);
        postOrder(tree);
        printf("\n");
    }
}

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

文章由半码博客整理,本文链接:https://www.bmabk.com/index.php/post/116702.html

(0)

相关推荐

发表回复

登录后才能评论
半码博客——专业性很强的中文编程技术网站,欢迎收藏到浏览器,订阅我们!