文档章节

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

RainOrz
 RainOrz
发布于 05/14 17:22
字数 335
阅读 129
收藏 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
博文 123
码字总数 85815
作品 0
青浦
程序员
Leetcode——二叉树常考算法整理

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

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

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

繁著
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

没有更多内容

加载失败,请刷新页面

加载更多

原型模式

1、原型模式-定义 用原型实例指定创建对象的种类,并且通过拷贝这些原型创建新的对象 克隆(浅度克隆->拷贝值类型或者引用,深度克隆->创建新的对象,开辟新的内存) 例如客户端知道抽象Pro...

阿元
51分钟前
5
0
awk命令扩展使用操作

awk 中使用外部shell变量 示例1 [root@centos01 t1022]# A=888[root@centos01 t1022]# echo "" | awk -v GET_A=$A '{print GET_A}'888[root@centos01 t1022]# echo "aaaaaaaaaaaaa" | aw......

野雪球
今天
10
0
深入解析MySQL视图VIEW

Q:什么是视图?视图是干什么用的? A:视图(view)是一种虚拟存在的表,是一个逻辑表,本身并不包含数据。作为一个select语句保存在数据字典中的。   通过视图,可以展现基表的部分数据;...

IT--小哥
今天
13
0
虚拟机学习之二:垃圾收集器和内存分配策略

1.对象是否可回收 1.1引用计数算法 引用计数算法:给对象中添加一个引用计数器,每当有一个地方引用它时,计数器值就加1;当引用失效时,计数器值就减1;任何时候计数器值为0的对象就是不可能...

贾峰uk
今天
10
0
smart-doc功能使用介绍

smart-doc从8月份底开始开源发布到目前为止已经迭代了几个版本。在这里非常感谢那些敢于用smart-doc去做尝试并积极提出建议的社区用户。因此决定在本博客中重要说明下smart-doc的功能,包括使...

上官胡闹
昨天
19
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部