1.1.5 树与二叉树

本节要求考生掌握树和二叉树的基本定义，重点考查二叉树的基本性质和二叉树的遍历。

1.树的定义

树是由n（n≥0）个节点组成的有限集合。若n=0，称为空树；若n＞0，则：

1）有一个特定的称为根（Root）的节点。它只有直接后继节点，而没有直接前驱节点。

2）除根节点以外的其他节点可以划分为m（m≥0）个互不相交的有限集合T0,T1,…,Tm-1，每个集合Ti（i=0,1,…,m-l）又是一棵树，称为根的子树；每棵子树的根节点有且仅有一个直接前驱节点，但可以有0个或多个直接后继节点。

如图1-6所示是一棵树的示例。

2.二叉树的定义及其性质

二叉树（Binary Tree）是由n（n≥0）个节点的有限集合构成，此集合或者为空集，或者由一个根节点及两棵互不相交的左右子树组成，并且左右子树都是二叉树，如图1-7所示。二叉树可以是空集合，根可以有空的左子树或空的右子树。

（1）二叉树的特点

二叉树具有以下两个特点：

1）非空二叉树只有一个根节点。

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

在二叉树中，一个节点可以只有左子树而没有右子树，也可以只有右子树而没有左子树。当一个节点既没有左子树也没有右子树时，该节点即为叶子节点。

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

1）满二叉树：除最后一层外，每一层上的所有节点都有两个子节点，如图1-8所示。

2）完全二叉树：除最后一层外，每一层上的节点数均达到最大值；在最后一层上只缺少右边的若干节点，如图1-9所示。

如果有一棵具有n个节点的深度为k的完全二叉树，则它的每一个节点都与深度为k的满二叉树中编号为1~n的节点一一对应。

（3）二叉树的基本性质

性质1：在二叉树的第k层上至多有2k-1个节点（k≥1）。

性质2：深度为m的二叉树至多有2m-1个节点。

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

性质4：具有n个节点的完全二叉树的深度至少为【log2n】+1，其中【log2n】表示log2n的整数部分。

性质5：具有n个节点的完全二叉树深度为【log2n】+1或【log2（n+1）】。

性质6：如果对一棵有n个节点的完全二叉树的节点按层序编号（从第1层到第【log2n】+1层，每层从左到右），则对任一节点i（1≤i≤n）有：

1）如果i=1，则节点i无双亲，是二叉树的根；如果i>1，则其双亲是节点【i/2】。

2）如果2i≤n，则节点i为叶子节点，无左孩子；否则，其左孩子是节点2i。

3）如果2i+1≤n，则节点i无右孩子；否则，其右孩子是节点2i+1。

（4）二叉树的存储结构

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

3.二叉树的遍历

所谓遍历二叉树，就是遵从某种次序，访问二叉树中的所有节点，使得每个节点仅被访问一次。

（1）前序遍历

前序遍历是指在访问根节点、遍历左子树与遍历右子树这三者中，首先访问根节点，然后遍历左子树，最后遍历右子树；并且，在遍历左右子树时，仍然先访问根节点，然后遍历左子树，最后遍历右子树。图1-10中的二叉树，前序遍历序列：ABCDEF。

（2）中序遍历

中序遍历是指在访问根节点、遍历左子树与遍历右子树这三者中，首先遍历左子树，然后访问根节点，最后遍历右子树；并且，在遍历左、右子树时，仍然先遍历左子树，然后访问根节点，最后遍历右子树。图1-10中的二叉树，中序遍历序列：CBDAEF。

（3）后序遍历

后序遍历是指在访问根节点、遍历左子树与遍历右子树这三者中，首先遍历左子树，然后遍历右子树，最后访问根节点；并且，在遍历左、右子树时，仍然先遍历左子树，然后遍历右子树，最后访问根节点。图1-10中的二叉树，后序遍历序列：CDBFEA。

例，已知二叉树的中序遍历序列为ABCDEFG，后序遍历序列为BDCAFGE，则前序遍历序列是什么？

解题过程如下：

1）从后序中，可以先得到根节点是E，然后再看中序的序列：ABCDEFG，可以发现ABCD位于根节点的左边，而FG位于根节点的右边，于是得到图1-11所示的图形。

2）先来看ABCD这部分，然后看后序序列，在后序序列中有BDCA这一部分，可以确定A是这部分的根，再看中序序列中的ABCD，发现BCD都在A的后面。因此，可以画出如图1-12所示的图形。

3）再看BCD这部分，从后序中看到的顺序是BDC，所以C是这部分的根节点，中序序列是BCD，可以断定B在C的左边，D在C的右边。这样，得到如图1-13所示的图形。

4）再看看右边的FG这部分，从后序序列FG和中序FG中，可以推出，G是这部分的根节点，而F位于G的左边。得到如图1-14所示的图形。

5）根据以上步骤合成一个二叉树，如图1-15所示。

6）写出前序遍历序列：EACBDGF。