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

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

2016-01-04 900
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介：   写在前面 昨天有同学问到我一题关于重构二叉树的问题(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
目录
相关文章
ephemerals__
|
1月前
|
C语言
【数据结构】二叉树（c语言）（附源码）
本文介绍了如何使用链式结构实现二叉树的基本功能，包括前序、中序、后序和层序遍历，统计节点个数和树的高度，查找节点，判断是否为完全二叉树，以及销毁二叉树。通过手动创建一棵二叉树，详细讲解了每个功能的实现方法和代码示例，帮助读者深入理解递归和数据结构的应用。
ephemerals__
107 8
java冯坚持
|
2月前
|
存储 算法 关系型数据库
数据结构与算法学习二一：多路查找树、二叉树与B树、2-3树、B+树、B*树。（本章为了解基本知识即可，不做代码学习）
这篇文章主要介绍了多路查找树的基本概念，包括二叉树的局限性、多叉树的优化、B树及其变体（如2-3树、B+树、B*树）的特点和应用，旨在帮助读者理解这些数据结构在文件系统和数据库系统中的重要性和效率。
java冯坚持
26 0
数据结构与算法学习二一：多路查找树、二叉树与B树、2-3树、B+树、B*树。（本章为了解基本知识即可，不做代码学习）
java冯坚持
|
2月前
|
存储 算法 搜索推荐
数据结构与算法学习十七：顺序储存二叉树、线索化二叉树
这篇文章主要介绍了顺序存储二叉树和线索化二叉树的概念、特点、实现方式以及应用场景。
java冯坚持
28 0
数据结构与算法学习十七：顺序储存二叉树、线索化二叉树
GuGuStudy
|
2月前
|
Java
【用Java学习数据结构系列】震惊，二叉树原来是要这么学习的（二）
【用Java学习数据结构系列】震惊，二叉树原来是要这么学习的（二）
GuGuStudy
28 1
GuGuStudy
|
2月前
|
算法 Java C语言
【用Java学习数据结构系列】震惊，二叉树原来是要这么学习的（一）
【用Java学习数据结构系列】震惊，二叉树原来是要这么学习的（一）
GuGuStudy
26 1
努力学习的小廉
|
2月前
|
存储
【数据结构】二叉树链式结构——感受递归的暴力美学
【数据结构】二叉树链式结构——感受递归的暴力美学
努力学习的小廉
18 1
是店小二呀
|
2月前
|
存储 编译器 C++
【初阶数据结构】掌握二叉树遍历技巧与信息求解：深入解析四种遍历方法及树的结构与统计分析
【初阶数据结构】掌握二叉树遍历技巧与信息求解：深入解析四种遍历方法及树的结构与统计分析
是店小二呀
36 3
平凡程序猿~
|
2月前
|
存储 算法 调度
数据结构--二叉树的顺序实现（堆实现）
数据结构--二叉树的顺序实现（堆实现）
平凡程序猿~
70 1
是店小二呀
|
2月前
【高阶数据结构】二叉树进阶探秘：AVL树的平衡机制与实现详解（三）
【高阶数据结构】二叉树进阶探秘：AVL树的平衡机制与实现详解
是店小二呀
28 1
是店小二呀
|
2月前
【高阶数据结构】二叉树进阶探秘：AVL树的平衡机制与实现详解（二）
【高阶数据结构】二叉树进阶探秘：AVL树的平衡机制与实现详解
是店小二呀
49 1