AI 助理
文档备案控制台
开发者社区 大数据 文章 正文

数据结构 - 二叉树（重构 + 遍历）

2016-01-04 991
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介：   写在前面 昨天有同学问到我一题关于重构二叉树的问题(link)，做了一下，也做个记录吧！ 所谓二叉树的重构，就是给你前序和中序，或者中序和后序，让你还原这棵二叉树. 注意：给出前序和后序是不能唯一确定一棵二叉树的，证明请看这儿.

 

 

  • 写在前面

昨天有同学问到我一题关于重构二叉树的问题(link)，做了一下，也做个记录吧！

所谓二叉树的重构，就是给你前序和中序，或者中序和后序，让你还原这棵二叉树.

注意：给出前序和后序是不能唯一确定一棵二叉树的，证明请看这儿.

 

一.给出前序和中序，重构二叉树

一个递归的过程：

当前结点的value：每一轮根据前序的第一个元素确定当前结点值.

左子树的中序遍历数组：以当前结点的value为分界点，将中序分为左部分和右部分，左部分即为左子树的中序遍历数组.

右子树的中序遍历数组：以当前结点的value为分界点，将中序分为左部分和右部分，右部分即为右子树的中序遍历数组.

左子树的前序遍历数组：pre[1 ... i] (i为左子树的中序遍历数组的个数).

右子树的前序遍历数组：pre[i+1 ... end]（i为左子树的中序遍历数组的个数）.

构造出这5个值，继续递归求左右子树即可.

题目1：重建二叉树（剑指offer）

给出前序和中序，要你重建二叉树.

按照上面所说递归即可,详见代码：

/**
* -----------------------------------------------------------------
* Copyright (c) 2016 crazyacking.All rights reserved.
* -----------------------------------------------------------------
*       Author: crazyacking
*       Date  : 2016-01-03-21.09
*/
#include <queue>
#include <cstdio>
#include <set>
#include <string>
#include <stack>
#include <cmath>
#include <climits>
#include <map>
#include <cstdlib>
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long( LL);
typedef unsigned long long( ULL);
const double eps( 1e-8);

/**
* Definition for binary tree
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/

struct TreeNode
{
    int val;
    TreeNode * left;
    TreeNode * right;
    TreeNode( int x) : val( x ), left( NULL ), right( NULL) {}
};


class Solution
{
public :
    vector < int > tpr;
    vector < int > tin;
    void reBuild( int a , int b , int n , TreeNode * treeNode)
    {
        if(n == 1) // leaf node
        {
            treeNode = new TreeNode( tpr [ a ]);
            return ;
        }
        else if(n <= 0) // null node
            return ;
        int i = 0;
        for(; tpr [ a ] != tin [b + i ]; ++ i);
        TreeNode * lson , * rson;
        reBuild( a + 1 ,b , i , lson);
        reBuild( a + 1 + i ,b + 1 + i ,n - i - 1 , rson);
        treeNode = new TreeNode( tpr [ a ]);
        treeNode -> left = lson;
        treeNode -> right = rson;
    }
    struct TreeNode * reConstructBinaryTree( vector < int > pre , vector < int > in)
    {
        tpr . clear();
        tin . clear();

        for( int i = 0; i < pre . size(); ++ i)
            tpr . push_back( pre [ i ]);
        for( int i = 0; i < in . size(); ++ i)
            tin . push_back( in [ i ]);

        TreeNode * root;
        int n = pre . size();
        reBuild( 0 , 0 ,n , root);
        return root;
    }
};

void DFS( TreeNode * root)
{
    if( root)
    {
        cout <<( root -> val) << " ";
    }
    else return ;
    if( root -> left)
        DFS( root -> left);
    if( root -> right)
        DFS( root -> right);
}

int main()
{
    freopen( "D: \\ Desktop \\ in.txt" , "r" , stdin);
    int n;
    vector < int > pre;
    vector < int > in;
    while( cin >>n)
    {
        pre . clear();
        in . clear();
        for( int i = 0; i <n; ++ i)
        {
            int tmp;
            cin >> tmp;
            pre . push_back( tmp);
        }
        for( int i = 0; i <n; ++ i)
        {
            int tmp;
            cin >> tmp;
            in . push_back( tmp);
        }
        Solution a;
        TreeNode * root = a . reConstructBinaryTree( pre , in);
        DFS( root);
    }
    return 0;
}

 

题目2：HDU 1710 Binary Tree Traversals

方法一：也很简单，根据上面说的方法递归建树，然后按照后序访问输出即可.

/**
* -----------------------------------------------------------------
* Copyright (c) 2016 crazyacking.All rights reserved.
* -----------------------------------------------------------------
*       Author: crazyacking
*       Date  : 2016-01-04-18.01
*/
#include <queue>
#include <cstdio>
#include <set>
#include <string>
#include <stack>
#include <cmath>
#include <climits>
#include <map>
#include <cstdlib>
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long( LL);
typedef unsigned long long( ULL);
const double eps( 1e-8);

int n;
vector < int > pr;
vector < int > in;

struct TreeNode
{
      int val;
      TreeNode * left , * right;
      TreeNode( int v) : val( v ), left( NULL ), right( NULL ){}
};

TreeNode * reBuildBinaryTree( vector < int > pr , vector < int > in)
{
      if( pr . size() == 0 || in . size() == 0)
            return NULL;
      int root = pr [ 0 ];
      TreeNode * node = new TreeNode( root);
      vector < int > prLeft , prRight , inLeft , inRight;
      int i = 0;
      for(; pr [ 0 ] != in [ i ]; ++ i);

      for( int j = 0; j != i; ++ j)
            inLeft . push_back( in [ j ]);
      for( int j = i + 1; j < in . size(); ++ j)
            inRight . push_back( in [ j ]);
      for( int j = 1; j < i + 1; ++ j)
            prLeft . push_back( pr [ j ]);
      for( int j = i + 1; j < pr . size(); ++ j)
            prRight . push_back( pr [ j ]);

      node -> left = reBuildBinaryTree( prLeft , inLeft);
      node -> right = reBuildBinaryTree( prRight , inRight);
      return node;
}


vector < int > po;
void getPostOrder( TreeNode * root , bool flag)
{
      if( root -> left)
            getPostOrder( root -> left , 0);
      if( root -> right)
            getPostOrder( root -> right , 0);
      po . push_back( root -> val);
}
int main()
{
      while( cin >>n)
      {
            int tmp;
            pr . clear();
            in . clear();
            po . clear();
            for( int i = 0; i <n; ++ i)
            {
                  cin >> tmp;
                  pr . push_back( tmp);
            }
            for( int i = 0; i <n; ++ i)
            {
                  cin >> tmp;
                  in . push_back( tmp);
            }
            TreeNode * root = reBuildBinaryTree( pr , in);
            getPostOrder( root , 1);
            for( int i = 0; i <n; ++ i)
            {
                  if( i <n - 1) cout << po [ i ] << " ";
                  else cout << po [ i ] << endl;
            }
      }
      return 0;
}

 

方法二：由于题目没让重构二叉树，只让输出后序访问的顺序，因此可直接访问输出.

/**
* -----------------------------------------------------------------
* Copyright (c) 2016 crazyacking.All rights reserved.
* -----------------------------------------------------------------
*       Author: crazyacking
*       Date  : 2016-01-04-20.09
*/
#include <queue>
#include <cstdio>
#include <set>
#include <string>
#include <stack>
#include <cmath>
#include <climits>
#include <map>
#include <cstdlib>
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long( LL);
typedef unsigned long long( ULL);
const double eps( 1e-8);

int n;
vector < int > pr; // pre Order
vector < int > in; // in Order
vector < int > po; // post Order

void getPostOrder( int a , int b , int n , bool flag)
{
      if(n == 1)
      {
            po . push_back( pr [ a ]);
            return;
      }
      else if(n <= 0)
            return;
      int i = 0;
      for(; pr [ a ] != in [b + i ]; ++ i);
      getPostOrder( a + 1 ,b , i , false);
      getPostOrder( a + i + 1 ,b + i + 1 ,n - i - 1 , false);
      po . push_back( pr [ a ]);
}

int main()
{
      while( cin >>n)
      {
            pr . clear();
            in . clear();
            po . clear();
            for( int i = 0; i <n; ++ i)
            {
                  int tmp;
                  cin >> tmp;
                  pr . push_back( tmp);
            }
            for( int i = 0; i <n; ++ i)
            {
                  int tmp;
                  cin >> tmp;
                  in . push_back( tmp);
            }

            getPostOrder( 0 , 0 ,n , true);
            for( int i = 0; i <n; ++ i)
            {
                  if( i <n - 1)
                        cout << po [ i ] << " ";
                  else cout << po [ i ] << endl;
            }
      }
      return 0;
}

 

 

 

 

二.给出后序和中序，重构二叉树

一个递归的过程：

当前结点的value：每一轮根据前序的最后一个元素确定当前结点值.

左子树的中序遍历数组：以当前结点的value为分界点，将中序分为左部分和右部分，左部分即为左子树的中序遍历数组.

右子树的中序遍历数组：以当前结点的value为分界点，将中序分为左部分和右部分，右部分即为右子树的中序遍历数组.

左子树的前序遍历数组：pre[0 ... i-1] (i为左子树的中序遍历数组的个数).

右子树的前序遍历数组：pre[i ... end-1]（i为左子树的中序遍历数组的个数）.

构造出这5个值，继续递归求左右子树即可.

红色部分标出的是和上面的不同点，其余都相同.

/**
* -----------------------------------------------------------------
* Copyright (c) 2016 crazyacking.All rights reserved.
* -----------------------------------------------------------------
*       Author: crazyacking
*       Date  : 2016-01-04-22.07
*/
#include <queue>
#include <cstdio>
#include <set>
#include <string>
#include <stack>
#include <cmath>
#include <climits>
#include <map>
#include <cstdlib>
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long( LL);
typedef unsigned long long( ULL);
const double eps( 1e-8);

int n;
vector < int > po;
vector < int > in;

struct TreeNode
{
      int val;
      TreeNode * left , * right;
      TreeNode( int v) : val( v ), left( NULL ), right( NULL ){}
};

TreeNode * reBuildBinaryTree( vector < int > po , vector < int > in)
{
      if( po . size() == 0 || in . size() == 0)
            return NULL;

      int root = po [ po . size() - 1 ];
      TreeNode * node = new TreeNode( root);
      vector < int > poLeft , poRight , inLeft , inRight;
      int i = 0;
      for(; in [ i ] != root; ++ i);

      for( int j = 0; j < i; ++ j)
            inLeft . push_back( in [ j ]);
      for( int j = i + 1; j < in . size(); ++ j)
            inRight . push_back( in [ j ]);
      for( int j = 0; j < i; ++ j)
            poLeft . push_back( po [ j ]);
      for( int j = i; j < po . size() - 1; ++ j)
            poRight . push_back( po [ j ]);
      node -> left = reBuildBinaryTree( poLeft , inLeft);
      node -> right = reBuildBinaryTree( poRight , inRight);
      return node;

}

void print_BFS( TreeNode * root)
{
      queue < TreeNode *> q;
      q . push( root);
      while( ! q . empty())
      {
            TreeNode * now = q . front();
            q . pop();
            cout <<( now -> val) << " ";
            if( now -> left) q . push( now -> left);
            if( now -> right) q . push( now -> right);
      }
}

int main()
{
    // test demo
      int a [] = { 7 , 4 , 2 , 5 , 8 , 6 , 3 , 1 };
      int b [] = { 4 , 7 , 2 , 1 , 5 , 3 , 8 , 6 };
      po . clear();
      in . clear();
      for( int i = 0; i < 8; ++ i)
      {
            po . push_back( a [ i ]);
            in . push_back(b [ i ]);
      }
      TreeNode * root = reBuildBinaryTree( po , in);
      print_BFS( root);
      return 0;
}

 

文章标签：
BI
关键词：
数据结构二叉树
数据结构遍历
crazyacking
目录
相关文章
修己xj
|
10月前
|
存储 算法 Java
算法系列之数据结构-二叉树
树是一种重要的非线性数据结构，广泛应用于各种算法和应用中。本文介绍了树的基本概念、常见类型（如二叉树、满二叉树、完全二叉树、平衡二叉树、B树等）及其在Java中的实现。通过递归方法实现了二叉树的前序、中序、后序和层次遍历，并展示了具体的代码示例和运行结果。掌握树结构有助于提高编程能力，优化算法设计。
修己xj
343 10
算法系列之数据结构-二叉树
RossyYan
|
Java C++
【C++数据结构——树】二叉树的基本运算（头歌实践教学平台习题）【合集】
本关任务：编写一个程序实现二叉树的基本运算。​ 相关知识 创建二叉树 销毁二叉树 查找结点 求二叉树的高度 输出二叉树 //二叉树节点结构体定义 structTreeNode{ intval; TreeNode*left; TreeNode*right; TreeNode(intx):val(x),left(NULL),right(NULL){} }; 创建二叉树 //创建二叉树函数（简单示例，手动构建） TreeNode*create
RossyYan
396 12
RossyYan
|
C++
【C++数据结构——树】二叉树的性质（头歌实践教学平台习题）【合集】
本文档介绍了如何根据二叉树的括号表示串创建二叉树，并计算其结点个数、叶子结点个数、某结点的层次和二叉树的宽度。主要内容包括： 1. **定义二叉树节点结构体**：定义了包含节点值、左子节点指针和右子节点指针的结构体。 2. **实现构建二叉树的函数**：通过解析括号表示串，递归地构建二叉树的各个节点及其子树。 3. **使用示例**：展示了如何调用 `buildTree` 函数构建二叉树并进行简单验证。 4. **计算二叉树属性**： - 计算二叉树节点个数。 - 计算二叉树叶子节点个数。 - 计算某节点的层次。 - 计算二叉树的宽度。 最后，提供了测试说明及通关代
RossyYan
212 10
RossyYan
|
存储 算法 测试技术
【C++数据结构——树】二叉树的遍历算法（头歌教学实验平台习题） 【合集】
本任务旨在实现二叉树的遍历，包括先序、中序、后序和层次遍历。首先介绍了二叉树的基本概念与结构定义，并通过C++代码示例展示了如何定义二叉树节点及构建二叉树。接着详细讲解了四种遍历方法的递归实现逻辑，以及层次遍历中队列的应用。最后提供了测试用例和预期输出，确保代码正确性。通过这些内容，帮助读者理解并掌握二叉树遍历的核心思想与实现技巧。
RossyYan
587 3
三三是该溜子
|
数据库
数据结构中二叉树，哈希表，顺序表，链表的比较补充
二叉搜索树，哈希表，顺序表，链表的特点的比较
三三是该溜子
341 0
数据结构中二叉树，哈希表，顺序表，链表的比较补充
LucianaiB
|
机器学习/深度学习 存储 算法
数据结构实验之二叉树实验基础
本实验旨在掌握二叉树的基本特性和遍历算法，包括先序、中序、后序的递归与非递归遍历方法。通过编程实践，加深对二叉树结构的理解，学习如何计算二叉树的深度、叶子节点数等属性。实验内容涉及创建二叉树、实现各种遍历算法及求解特定节点数量。
LucianaiB
380 4
RossyYan
|
数据采集 存储 算法
【C++数据结构——图】图的遍历（头歌教学实验平台习题） 【合集】
本文介绍了图的遍历算法，包括深度优先遍历（DFS）和广度优先遍历（BFS）。深度优先遍历通过递归方式从起始节点深入探索图，适用于寻找路径、拓扑排序等场景；广度优先遍历则按层次逐层访问节点，适合无权图最短路径和网络爬虫等应用。文中提供了C++代码示例，演示了如何实现这两种遍历方法，并附有测试用例及结果，帮助读者理解和实践图的遍历算法。
RossyYan
733 0
ephemerals__
|
C语言
【数据结构】二叉树（c语言）（附源码）
本文介绍了如何使用链式结构实现二叉树的基本功能，包括前序、中序、后序和层序遍历，统计节点个数和树的高度，查找节点，判断是否为完全二叉树，以及销毁二叉树。通过手动创建一棵二叉树，详细讲解了每个功能的实现方法和代码示例，帮助读者深入理解递归和数据结构的应用。
ephemerals__
1308 8
努力学习的小廉
|
存储
【数据结构】二叉树链式结构——感受递归的暴力美学
【数据结构】二叉树链式结构——感受递归的暴力美学
努力学习的小廉
156 2
GuGuStudy
|
Java
【用Java学习数据结构系列】震惊，二叉树原来是要这么学习的（二）
【用Java学习数据结构系列】震惊，二叉树原来是要这么学习的（二）
GuGuStudy
147 1

热门文章

最新文章

  • 1
    数据结构（一）——数据结构简介
  • 2
    程序员变量命名神器——CodeLf
  • 3
    CentOS 8解决yum不能更新源问题
  • 4
    几个常用快速无损压缩算法性能比较
  • 5
    经典基础C++笔试题（附答案）
  • 6
    Python for循环及基础用法详解
  • 7
    时序数据库技术和架构演进
  • 8
    Aliyun Java Initializr 和 Spring 官方的到底有什么区别？
  • 9
    zabbix报错： cannot connect to [[192.168.119.110]:10050]: [111] Connection refused
  • 10
    Cursor + qwen2.5-coder 32b 的配置方式
  • 1
    基于跳表数据结构的企业局域网监控异常连接实时检测 C++ 算法研究
    192
  • 2
    232.用栈实现队列，225. 用队列实现栈
    193
  • 3
    栈区的非法访问导致的死循环(x64)
    166
  • 4
    Java 集合面试题从数据结构到 HashMap 源码剖析详解及长尾考点梳理
    386
  • 5
    Redis设计与实现——数据结构与对象
    403
  • 6
    快速排序-数据结构与算法
    650
  • 7
    16.1k star! 只需要DDL就能一键生成数据库关系图！开源神器ChartDB让你的数据结构"看得见"
    2141
  • 8
    java实现队列数据结构代码详解
    307
  • 9
    Java 中 .length 的使用方法：深入理解 Java 数据结构中的长度获取机制
    932
  • 10
    线性数据结构详解
    271

    • 相关课程

    更多
  • Go语言核心编程 - 数据结构和算法

    • 相关电子书

    更多
  • 如何使用Tair增强数据结构构建丰富在线实时场景
  • Apache Flink 流式应用中状态的数据结构定义升级
  • 低代码开发师（初级）实战教程
    • 下一篇
    附部署代码｜云数据库RDS 全托管 Supabase服务：小白轻松搞定开发AI应用