文档章节

二叉树三种遍历方法(根据两种排序求第三种的顺序)

RainOrz
 RainOrz
发布于 2018/05/14 17:22
字数 335
阅读 277
收藏 0

1.已知先序和中序求后序

     先序遍历的节点顺序是:ADCEFGHB,中序遍历是CDFEGHAB,则后序遍历的结果是  CFHGEDBA

解:1)根据先序遍历结果可知A是根节点,根据中序遍历知道A的左子树是(CDFEGH),右子树是(B)

      2)左边中D是根节点,由中序遍历的顺序CD知道,C是D的左子树;

           E是D的右子树,由中序遍历的顺序FE知道,F是E的左子树;

           G是E的右子树,由中序遍历的顺序GH知道,H是G的右子树

      3)故二叉树的图为 

                                         A

                                       /    \

                                     D       B    

                                    /   \ 

                                  C     E

                                       /   \

                                      F    G

                                              \

                                               H

     4)由图知道后序遍历的结果是CFHGEDBA

2. 已知后序和中序求先序

       后序遍历是DABEC,中序遍历是DEBAC,则先序遍历是CEDBA

解:1)根据后序遍历结果知道C是根节点,根据中序遍历知道C的左子树是DEBA,没有右子树

       2)左边E是根节点,由中序遍历DE知道,D是E的左子树

            B是E的右子树,A是B的右子树

       3)故二叉树的图为 

                                       C

                                     /    \

                                   E

                                 /   \

                                D    B

                                        \

                                         A

      4)由图知道先序遍历的结果是CEDBA

本文转载自:https://blog.csdn.net/jsjxy2009/article/details/39403453/

共有 人打赏支持
RainOrz
粉丝 8
博文 135
码字总数 89239
作品 0
青浦
程序员
私信 提问
Leetcode——二叉树常考算法整理

二叉树常考算法整理 希望通过写下来自己学习历程的方式帮助自己加深对知识的理解,也帮助其他人更好地学习,少走弯路。也欢迎大家来给我的Github的Leetcode算法项目点star呀~~ 前言 二叉树即...

qq_32690999
2018/05/28
0
0
[算法总结] 20 道题搞定 BAT 面试——二叉树

本文首发于我的个人博客:尾尾部落 0. 几个概念 完全二叉树:若二叉树的高度是h,除第h层之外,其他(1h-1)层的节点数都达到了最大个数,并且第h层的节点都连续的集中在最左边。想到点什么没...

繁著
2018/09/04
0
0
面试算法知识梳理(13) - 二叉树算法第三部分

面试算法代码知识梳理系列 面试算法知识梳理(1) - 排序算法 插入排序 希尔排序 选择排序 冒泡排序 计数排序 基数排序 归并排序 快速排序 双向扫描的快速排序 堆排序 面试算法知识梳理(2) - 字...

泽毛
2017/12/22
0
0
Android 面试文档分享

一、概述 最近在准备面试的东西,整理了一些读书笔记分享给各位 百度网盘地址,大家可以自由下载,以下内容完全原创。 前两部分是对于一些 经典书籍的读书笔记 和 面试题,都是上学看书的时候...

泽毛
2017/11/10
0
0
数据结构(二)——树结构模型及应用

基于树实现的数据结构,具有两个核心特征: 逻辑结构:数据元素之间具有层次关系; 数据运算:操作方法具有Log级的平均时间复杂度。 因此,树在文件系统、编译器、索引以及查找算法中有很广的...

yhthu
2017/11/11
0
0

没有更多内容

加载失败,请刷新页面

加载更多

GlusterFS的再次节点重置和恢复

采用Ubuntu+ZFS+GlusterFS的存储集群,其中一个节点再次出现故障,gluster volume status显示为N/A状态。 检查网络,发现原来的IP地址 10.1.1.193发生了改变(估计被DHCP重新分派地址了),导...

openthings
28分钟前
5
0
BOM与正则表达式

BOM BOM的全称叫做Browser OjbectModel 浏览器对象模型,它定义了操作浏览器的接口。 BOM对象包括:Window、History、Navigator、Screen和Location。但是由于浏览器厂商的不同,BOM对象的兼容...

Panda-Q
29分钟前
1
0
牵头函数

箭头函数表达式的语法比函数表达式更短,并且没有自己的this,arguments,super或new.target。这些函数表达式更适用于那些本 来需要匿名函数的地方,并且它们不能用作构造函数。 首先:我们先...

wshining
34分钟前
1
0
mysql把一个数据库中的数据复制到另一个数据库中的表 2个表结构相同

首页 问题 全部问题 经济金融 企业管理 法律法规 社会民生 科学教育 健康生活 体育运动 文化艺术 电子数码 电脑网络 娱乐休闲 行政地区 心理分析 医疗卫生 精选 知道专栏 知道日报 知道大数据...

linjin200
35分钟前
1
0
python redis操作

redis命令:http://blog.csdn.net/yhl27/article/details/9936189 python redis: 干货 http://www.cnblogs.com/wangtp/p/5636872.html http://doc.redisfans.com/ http://developer.51cto.......

stys35
36分钟前
1
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部