大学计算机基础：二叉树的性质与遍历方法

1.基本概念

二叉树（Binary Tree）是每个节点最多有两个子树的树结构。通常子树被称作“左子树”（left subtree）和“右子树”（right subtree）。

二叉树的特点：

·二叉树不存在度大于2的节点。

·二叉树的子树有左右之分，次序不能颠倒。

如图9-26所示中，树1和树2是同一棵树，但它们是不同的二叉树。

图9-26　左子树和右子树

1）斜树

所有的节点都只有左子树的二叉树叫左斜树。所有的节点都只有右子树的二叉树叫右斜树。这两者统称为斜树。

斜树每一层只有一个节点，节点的个数与二叉树的深度相同。其实斜树就是线性表结构。

2）满二叉树

在一棵二叉树中，如果所有分支节点都存在左子树和右子树，并且所有叶子都在同一层上，这样的二叉树称为满二叉树。

满二叉树具有如下特点：

·叶子只能出现在最下一层

·非叶子节点的度一定是2

·同样深度的二叉树中，满二叉树的节点个数最多，叶子数最多。

3）完全二叉树

若设二叉树的高度为h，除第h层外，其他各层（1～h—1）的节点数都达到最大个数，第h层有叶子节点，并且叶子节点都是从左到右依次排布，这就是完全二叉树。

完全二叉树的特点：

·叶子节点只能出现在最下两层

·最下层叶子在左部并且连续

·同样节点数的二叉树，完全二叉树的深度最小

4）平衡二叉树

平衡二叉树又被称为AVL树（区别于AVL算法），它是一棵二叉排序树，且具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树，如图9-27所示。

图9-27　特殊二叉树

2.二叉树的性质

1.在二叉树的第i层上至多有2i-1个节点（i＞=1）。

2.深度为k的二叉树至多有2k—1个节点（k＞=1）。

3.对于任意一棵二叉树，度为0的节点（即叶子节点）总比度为2的节点多一个。

4.具有n个节点的完全二叉树的深度为「log2n」+1（「x」表示不大于x的最大整数）。

5.如果对一棵有n个节点的完全二叉树的节点按层序编号（从第一层到第「log2n」+1层，每层从左到右），对任一节点i（1≤i≤n）有：

·若i=1，则节点i是二叉树的根，无双亲；如i＞1，则其双亲是节点「i/2」。(www.xing528.com)

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

·若2i+1＞n，则节点i无右孩子；否则其右孩子是节点2i+1。

3.二叉树的实现

二叉树是一种特殊的树，它的存储结构相对于前面谈到的一般树的存储结构要简单一些。

1）顺序存储

二叉树的顺序存储结构就是用一维数组来存储二叉树中的节点。不使用数组的第一个位置。节点的存储位置反映了它们之间的逻辑关系：位置k的节点的双亲节点的位置为「k/2」，它的两个孩子节点的位置分别为2k和2k+1，如图9-28所示。

图9-28　二叉树的顺序存储

一棵深度为k的右斜树，只有k个节点，但却需要分配2k-1个顺序存储空间。所以顺序存储结构一般只用于完全二叉树。

2）链式存储

二叉树每个节点最多有两个孩子，所以为它设计一个数据域和两个指针域即可。我们称这样的链表为二叉链表。其结构如图9-29所示：

图9-29　二叉树的链式存储

4.二叉树的遍历

二叉树的遍历（traversing binary tree）是指从根节点出发，按照某种次序依次访问二叉树中所有节点，使得每个节点被访问一次且仅被访问一次。

二叉树的遍历主要有四种：前序遍历、中序遍历、后序遍历和层序遍历。

1）前序遍历

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

对于图9-30，三处使用前序遍历，则顺序为：ABEFCGDHIJ

图9-30　二叉树的遍历

2）中序遍历

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

对于右图，使用中序遍历，则顺序为：EFBGCHIJDA

3）后序遍历

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

对于右图，使用后序遍历，则顺序为：FEGJIHDCBA

注意：

·已知前序遍历和中序遍历，可以唯一确定一棵二叉树。

·已知后序遍历和中序遍历，可以唯一确定一棵二叉树。

·已知前序遍历和后序遍历，不能确定一棵二叉树。

如前序遍历是ABC，后序遍历是CBA的二叉树，各图9-31所示：

图9-31　前序遍历推导后序遍历