当前位置:文档之家› 快速判断二叉树先序遍历 后序遍历

快速判断二叉树先序遍历 后序遍历

一、知道二叉树的先序/后序遍历和中序遍历(中序必须要知道,不然无法判断),要快速判断后序/先序遍历,首先要
了解二叉树的遍历规律

二、二叉树遍历规律
1、三种遍历都有一个规律,就是:
逆时针沿着二叉树外缘移动,即方向相同,如下图1:

图1
2、
3、 不同的是他们出发点不同,下面说明他们的出发点和遍历顺序序列

三、二叉树三种遍历
1、先序遍历
先序遍历先从二叉树的根开始,然后到左子树,再到右子树,,如图2

图2
先序遍历序列是ABDCEF,重点是记住第一个字母“A”是根,出发点是根“A”

2、中序遍历
中序遍历先从左子树开始,然后到根,再到右子树,如图3

图3
即中序遍历序列是DBAECF,重点是记住中序遍历的根位置,是在序列的第一个字母和最后一个字母之间,出发点是左
子树的最下边的左边的开始,(为什么到A之后直接跳过C呢?因为C也是E和F的根,所以按照中序遍历规律,先到
E再到C再到F)
3、后序遍历
后序遍历先从左子树开始,然后到右子树,再到根,如图4

图4
即后序遍历序列式DBECFA,重点是知道了根是最后面一个字母“A”,出发点是左子树的最下边左边,。
四、道了先序遍历和中序遍历,或者是后序遍历和中序遍历,判断出后序遍历,或者是先序遍历的方法
比如知道先序遍历是ABDCEF,中序遍历是DBAECF,那么可以从先序遍历知道这个二叉树的根是A,(如果是选择题,
可以快速判断出后序遍历的序列最后面一个字母肯定是A,然后选择最后面有A的选项)
从中序遍历看出A把DB和ECF隔开,即DB \A \ECF,因此可以知道DB属于左子树,ECF属于右子树

如果是填空题就要写出该二叉树的图,先写出左子树,从中序遍历知道DB是右子树,把DB看成一个整体,则从先序
遍历判断可以确定B是D的根,这样就确定出左子树的图是

把ECF右子树看成一个整体,则从先序遍历可以知道C是E和F的根,确定出右子树是

然后把两个子树连在根“A”的下面,再根据后序遍历规律读出序列就可以了
后面省略。。。。。。。。。。。
这是我参考网上的一些资料总结出来的,只要你理解了三个遍历的规律就很容易做出判断了,我觉得考试的重点是C
语言方面的,比如条件语句,分支结构,循环结构,逻辑判断,数组等,,,,,,,,我当时主要是靠c语言那块得分的,
数据结构我也不是很懂,你可以从简单的开始,记一些基本的,祝你考试成功
http://baike.baidu.com/link?url=b8c_4x48kZCaZsaz7UBkf6IuV27eXjYClCx1VpY_o06icCzcVRjmN_Rd9HtsPzs9

相关主题