前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >二叉树的重建

二叉树的重建

作者头像
指点
发布2019-01-18 17:25:14
5060
发布2019-01-18 17:25:14
举报
文章被收录于专栏:指点的专栏

http://blog.csdn.net/hacker_zhidian/article/details/60586445这篇文章中我们看了一下二叉树的四种遍历方式,接下来我们看一下关于二叉树的重建问题,什么叫二叉树的重建呢?

比方说给你一棵二叉树的前序遍历顺序和中序遍历顺序,要求你求出这颗二叉树的后序遍历顺序。来看一下个具体的例题数据,给定一个二叉树的信息:

二叉树节点数: 5 前序遍历顺序:1 2 3 4 5 中序遍历顺序:3 2 4 1 5 求后续遍历顺序?

像这种题目咋一看没什么头绪啊,如果不熟悉二叉树的性质,这种题是挺费脑的。但是我们仔细想想,二叉树的前序遍历顺序是:根节点 –> 左子树 –> 右子树 中序遍历的顺序是:左子树 –> 根节点 –> 右子树

那么从上面的数据中,我们可以知道,节点值为 1 的节点就是整个二叉树的根节点。之后再去中序遍历的顺序中找节点值为 1 的节点位置,我们在中序遍历的顺序中发现, 节点值为 1 的节点右边有一个节点值为 5 的节点,左边有三个节点值分别为 3 2 4 的节点。Ok,根据中序遍历的顺序,我们知道节点值为 1 的节点有两棵子树,节点值为 1 的节点有两个子节点,接下来,我们要对这个节点的做 左右子节点进行讨论:前序遍历的顺序的第二个节点(节点值为 2 )就是节点值为 1 的节点的左子节点,接下来继续查找这个节点值为 2 的节点在中序遍历中的位置,我们发现节点值为 2 的节点在中序遍历中也存在左右子节点,那么继续对它的左右子节点讨论。。。 如果还是没理解的话看下图:

这里写图片描述
这里写图片描述

这张图是笔者自己模拟的。上传的时候更改了好几次,一会图片大小超过限制,一会图片方向不对。。。 主要还是根据前序遍历和中序遍历的顺序来一步步重建树节点

整个过程的代码,也是这个问题的核心代码:

代码语言:javascript
复制
// 重建二叉树以第 n 个节点为根节点的子二叉树,l 为二叉树节点的左边界,r 为右边界
void rec(int l, int r, int n) { 
    if(l >= r) {
        node[n].w = INF; // 如果当前节点为空,那么赋值为 INF
        return ;
    } 
    int root = pre[pos++];
    node[n].w = root; // 获取当前节点储存的值 
    node[n].l = 2 * n; // 当前节点左孩子所在数组下标 
    node[n].r = 2 * n + 1;  // 当前节点右孩子节点所在数组下标 
    int m = find(in, in+r, root) - in; // 得到当前节点在中序遍历数组中的下标
    rec(l, m, 2*n); // 重建左子树 
    rec(m+1, r, 2*n+1); // 重建右子树 
}

上述代码中,node储存的是二叉树节点的信息数组。下面给出完整的代码:

代码语言:javascript
复制
/*
 * 根据二叉树的前序遍历和中序遍历重建二叉树, 
 * 这里依然采用数组下标来模拟指针 
 */

#include <iostream>
#include <algorithm>
using namespace std;
const int INF = -999999999; // 二叉树节点为空的时候储存的数值 
const int N = 100010; // 二叉树的节点个数 
int pre[N]; // 二叉树前序遍历的结果 
int in[N];  // 二叉树中序遍历的结果  
int pos; 

struct Node { // 节点信息结构体 
    int l; // 节点的左孩子所在数组下标 
    int r; // 节点的右孩子所在数组下标 
    int w; // 节点的值 
}; 
Node node[N]; // 储存二叉树节点信息的数组 

// 重建二叉树的第 n 个节点为根节点的子二叉树, l 为二叉树节点的左边界,r 为右边界
void rec(int l, int r, int n) { 
    if(l >= r) {
        node[n].w = INF; // 如果当前节点为空,那么赋值为 -1 
        return ;
    } 
    int root = pre[pos++];
    node[n].w = root; // 获取当前节点储存的值 
    node[n].l = 2 * n; // 当前节点左孩子所在数组下标 
    node[n].r = 2 * n + 1;  // 当前节点右孩子节点所在数组下标 
    int m = find(in, in+r, root) - in; // 得到当前节点在中序遍历数组中的下标
    rec(l, m, 2*n); // 重建左子树 
    rec(m+1, r, 2*n+1); // 重建右子树 
}

// 后序遍历重建的二叉树 
void postOrderParse(int n) {
    if(node[n].w == INF) { // 如果当前节点为空,那么结束输出 
        return ;
    }

    postOrderParse(2*n); 
    postOrderParse(2*n+1);
    // 这里输出没有严格的控制空格个数,在 OJ 上做题的小伙伴注意一下 
    cout << node[n].w << " "; 
} 

int main() {
    int n;
    cin >> n;
    for(int i = 0; i < n; i++) {
        cin >> pre[i];
    } 
    for(int i = 0; i < n; i++) {
        cin >> in[i];
    } 

    rec(0, n, 1); // 从二叉树根节点开始重建二叉树 

    cout << "该二叉树的后序遍历:" << endl;
    postOrderParse(1); 

    return 0;
} 

好了。来看一下运行结果:

这里写图片描述
这里写图片描述

我们可以手工构造出这棵二叉树:

这里写图片描述
这里写图片描述

根据二叉树的遍历顺序,我们可以很容易得到该二叉树的后续遍历,和程序执行的结果一样。这种二叉树重建的思想可以解决一类问题,感兴趣的小伙伴可以看一下这篇文章 http://blog.csdn.net/Hacker_ZhiDian/article/details/60771795

或者试一下这道题https://www.patest.cn/contests/gplt/L2-011

好了,如果博客中有什么不正确的地方,还请多多指点。如果觉得我写得不错,请点个赞表示对我的支持。

谢谢观看。。。

本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2017年03月07日,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档