热门标签 | HotTags
当前位置:  开发笔记 > 编程语言 > 正文

二叉树前序遍历、中序遍历和后序遍历之间还原二叉树

1类定义代码2structTreeNode3{4charval;5TreeNode*left;6TreeNode*right;7TreeNode(charx):val(x),lef

技术分享图片


1 // 类定义代码
2 struct TreeNode
3 {
4 char val;
5 TreeNode* left;
6 TreeNode* right;
7 TreeNode(char x) : val(x), left(NULL), right(NULL) {}
8 };
9 int main()
10 {
11 char* pre = "ACDEBF";
12 char* vin = "DCEABF";
13 char* post = "DECFBA";
14 return 0;
15 }


1. 前序遍历和中序遍历还原二叉树

算法思想:描述如下:



  1. 根据 前序遍历 结果,第一个元素为二叉树的根节点;

  2. 观察 中序遍历 结果,根节点左侧的为左子树,若左子树根节点前(后)再无任何元素,则左(右)子树的左分支为空;根节点右侧的为右子树,若右子树根节点前(后)再无任何元素,则左(右)子树的左分支为空;

  3. 通过以上递归过程。先找到当前树的根节点,然后划分为左右子树,再进入左子树重复上面的过程,最后再进入右子树重复上面的过程,最终还原一棵树。

递归代码:


1 TreeNode* BinaryTreeFromOrderings(char* pre, char* vin, int length)
2 {
3 if( length == 0 ) return NULL;
4
5 int rootIndex = 0;
6 // 寻找当前根节点,记录子树元素个数 
7 for(; rootIndex )
8 if( vin[rootIndex] == pre[0] ) break;
9
10 TreeNode* tree = new TreeNode( vin[rootIndex] );
11 // 返回当前左子树
12 tree ->left = BinaryTreeFromOrderings(pre + 1, vin, rootIndex );
13 // 返回当前右子树
14 tree ->right = BinaryTreeFromOrderings(pre + rootIndex + 1, vin + rootIndex + 1, length - (rootIndex + 1));
15
16 return tree;
17 }


2. 中序遍历和后序遍历还原二叉树

算法思想:描述如下:



  1. 根据后序遍历结果,最后一个元素为二叉树的根节点;

  2. 观察中序遍历结果,其中根节点左侧为左子树,若左子树根节点前(后)再无任何元素,则左(右)子树的左分支为空;其中根节点右侧为右子树,若右子树根节点前(后)再无任何元素,则左(右)子树的左分支为空;

  3. 上面描述的过程是递归的。现根据后续遍历结果找根节点,根节点左侧为左子树,右侧为右子树,再进入左子树重复上面的过程,最后进入右子树重复上面的过程,最终还原一棵树。

递归代码:


TreeNode* BinaryTreeFromPostings(char* vin, char* post, int length)
{
if( length == 0 ) return NULL;
int rootIndex = 0;
// 寻找当前根节点,记录子树元素个数
for(; rootIndex )
if( vin[rootIndex] == post[length - 1]) break;

TreeNode
* tree = new TreeNode( vin[rootIndex] );
// 返回当前右子树
tree ->right = BinaryTreeFromPostings(vin + rootIndex + 1, post + rootIndex, length - (rootIndex + 1) );
// 返回当前左子树
tree ->left = BinaryTreeFromPostings(vin, post, rootIndex );

return tree;
}


3. 前序遍历和后序遍历还原二叉树

  已知前序和中序,后序和中序遍历序列之后,可以唯一确定一棵二叉树。但是,只知道前序和后序遍历序列,是无法分辨哪个结点是左子树或右子树。


推荐阅读
  • 网络流24题——试题库问题
    题目描述:假设一个试题库中有n道试题。每道试题都标明了所属类别。同一道题可能有多个类别属性。现要从题库中抽取m道题组成试卷。并要求试卷包含指定类型的试题。试设计一个满足要求的组卷算 ... [详细]
  • 本文提供了一个关于AC自动机(Aho-Corasick Algorithm)的详细解析与实现方法,特别针对P3796题目进行了深入探讨。文章不仅涵盖了AC自动机的基本概念,还重点讲解了如何通过构建失败指针(fail pointer)来提高字符串匹配效率。 ... [详细]
  • 本报告记录了嵌入式软件设计课程中的第二次实验,主要探讨了使用KEIL V5开发环境和ST固件库进行GPIO控制及按键响应编程的方法。通过实际操作,加深了对嵌入式系统硬件接口编程的理解。 ... [详细]
  • LeetCode 102 - 二叉树层次遍历详解
    本文详细解析了LeetCode第102题——二叉树的层次遍历问题,提供了C++语言的实现代码,并对算法的核心思想和具体步骤进行了深入讲解。 ... [详细]
  • 在1995年,Simon Plouffe 发现了一种特殊的求和方法来表示某些常数。两年后,Bailey 和 Borwein 在他们的论文中发表了这一发现,这种方法被命名为 Bailey-Borwein-Plouffe (BBP) 公式。该问题要求计算圆周率 π 的第 n 个十六进制数字。 ... [详细]
  • 在项目冲刺的最后一天,团队专注于软件用户界面的细节优化,包括调整控件布局和字体设置,以确保界面的简洁性和用户友好性。 ... [详细]
  • JavaScript 页面卸载事件详解 (onunload)
    当用户从页面离开时(如关闭页面或刷新页面),会触发 onunload 事件,此时可以执行预设的脚本。需要注意的是,不同的浏览器对 onunload 事件的支持程度可能有所不同。 ... [详细]
  • 默认情况下,Git 使用 Nano 编辑器进行提交信息的编辑,但如果您更喜欢使用 Vim,可以通过简单的配置更改来实现这一变化。本文将指导您如何通过修改全局配置文件来设置 Vim 作为默认的 Git 提交编辑器。 ... [详细]
  • 探索Java 11中的ZGC垃圾收集器
    Java 11引入了一种新的垃圾收集器——ZGC,由Oracle公司研发,旨在支持TB级别的内存容量,并保证极低的暂停时间。本文将探讨ZGC的开发背景、技术特点及其潜在的应用前景。 ... [详细]
  • 本文探讨了使用普通生成函数和指数生成函数解决组合与排列问题的方法,特别是在处理特定路径计数问题时的应用。文章通过详细分析和代码实现,展示了如何高效地计算在给定条件下不相邻相同元素的排列数量。 ... [详细]
  • 在Notepad++中配置Markdown语法高亮及实时预览功能
    本文详细介绍了如何在Notepad++中配置Markdown语法高亮和实时预览功能,包括必要的插件安装和设置步骤。 ... [详细]
  • 探讨如何在映射文件中处理重复的属性字段,以避免数据操作时出现错误。 ... [详细]
  • 利用无代码平台实现高效业务应用开发
    随着市场环境的变化加速,全球企业都在探索更为敏捷的应用开发模式,以便快速响应新兴的商业机遇。然而,传统的软件开发方式不仅成本高昂,而且耗时较长,这往往导致IT与业务部门之间的合作障碍,进而影响项目的成功。本文将探讨如何通过无代码开发平台解决这些问题。 ... [详细]
  • 为何Compose与Swarm之后仍有Kubernetes的诞生?
    探讨在已有Compose和Swarm的情况下,Kubernetes是如何以其独特的设计理念和技术优势脱颖而出,成为容器编排领域的领航者。 ... [详细]
  • 本文探讨了程序员这一职业的本质,认为他们是专注于问题解决的专业人士。文章深入分析了他们的日常工作状态、个人品质以及面对挑战时的态度,强调了编程不仅是一项技术活动,更是个人成长和精神修炼的过程。 ... [详细]
author-avatar
译林hy_774
这个家伙很懒,什么也没留下!
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有