考点6 树和二叉树

1.树的基本概念

树是一种简单的非线性结构，直观地来看树是以分支关系定义的层次结构。树是由n（n≥0）个节点构成的有限集合，当n=0时，树称为空树。当n≠0时，树中的节点应该满足以下两个条件：

●有且仅有一个没有前驱的节点称之为根；

●其余节点分成m（m＞0）个互不相交的有限集合 T1,T2,…,Tm，其中每一个集合又都是一棵树，称T1,T2,…,Tm为根节点的子树。

在树的结构中主要涉及下面几个概念。

●每一个节点只有一个前件，称为父节点，没有前件的节点只有一个，称为树的根节点，简称树的根。

●每一个节点可以有多个后件，称为该节点的子节点。没有后件的节点称为叶子节点。

●一个节点所拥有的后继个数称为该节点的度。

●所有节点最大的度称为树的度。

●树的最大层次称为树的深度。

2.二叉树及其基本性质

（1）二叉树的定义。

二叉树是一种非线性结构，是一个有限的节点集合，该集合或者为空，或者由一个根节点及其两棵互不相交的左右二叉子树所组成。当集合为空时，称该二叉树为空二叉树。

二叉树具有以下特点。

●二叉树可以为空，空的二叉树没有节点，非空二叉树有且只有一个根节点。

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

（2）满二叉树和完全二叉树。

满二叉树：除最后一层外，每一层上的所有节点都有两个子节点，即在满二叉树的第k层上有2k-1个节点，且深度为m的满二叉树中有2m-1个节点。

完全二叉树：除最后一层外，每一层上的节点数都达到最大值；在最后一层上只缺少右边的若干节点。

满二叉树与完全二叉树的关系：满二叉树一定是完全二叉树，但完全二叉树不一定是满二叉树。

真考链接

考核概率为100%，本节内容属于必考知识点，特别是关于二叉树的遍历。考生要熟记该考点内容，尤其是二叉树的概念及其相关术语，并掌握二叉树的性质以及二叉树的3种遍历方法。本知识点是数据结构的重要部分。

（3）二叉树的主要性质。

●一棵非空二叉树的第k层上最多有2k-1个节点（k≥1）。

●深度为m的满二叉树中有2m-1个节点。

●对任何一棵二叉树，度为0的节点（即叶子节点）总是比度为2的节点多一个。

●具有n个节点的完全二叉树的深度k为［log2n］+1。

3.二叉树的存储结构

在计算机中，二叉树通常采用链式存储结构，用于存储二叉树中各元素的存储节点由数据域和指针域组成。由于每一个元素可以有两个后件（即两个子节点），所以用于存储二叉树的存储节点的指针域有两个：一个指向该节点的左子节点的存储地址，称为左指针域；另一个指向该节点的右子节点的存储地址，称为右指针域。因此，二叉树的链式存储结构也称为二叉链表。

对于满二叉树与完全二叉树可以按层次进行顺序存储。

4.二叉树的遍历

二叉树的遍历是指不重复地访问二叉树中的所有节点。二叉树的遍历主要是针对非空二叉树的，对于空二叉树，则结束返回。

二叉树的遍历有前序遍历、中序遍历和后序遍历。

（1）前序遍序（DLR）。

首先访问根节点，然后遍历左子树，最后遍历右子树。

（2）中序遍历（LDR）。

首先遍历左子树，然后访问根节点，最后遍历右子树。

（3）后序遍历（LRD）。

首先遍历左子树，然后遍历右子树，最后访问根节点。

小提示

已知一棵二叉树的前序遍历序列和中序遍历序列，可以唯一确定这棵二叉树。已知一棵二叉树的后序遍历序列和中序遍历序列，也可以唯一确定这棵二叉树。已知一棵二叉树的前序遍历序列和后序遍历序列，不能唯一确定这棵二叉树。

真题精选

对如右图中二叉树进行后序遍历的结果为______。

A）ABCDEF

B）DBEAFC

C）ABDECF

D）DEBFCA

【答案】D

【解析】执行后序遍历，依次执行如下操作：

①按照后序遍历的顺序遍历根节点的左子树；

②按照后序遍历的顺序遍历根节点的右子树；

③访问根节点。