出题趋势

　　考点精讲

　　1、树

　　树是一种简单的非线性结构，所有元素之间具有明显的层次特性。

　　在树结构中，每一个结点只有一个前件，称为父结点，没有前件的结点只有一个，称为树的根结点，简称树的根。每一个结点可以有多个后件，称为该结点的子结点。没有后

　　-62-件的结点称为叶子结点。

　　在树结构中，一个结点所拥有的后件的个数称为该结点的度，所有结点中最大的度称为树的度。树的最大层次称为树的深度。

　　2、二叉树：度为2的树就是二叉树。

　　(1)二叉树的特点：①非空二叉树只有一个根结点；②每一个结点最多有两棵子树，且分别称为该结点的左子树与右子树。

　　3、二叉树的性质

　　(1)在二叉树中，第i层的结点总数不超过2i-1(i≥1)。

　　(2)深度为h的二叉树总计最多有2h-1个结点(h≥1)，最少有h个结点。

　　(3)对于任意一棵二叉树，如果其叶子结点数为N0，而度数为2的结点总数为N2，则N0=N2+1，即叶子数总比度为2的节点数多1。

　　(4)具有n个结点的完全二叉树的深度为int(log2n)+1。

　　(5)有N个结点的完全二叉树各结点如果用顺序方式存储，则结点之间有如下关系：

　　若k为结点编号，则如果k<>1，则其父结点的编号为k/2；

　　如果2xk<=N，则其左孩子(即左子树的根结点)的编号为2k；若2xk>N，则无左孩子;如果2xk+1<=N，则其右孩子的结点编号为2k+1；若2k+1>N，则无右孩子。

　　3、完全二叉树和满二叉树

　　(1)完全二叉树：只有最下面的两层结点度小于2，并且最下面一层的结点都集中在该层最左边的若干位置的二叉树；

　　(2)满二叉树：除了叶子结点外每一个结点都有左右子女且叶子结点都处在最低层的二叉树。

　　4、遍历是对树的一种最基本的运算。所谓遍历二叉树，就是按一定的规则和顺序走遍二叉树的所有结点，使每一个结点都被访问一次，而且只被访问一次。由于二叉树是非线性结构，因此，树的遍历实质上是将二叉树的各个结点转换成为一个线性序列来表示。设L、D、R分别表示遍历左子树、访问根结点和遍历右子树，则对一棵二叉树的遍历有三种情况：DLR(称为先根次序遍历，简称前序遍历)，LDR(称为中根次序遍历，简称中序遍历)，LRD(称为后根次序遍历，简称后序遍历)。

　　(1)前序遍历：访问根；按先序遍历左子树；按先序遍历右子树。

　　(2)中序遍历：按中序遍历左予树；访问根；按中序遍历右子树。

　　(3)后序遍历：按后序遍历左予树；按后序遍历右子树；访问根。

　　真题分析

　　【真题1】某二叉树有5个度为2的结点，则该二叉树中的叶子结点数是________。（2009年3月）

　　A)6

　　B)4

　　C)10

　　D)8

　　解析：根据二叉树的性质，在任意二叉树中，度为0的结点(即叶子结点)总是比度为2的结点多一个。

　　答案：A

　　【真题2】深度为5的满二叉树有__【2】__个叶子节点。（2008年4月）

　　解析：在二叉树中，深度为N的满二叉树的叶子结点数目为：2(N-1)。

　　答案：16

　　【真题3】一棵二叉树中共有70个叶子节点与80个度为1的结点，则该二叉树总结点数为________。（2007年9月）

　　A)229

　　B)231

　　C)219

　　D)221

　　解析：在二叉树中，叶子结点个数为N0，则度为2的结点数N2=N0-1。

　　本题中叶子结点的个数为70，所以度为2的结点个数为69，因而总结点数=叶子结点数+度为1的结点数+度为2的结点数=70+80+69=219。

　　答案：C

　　【真题4】某二叉树中有n个度为2的结点，则该二叉树中的叶子结点数为________。（2007年3月）

　　A)2n

　　B)n/2

　　C)n+l

　　D)n-1

　　解析：在任意一棵二叉树中，度为0的结点(即叶子结点)总是比度为2的结点多一个。所以该二叉树的叶子结点数等于n+1。

　　答案：C

　　【真题5】在深度为7的满二叉树中，度为2的结点个数为__【1】__。（2007年3月）

　　解析：一棵深度为7的满二叉树，其结点个数为2-1=127，又因为叶子结点7个数N0和度为2的结点个数N2的关系是N0=N2+1，所以总结点数是N0+N2=2N2+1=127，所以度为2的结点个数等于63。

　　答案：63  [NextPage] 　【真题6】在深度为7的满二叉树中，叶子结点的个数为________。（2006年4月）

　　A)64

　　B)63

　　C)32

　　D)31

　　解析：在二叉树的第k层上，最多有2(k-1)(k≥1)个结点。对于满二叉树来说，每一层上的结点数都达到最大值，即在满二叉树的第k层上有2(k-1)个结点。因此，在深度为7的满二叉树中，所有叶子结点在第7层上，即其结点数 为2(k-1)=2(7-1)=2=64。6

　　答案：A

　　【真题7】一棵二叉树第六层（根结点为第一层）的结点数最多为__【4】__个。（2005年9月）

　　解析：二叉树的一个性质是，在二叉树的第k层上，最多有2(k-1)(k>=1)个节点。由此，2(6-1)=2=32。所以答案为32。5

　　答案：32

　　【真题8】某二叉树中度为2的结点有18个，则该二叉树中有__【1】__个叶子结点。（2005年4月）

　　解析：二叉树具有如下性质：在任意一棵二叉树中，度为0的结点(即叶子结点)总是比度为2的结点多一个。根据题意，度为2的节点为18个，那么，叶子结点就是19个。

　　答案：19

　　【真题9】下列二叉树进行中序遍历的结果是__【1】__。（2008年9月）

　　解析：中序遍历是指先遍历左子树，然后访问根结点，最后遍历右子树；并且，在遍历左、右子树时，仍然先遍历左子树，然后访问根结点，最后遍历右子树。所以中序遍历的结果是DBXEAYFZC。

　　答案：DBXEAYFZC

　　【真题10】对下列二叉树进行中序遍历的结果是__【4】__。（2007年9月）

　　解析：二叉树的中序遍历是指首先按中序遍历根结点的左子树，然后访问根结点，最后按中序遍历根结点的右子树，中序遍历二叉树的过程是一个递归的过程。

　　答案：ACBDFEHGP

　　【真题11】对下列二叉树进行前序遍历的结果为________。对下列二叉树进行前序遍历的结果为________。（2007年3月）

　　A)ABDYECFXZ

　　B)ABCDEFXYZ

　　C)DYBEAFCZX

　　D)YDEBFZXCA

　　解析：二叉树前序遍历的简单描述：若二叉树为空，则结束返回；否则：①访问根结点；②前序遍历左子树；③前序遍历右子树。可见，前序遍历二叉树的过程是一个递归的过程。根据题目中给出的二叉树的结构可知前序遍历的结果是ABDYECFXZ。

　　答案：A

　　【真题12】对下列二叉树进行中序遍历的结果是________。（2006年9月）

　　A)ABDCGEF

　　B)FCADBEG

　　C)ACBDFEG

　　D)ACBDFGE

　　解析：二叉树的中序遍历递归算法为：如果根不空，则(1)按中序次访问左子树，(2)访问跟结点，(3)按中序次序访问右子树；否则返回。二叉树的中序遍历递归算法为：如果根不空，则(1)按中序次访问左子树，(2)访问跟结点，(3)

　　按中序次序访问右子树；否则返回。本题中，根据中序遍历算法，应首先按照中序次序访问以C为根结点的左子树，然后再访问根结点F最后才访问以E为根结点的右子树。遍历以C为根结点的左子树同样要遵循中序遍历算法，因此中序遍历结果为ACBD；然后遍历

　　根结点F；遍历以E为根结点的右子树，同样要遵循中序遍历算法，因此中序遍历结果为EG。最后把这三部分的遍历结果按顺序连接起来，中序遍历结果为ACBDFEG。

　　答案：C

　　【真题13】对如下二叉树对如下二叉树进行后序遍历的结果为________。（2006年4月）

　　A)ABDECF

　　B)DEBFCA

　　C)ABCDEF

　　D)DBEAFC

　　解析：二叉树后序遍历的简单描述如下：若二叉树为空，则结束返回。否则(1)后序遍历左子树；(2)后序遍历右子树；(3)访问根结点。二叉树后序遍历的简单描述如下：若二叉树为空，则结束返回。否则(1)后序遍历左子树；(2)后序遍历右子树；(3)访问根结点。也就是说，后序遍历是指在访问根结点、遍历左子树与遍历右子树这三者中，首先遍历左子树，然后遍历右子树，最后访问根结点，并且，在遍历左、右子树时，仍然先遍历左子树，然后遍历右子树，最后访问根结点。根据后序遍历的算法，后序遍历的结果为DEBFCA。

　　答案：B

　　【真题14】设二叉树如下：

　　对该二叉树进行后序遍历的结果为__【3】__。（2010年3月）

　　解析：本题为二叉树遍历题，LRD的结果为：EDBGHFCA

　　答案：EDBGHFCA

　　【真题15】某二叉树有5个度为2的结点以及3个度为1的结点，则该二叉树中共有__【1】__个结点。（2009年9月）

　　解析：假设：度为0的节点用N0表示，度为1的节点用N1表示，度为2的节点用N2表示。其中度为0的结点数比度为2的结点数多1个，即N0=N2+1。所以N=N0+N1+N2=(N2+1)+N1+N2=N1+2×N2+1=3+2×5+1=14。

　　答案：14

　　【真题16】一棵二叉树有10个度为1的结点，7个度为2的结点，则该二叉树有__【3】__个结点。（2010年9月）

　　解析：计算一棵二叉树结点个数的公式为：度为2的结点数*2+度为1的结点数*1+1。根据这个公式我们可以知道题目中描述的二叉树结点数为25个。

　　答案：25