热门标签 | 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. 前序遍历和后序遍历还原二叉树

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


推荐阅读
  • 本文介绍了一种支付平台异步风控系统的架构模型,旨在为开发类似系统的工程师提供参考。 ... [详细]
  • Manacher算法详解:寻找最长回文子串
    本文将详细介绍Manacher算法,该算法用于高效地找到字符串中的最长回文子串。通过在字符间插入特殊符号,Manacher算法能够同时处理奇数和偶数长度的回文子串问题。 ... [详细]
  • 本文介绍了多种开源数据库及其核心数据结构和算法,包括MySQL的B+树、MVCC和WAL,MongoDB的tokuDB和cola,boltDB的追加仅树和mmap,levelDB的LSM树,以及内存缓存中的一致性哈希。 ... [详细]
  • A*算法在AI路径规划中的应用
    路径规划算法用于在地图上找到从起点到终点的最佳路径,特别是在存在障碍物的情况下。A*算法是一种高效且广泛使用的路径规划算法,适用于静态和动态环境。 ... [详细]
  • 解决SQL Server数据库sa登录名无法连接的问题
    在安装SQL Server数据库后,使用Windows身份验证成功,但使用SQL Server身份验证时遇到问题。本文将介绍如何通过设置sa登录名的密码、启用登录名状态以及开启TCP协议来解决这一问题。 ... [详细]
  • 自动验证时页面显示问题的解决方法
    在使用自动验证功能时,页面未能正确显示错误信息。通过使用 `dump($info->getError())` 可以帮助诊断和解决问题。 ... [详细]
  • 网站访问全流程解析
    本文详细介绍了从用户在浏览器中输入一个域名(如www.yy.com)到页面完全展示的整个过程,包括DNS解析、TCP连接、请求响应等多个步骤。 ... [详细]
  • Framework7:构建跨平台移动应用的高效框架
    Framework7 是一个开源免费的框架,适用于开发混合移动应用(原生与HTML混合)或iOS&Android风格的Web应用。此外,它还可以作为原型开发工具,帮助开发者快速创建应用原型。 ... [详细]
  • 本文介绍了如何使用 CMD 批处理脚本进行文件操作,包括将指定目录下的 PHP 文件重命名为 HTML 文件,并将这些文件复制到另一个目录。 ... [详细]
  • 本文介绍了Java编程语言的基础知识,包括其历史背景、主要特性以及如何安装和配置JDK。此外,还详细讲解了如何编写和运行第一个Java程序,并简要介绍了Eclipse集成开发环境的安装和使用。 ... [详细]
  • Bootstrap 缩略图展示示例
    本文将展示如何使用 Bootstrap 实现缩略图效果,并提供详细的代码示例。 ... [详细]
  • 使用 Git Rebase -i 合并多个提交
    在开发过程中,频繁的小改动往往会生成多个提交记录。为了保持代码仓库的整洁,我们可以使用 git rebase -i 命令将多个提交合并成一个。 ... [详细]
  • malloc 是 C 语言中的一个标准库函数,全称为 memory allocation,即动态内存分配。它用于在程序运行时申请一块指定大小的连续内存区域,并返回该区域的起始地址。当无法预先确定内存的具体位置时,可以通过 malloc 动态分配内存。 ... [详细]
  • Python多线程详解与示例
    本文介绍了Python中的多线程编程,包括僵尸进程和孤儿进程的概念,并提供了具体的代码示例。同时,详细解释了0号进程和1号进程在系统中的作用。 ... [详细]
  • 本文详细介绍了Linux系统中用于管理IPC(Inter-Process Communication)资源的两个重要命令:ipcs和ipcrm。通过这些命令,用户可以查看和删除系统中的消息队列、共享内存和信号量。 ... [详细]
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社区 版权所有