树结构-二叉树

2023-10-09 16:33:58

0 前言

树形结构是一类重要的非线性数据结构。其中以树和二叉树最为常见，直观来看，树是以分支关系定义的层次结构。树结构在客观世界中广泛存在，如人类社会的族谱和各种社会组织结构都可以用树来形象表示。树在计算机领域中也得到广泛应用，如在编译程序时，可用树来表示源程序的语法结构。又如在数据库系统中，树形结构也是信息的重要组织形式之一。本文主要讨论二叉树的存储结构及其各种操作。

1 二叉树基本概念

1.1 二叉树的定义

二叉树(Binary Tree) 是一张常见的树型结构。

定义：有且只有一个根结点，除根结点外，每个结点只有一个父结点，最多只有两颗子树（即二叉树中不存在度大于2的结点），并且结点的子树有左右之分，其次序不能任意颠倒。

1.2 二叉树的5种基本形态

1.3 二叉树的基本性质

二叉树具有下列重要性质。

性质1）在二叉树的第 i 层上至多有个结点。(i ≥ 1)

性质2）深度为 k 的二叉树至多有个结点。(k ≥ 1)

性质3）对任何一棵二叉树 T，如果其终端结点数为，度为 2 的结点数为，则 = + 1。终端结点也称为叶子结点，是指没有子树的结点。

性质3指出，一个二叉树，叶子结点数 = 度为2的结点数 + 1

满二叉树：一棵深度为 k 且有个结点的二叉树称为满二叉树。

这种树的特点是每一层上的结点数都达到最大结点数，即第 i 层上有个结点数。

如下图 6.4(a) 所示是一棵深度为 4 的满二叉树。

完全二叉树：对一棵满二叉树的结点进行连续编号，约定编号从根结点起，自上而下，自左而右，由此可引出完全二叉树的定义。

深度为 k，有 n 个结点的二叉树，当且仅当其每一个结点都与深度为 k 的满二叉树中编号从 1 至 n 的结点一一对应时，称之为完全二叉树。

这种树的特点：（1）叶子结点只可能在层次最大的两层上出现；（2）对任一结点，若其右分支下的子孙结点的最大层次为 L，则其左分支下的子孙结点的最大层次必为 L 或 L+1。

如下图 6.4(b) 所示为一棵深度为 4 的完全二叉树。

完全二叉树的两个重要性质:

性质4）具有 n 个结点的完全二叉树的深度为

证明：假设完全二叉树深度为 k，则根据性质2 和完全二叉树的定义有：

或

于是，因为 k 是整数，所以。

性质5）如果对一棵有 n 个结点的完全二叉树（其深度为）的结点按层序编号（从第 1 层到第层，每层从左到右），则对任一结点 i（），有：

（1）如果 i = 1，则结点 i 是二叉树的根结点，无双亲；如果 i > 1，则其父结点 FATHER(i) 的编号为。

（2）如果 2i > n，则结点 i 无左孩子（结点 i 为叶子结点）；否则其左孩子结点 LChild(i) 的编号为 2i。

（3）如果 2i+1 > n，则结点无右孩子；否则其右孩子结点RChild(i) 的编号为 2i+1。

分析如下：

（1）i = 1时，由完全二叉树的定义可知，其左孩子是结点 2。若 n < 2，即不存在结点2，此时结点 i 无左孩子。结点 i 的右孩子也只能是结点 3，若结点 3 不存在，即 n < 3，此时结点 i 无右孩子。

（2）对于 i > 1 可分为两种情况讨论：

① 设第 j（）层的第一个结点的编号为 i（由二叉树的定义和性质2可知），则其左孩子必为第 j+1 层的第一个结点，其编号为，若 2i > n，则结点 i 无左孩子；其右孩子必为第 j+1 层的第二个结点，起编号为 2i+1，若 2i+1 > n，则其无右孩子。

② 假设第 j（）层上某个结点的编号为 i（），且 2i+1 < n，则其左孩子为 2i，右孩子为 2i+1。

如果编号 i+1 的结点是编号为 i 的结点的右兄弟（图6.5(a)）或者堂兄弟（图6.5(b)），若它有左孩子，则编号必为 2(i+1)=2i+2；若它有右孩子，则其编号必为 2(i+1)+1=2i+3。

1.4 二叉树的存储结构

1. 顺序存储结构

// - - - - - 二叉树的顺序存储表示 - - - - -
#define MAX_TREE_SIZE  100                  //二叉树的最大结点数
typedef TElemType SqBiTree[MAX_TREE_SIZE];  //0号单元存储根节点
SqBiTree bt;

按照顺序存储结构的定义，在此约定，用一组地址连续的存储单元依次自上而下，自左而右存储完全二叉树上的结点元素，即将完全二叉树上编号为 i 的结点元素存储在如上定义的一个一维数组中下标为 i-1 的位置中。

例如，在图 6.6(a) 所示为上图 6.4(b) 所示完全二叉树的顺序存储结构。对于一般二叉树，则应该将其每个结点与完全二叉树上的结点相对照，存储在一维数组的对应位置中，如图 6.6(b) 所示，图中以 "0" 表示不存在此结点。由此可见，这种顺序存储结构仅适用于完全二叉树。因为，在最坏的情况下，一个深度为 k 且只有 k 个结点的单支树（树中不存在度为 2 的结点）却需要长度为的一维数组。

2. 链式存储结构

由二叉树的定义可知，二叉树的结点（如图 6.7(a)所示）由一个数据元素和分别指向其左、右子树的两个分支构成，则表示二叉树的链表中的结点至少包含了 3 个域：数据域和左、右指针域，如图 6.7(b)所示。有时，为了便于找到结点的双亲，则还可在结点结构中增加一个指向其双亲结点的指针域，如图 6.7(c)所示。

利用这两种结点结构所得的二叉树的存储结构分别称之为二叉链表和三叉链表，如图 6.8 所示。

链表的头指针指向二叉树的根节点。容易证得，在含有 n 个结点的二次链表中有 n+1 个空链域。我们可以利用这些空链域存储其他有用的信息，从而得到另一种链式存储结构——线索链表。

以下是二叉链表的定义和部分基本操作的函数原型说明：

// - - - - - 二叉树的二叉链表存储表示 - - - - -
typedef struct BiTNode {
	TElemType       data;               //数据域
	struct BiTNode  *lchild, *rchild;   //左右孩子指针
}BiTNode, *BiTree;

typedef int Status;
// - - - - - 基本操作的函数原型说明(部分) - - - - -
Status CreateBitTree(BiTree T);
  //按先序次序输入二叉树中结点的值(如一个字符)，空格字符表示空树。
  //构造二叉链表表示的二叉树T
Status PreOrderTraverse(BiTree T, Status (*Visit)(TElemType e));
  //采用二叉链表存储结构，Visit 是对结点操作的应用函数。
  //先序遍历二叉树T，对每个结点调用函数 Visit 一次且仅一次。
  //一旦 Visit()失败，则操作失败
Status InOrderTraverse(BiTree T, Status (*Visit)(TElemType e));
  //采用二叉链表存储结构，Visit 是对结点操作的应用函数。
  //中序遍历二叉树T，对每个结点调用函数 Visit 一次且仅一次。
  //一旦 Visit()失败，则操作失败
Status PostOrderTraverse(BiTree T, Status (*Visit)(TElemType e));
  //采用二叉链表存储结构，Visit 是对结点操作的应用函数。
  //后序遍历二叉树T，对每个结点调用函数 Visit 一次且仅一次。
  //一旦 Visit()失败，则操作失败
Status LevelOrderTraverse(BiTree T, Status (*Visit)(TElemType e));
  //采用二叉链表存储结构，Visit 是对结点操作的应用函数。
  //层序遍历二叉树T，对每个结点调用函数 Visit 一次且仅一次。
  //一旦 Visit()失败，则操作失败

在不同的存储结构中，实现二叉树的操作方法也不同，如找结点 x 的双亲结点 PARENT(T, e)，在三叉链表中很容易实现，而在二叉链表中则需要从根结点出发进行逐一巡查。由此，在具体应用中采用什么存储结构，除根结点二叉树的形态之外，还应考虑需进行何种操作。

2 遍历二叉树

遍历二叉树(Traversing binary tree)，即如何按某条搜索路径巡访二叉树中的每一个结点，使得每一个结点均被访问一次，而且仅被访问一次。“访问” 的含义，可以是对结点作各种处理，如输出结点的信息等。

码农公寓