1.6　树与二叉树

【考点1】树的基本概念

（1）树是一种简单的非线性结构，在这种结构中，所有数据元素之间的关系具有明显的层次特性。在树的图形表示中，上端结点是前件，下端结点是后件。

（2）在树结构中，每个结点只有一个前件（父结点），没有前件的结点只有一个，称为树的根结点。每个结点都可以有多个后件（子结点），没有后件的结点称为叶子结点。

（3）一个结点拥有的后件个数称为该结点的度。除根结点外，每个结点都有一个唯一的分支指向它。树中的结点数为树中所有结点的度之和再加1。

（4）根结点在第1层，同一层上所有结点的所有子结点都在下一层，树的最大层次称为树的深度。

（5）在树中，叶子结点没有子树。

（6）用树来表示算术表达式的原则：

①表达式中的每一个运算符在树中对应一个结点，称为运算符结点；

②运算符的每一个运算对象在树中为该运算符结点的子树（在树中的顺序为从左到右）；

③运算对象中的单变量均为叶子结点。

【真题演练】

1下列数据结构中，属于非线性结构的是（　　）。[2013年3月真题]

A．循环队列

B．带链队列

C．二叉树

D．带链栈

【答案】C

【解析】线性结构要满足两个条件：①有且仅有一个根结点；②每个结点最多有一个前驱，也最多有一个后继。栈和队列均满足这两个条件，属于线性结构；循环队列是一个头结点和尾结点互为前驱结点和后继结点的特殊的队列，属于线性结构；带链队列、带链栈都是用链表形式来实现的，分别满足队列和栈的条件，只是存储结构不连续，属于线性结构。二叉树除了叶子结点外，每个结点都可以有两个后继结点，属于非线性结构。答案选择C选项。

2某二叉树的中序序列为DCBAEFG，后序序列为DCBGFEA，则该二叉树的深度（根结点在第1层）为（　　）。[2015年3月真题]

A．5

B．4

C．3

D．2

【答案】B

【解析】二叉树的后序序列为DCBGFEA，则A为根结点。中序序列为DCBAEFG，则DCB为左子树结点，EFG为右子树结点。同理B为C父结点，C为D父结点。根据分析，可画出左子树，同理E为F父结点，F为G父结点。根据分析，可画出右子树，故二叉树深度为4层。

【考点2】二叉树及其基本性质

（1）二叉树定义

二叉树是一种很有用的非线性结构，树结构的特殊形式。

（2）二叉树的两个特点

①非空二叉树只有一个根结点；

②每一个结点最多有两棵子树，且分别称为该结点的左子树与右子树。

（3）二叉树的基本性质

①在二叉树的第k层上，最多有2^k－1（k≥1）个结点。

②深度为m的二叉树最多有2^m－1个结点。

③在任意一棵二叉树中，度为0的结点（即叶子结点）总是比度为2的结点多一个。

④具有n个结点的二叉树，其深度至少为[log₂n]＋1，其中[log₂n]表示取log₂n的整数部分。

（4）满二叉树与完全二叉树

满二叉树与完全二叉树是两种特殊形态的二叉树。

①满二叉树

除最后一层外，每一层上的所有结点都有两个子结点。

②完全二叉树

a．除最后一层外，每一层上的结点数均达到最大值；在最后一层上只缺少右边的若干结点。

b．对于完全二叉树来说，叶子结点只可能在层次最大的两层上出现；对于任何一个结点，若其右分支下的子孙结点的最大层次为p，则其左分支下的子孙结点的最大层次或为p，或为p＋1。

c．满二叉树也是完全二叉树，而完全二叉树不一定是满二叉树。

③完全二叉树具有以下两个性质：

a．具有n个结点的完全二叉树的深度为[log₂n]＋1。

b．设完全二叉树共有n个结点。如果从根结点开始，按层序（每一层从左到右）用自然数1，2，…，n给结点进行编号，则对于编号为k（k＝1，2，…，n）的结点有以下结论：

第一，若k＝1，则该结点为根结点，它没有父结点；若k＞1，则该结点的父结点编号为INT（k/2）。

第二，若2k≤n，则编号为k的结点的左子结点编号为2k；否则该结点无左子结点（显然也没有右子结点）。

第三，若2k＋1≤n，则编号为k的结点的右子结点编号为2k＋1；否则该结点无右子结点。

根据完全二叉树的这个性质，如果按从上到下、从左到右顺序存储完全二叉树的各结点，则很容易确定每一个结点的父结点、左子结点和右子结点的位置。

【真题演练】

1某二叉树共有13个结点，其中有4个度为1的结点，则叶子结点数为（　　）。[2014年3月真题]

A．5

B．4

C．3

D．2

【答案】A

【解析】对任何一棵二叉树来说，度为0的结点，即叶子结点，总是比度为2的结点多一个。所以可设叶子结点个数为n，则度为2的结点个数为n-1。13=n+4+n-1，得n=5。答案选择A选项。

2某二叉树中有15个度为1的结点，16个度为2的结点，则该二叉树中总的结点数为（　　）。[2014年9月真题]

A．32

B．46

C．48

D．49

【答案】C

【解析】在树结构中，一个结点所拥有的后继个数称为该结点的度。由二叉树的基本性质可得，对于任何的二叉树，叶子结点总是比度为2的结点多一个。因为度为2的结点有16个，所以叶子结点个数为17，因此结点总数为16+17+15=48。答案选择C选项。

3某二叉树中共有935个结点，其中叶子结点有435个，则该二叉树中度为2的结点个数为（　　）。[2014年3月真题]

A．64

B．66

C．436

D．434

【答案】D

【解析】在树结构中，一个结点所拥有的后件个数称为该结点的度。对于任何一棵二叉树来说，度为0的结点总是比度为2的结点多一个。叶子结点有435个，则度为2的结点为434。答案选择D选项。

4深度为7的完全二叉树中共有125个结点，则该完全二叉树中的叶子结点数为（　　）。[2014年9月真题]

A．62

B．63

C．64

D．65

【答案】B

【解析】定义一棵树的根结点所在的层次为1，其他结点所在的层次等于它的父结点所在的层次加1，树的最大层次称为树的深度。完全二叉树指除最后一层外，每一层上的结点数均达到最大值，在最后一层上只缺少右边的若干结点。本题中，前6层是满二叉树，结点个数为2⁶-1=63，所以第7层有125-63=62个叶子结点，分别挂在第6层的左边62个结点上，所以第6层的最后1个结点为叶子结点，该完全二叉树共有62+1=63个叶子结点。答案选择B选项。

【考点3】二叉树的存储结构

（1）在计算机中，二叉树采用链式存储结构。

（2）用于存储二叉树中各元素的存储结点由两部分组成：

①数据域

②指针域

【真题演练】

下列叙述中正确的是（　　）。[2014年9月真题]

A．结点中具有两个指针域的链表一定是二叉链表

B．结点中具有两个指针域的链表可以是线性结构，也可以是非线性结构

C．二叉树只能采用链式存储结构

D．循环链表是非线性结构

【答案】B

【解析】A项错误，具有两个指针域的链表可能是双向链表，也可能是二叉链表，其中双向链表是线性结构，二叉树为非线性结构；B项正确，如双向链表是线性结构，二叉树为非线性结构，两者结点中均有两个指针域；C项错误，二叉树通常采用链式存储结构，也可采用其他结构；D项错误，循环链表是线性结构，逻辑概念线性非线性与实际存储结构无关。答案选择B选项。

【考点4】二叉树的遍历

二叉树的遍历是指不重复地访问二叉树中的所有结点。在遍历二叉树结点中遵循先左后右的原则。二叉树的遍历可分为三种：

（1）前序遍历（DLR）

首先访问根结点，然后遍历左子树，最后遍历右子树；并且，在遍历左、右子树时，仍然先访问根结点，然后遍历左子树，最后遍历右子树。该过程是一个递归的过程。

（2）中序遍历（LDR）

首先遍历左子树，然后访问根结点，最后遍历右子树；并且，在遍历左、右子树时，仍然先遍历左子树，然后访问根结点，最后遍历右子树。该过程是一个递归的过程。

（3）后序遍历（LRD）

首先遍历左子树，然后遍历右子树，最后访问根结点，并且，在遍历左、右子树时，仍然先遍历左子树，然后遍历右子树，最后访问根结点。该过程是一个递归的过程。

【注意】

①如果知道了某二叉树的前序序列和中序序列，则可以唯一地恢复该二叉树。

②如果知道了某二叉树的后序序列和中序序列，则可以唯一地恢复该二叉树

③如果只知道某二叉树的前序序列和后序序列，是不能唯一恢复该二叉树的。

【真题演练】

1设二叉树如下：

则后序遍历为（　　）。[2014年9月真题]

A．ABDEGCFH

B．DBGEAFHC

C．DGEBHFCA

D．ABCDEFGH

【答案】C

【解析】后序遍历，先访问左子树，再访问右子树，最后访问根结点。法一：本题中，树不为空，所以先后序遍历左子树，得DGEB，再后序遍历右子树，得HFC，最后访问根结点。所以该二叉树的后序序列为DGEBHFCA。法二：由后序遍历的过程知，树的根结点一定是最后遍历到，即A结点一定在遍历序列的最后，答案选择C选项。

2某二叉树的前序序列为ABCD，中序序列为DCBA，则后序序列为（　　）。[2014年9月真题]

A．BADC

B．DCBA

C．CDAB

D．ABCD

【答案】B

【解析】由前序序列ABCD得A为根结点，又因为中序序列为DCBA，所以DCB是A的左子树。同理可得B是CD的根结点，DC是B的左子树，C是D的根结点，所以可以确定二叉树的形状，得后序序列为DCBA。答案选择B选项。