[数据结构] 06 - 1 - 树和二叉树

6.1 - 树

一、树的基础知识

(一)树的定义

树(Tree)是 n (n ≥ 0) 个节点的有限集。

树可以为空,n = 0 的树称为空树。

在任意一棵非空树中:

  • 有且仅有一个特定的称为根(Root)的节点;
  • 当 n > 1 时,其余节点可分为 m (m > 0) 个互不相交的有限集 T1 …… Tn,其中每一个集合本身又是一棵树,被称为根的子树(SubTree)。

(二)树的结点

1. 结点的度

结点拥有的子树数量称为结点的度(Degree)。

2. 结点的分类(根据度分)

  • 度为 0 的结点:称为叶结点(Leaf)或终端结点;
  • 度不为 0 的结点:称为非终端结点或分支结点。
  • 除根节点外的分支结点,也称为内部结点;
  • 树的度是树内各结点的度的最大值。

(三)树的结点的关系

1. 关于树中层次、高度等的描述

  • 层次(Level):从根开始,根为第 1 层,根的子结点为第 2 层,依此类推;
  • 深度(Depth):通常指从根结点到某结点的路径长度或层数;
  • 高度(Height):通常指从某结点到其最远叶子结点的最长路径长度或层数;
  • 路径(Path):从一个结点到另一个结点所经过的结点序列;
  • 路径长度(Path Length):路径上经过的边数。

2.结点的关系

  • 孩子(Child):某结点的子树是该节点的孩子;
  • 双亲(Parent):B 树是 A 结点的子树,A 是 B 的双亲;
  • 兄弟(Sibling):同一个双亲结点的子结点;
  • 祖先(Ancestor):从根到该结点所经分支上的所有结点;
  • 子孙(Descendent):以某结点为根的子树中的任一结点。

(四)树的分类

  • 有序树(Ordered Tree):子树有先后次序,不可随意调换;
  • 无序树(Unordered Tree):子树之间无顺序关系,交换后仍是同一棵树;
  • 森林(Forest):m 棵互不相交的树的集合。一棵树去掉根节点后,其子树的集合就是一个森林。

二、树 ADT

(一)数据对象和数据关系

数据对象:

  • 元素类型:由 n 个节点(Node)组成,每个节点包含一个数据元素(或称为值)和若干指向其子树的指针;
  • n = 0 时,称为空树,数据对象为空集;
  • n > 0 时,数据对象中存在唯一的根节点,无前驱。

数据关系:

树是一种层次结构,节点之间存在“一对多”的关系。

  • 每个节点(除根节点外)有且仅有一个前驱(双亲节点),但可以有 0 个或多个后继(子节点);

(二)基本操作示例

树的基本操作示例表
典型函数定义操作中文名操作简单描述
isEmpty(T)判空操作判断树 T 是否为空树
getRoot(T)取根节点返回树 T 的根节点(空树时返回空/异常)
getParent(T, v)取父节点(双亲节点)返回节点 v 的父节点(根节点无父节点)
getFirstChild(T, v)取第一个孩子返回节点 v 的第一个子节点
getNextSibling(T, v)取下一个兄弟返回节点 v 的下一个兄弟节点
getChild(T, v, i)取第 i 个孩子返回节点 v 的第 i 个子节点
getDegree(T, v)取节点度返回节点 v 的子节点个数
getDepth(T)求树深度返回树 T 的最大层次数(深度/高度)
getNodeCount(T)求节点数返回树 T 中节点的总数
getLeafCount(T)求叶子数返回树 T 中叶子节点的个数
locate(T, e)查找节点查找数据元素为 e 的节点并返回其位置/引用
insertChild(T, v, i, c)插入子树将子树 c 插入为节点 v 的第 i 个孩子
deleteChild(T, v, i)删除子树删除节点 v 的第 i 个孩子及其子树
traverse(T, visit)遍历操作按某种次序(先序/后序/层次等)访问树中所有节点
preOrder(T, visit)先序遍历先访问根,再依次先序遍历各子树
postOrder(T, visit)后序遍历先依次后序遍历各子树,再访问根
levelOrder(T, visit)层次遍历按层次从上到下、从左到右访问节点
clear(T)清空操作删除树中所有节点,使 T 变为空树
destroy(T)销毁操作释放树 T 占用的全部存储空间

树和线性表不同,所以遍历方式有很多,将在 06-2 中介绍。


三、树的存储

树有三种主要的表示方法:

表示法核心思想逻辑存储结构优点缺点
双亲表示法记录双亲结点的数组下标。连续数组(包含 data 和 parent 字段)。寻找双亲极快寻找结点的孩子需要遍历整个数组。
孩子表示法数组存结点,每个结点附带一个单链表记录其所有孩子。结构体数组 + 孩子结点单链表。寻找所有孩子非常方便寻找结点的双亲比较麻烦,需要遍历全树的所有链表。
孩子兄弟表示法两个指针,分别指向第一个孩子和下一个右兄弟。二叉链表(包含 data、firstchild、rightsibling)。将任意普通树转换为了二叉树,利于复用二叉树的操作算法找结点的双亲不够直接(可额外增加 parent 指针优化)。

(一)双亲表示法

用一组连续空间(数组)存储结点,每个结点中附带一个指示其双亲结点在数组中下标的字段。根结点的双亲下标设为 -1。

#define MAX_TREE_SIZE 100
typedef int ElemType;
 
typedef struct {
    ElemType data;      // 数据元素
    int parent;         // 双亲位置下标(根为 -1)
} PTNode;
 
typedef struct {
    PTNode nodes[MAX_TREE_SIZE];  // 结点数组
    int n;                        // 结点数
} PTree;
例子:用双亲表示法表示一个树结构

下标dataparent
0A-1
1B0
2C0
3D1
4E2
5F2
6G3
7H3
8I3
9J4

优缺点:

  • 优点:可快速找某个结点的双亲结点,同时为 O(1);
  • 缺点:找孩子结点,必须遍历整个数组。

(二)孩子表示法

把每个结点的孩子结点排列起来,看成线性表,用单链表存储;n 个结点有 n 个孩子链表;再用一个数组存放每个结点的头指针(和数据)。

#define MAX_TREE_SIZE 100
typedef int ElemType;
 
// 孩子链表中的结点
typedef struct CNode {
    int child;              // 孩子结点在表头数组中的下标
    struct CNode *next;     // 指向下一个孩子
} CNode;
 
// 表头数组的元素
typedef struct {
    ElemType data;          // 数据元素
    CNode *firstchild;      // 孩子链表头指针
} CTBox;
 
typedef struct {
    CTBox nodes[MAX_TREE_SIZE];  // 表头数组
    int n;                       // 结点数
} CTree;

包含双亲数据的孩子表示法

特点:

  • 找孩子很方便(沿着孩子链表遍历)。
  • 找双亲不方便,需要遍历所有孩子链表。
  • 可以在此基础上再加一个 parent 字段,变成"双亲孩子表示法",兼顾两者。

(三)孩子兄弟表示法(二叉链表表示法)

每个结点设两个指针,一个指向"第一个孩子",另一个指向"下一个兄弟"。这种表示法把任意树转换成二叉树结构。

二叉树的形式

typedef int ElemType;
 
typedef struct CSNode {
    ElemType data;                        // 数据元素
    struct CSNode *firstchild;            // 指向第一个孩子
    struct CSNode *nextsibling;           // 指向下一个兄弟
} CSNode, *CSTree;

特点:

  • 结构最灵活,结点数不受固定数组大小限制,便于动态分配。
  • 找孩子:通过 firstchild 再沿 nextsibling 遍历兄弟。
  • 找双亲:需要从根开始遍历,不太方便。
  • 任意树都可唯一转换为二叉树,因此常与"树与二叉树转换"结合使用,是最常用的树存储结构之一。

6.2 - 二叉树

一、二叉树基础知识

(一)二叉树定义

二叉树(Binary Tree)是 n(n≥0)n (n ≥ 0) 个结点的有限集合,该集合或者为空集(空二叉树),或者是由一个根节点和两棵互不相交的、分别称为根节点的左子树和右子树的二叉树组成的。

二叉树的定义是一种递归定义。

(一)二叉树的特点

  • 度严格不超过 2,只能是 0、1 或 2;
  • 左右子树的次序严格固定,也就是交换了左、右子树的二叉树不是原来的二叉树;
  • 二叉树有五种基本形态:
    • 空二叉树(没有任何结点);
    • 只有一个根结点;
    • 只有左子树(右子树为空);
    • 只有右子树(左子树为空);
    • 空二叉树(左子树和右子树均为空);

(三)特殊二叉树

斜树(Skewed Tree)

  • 左斜树:所有结点都只有左子树。
  • 右斜树:所有结点都只有右子树。
  • 本质:结构退化为线性表,但不建议直接说线性表是树的一种特殊形式,可以说它是树的一种受限特例。

满二叉树(Full Binary Tree)

  • 定义:所有分支结点都有左孩子和右孩子,所有的叶子结点都在同一层上;
  • 特征:叶子结点只能在最下层,非叶子结点的度都是 2;在同样深度的二叉树中,满二叉树的结点数、叶子数都最多。

满二叉树

完全二叉树(Complete Binary Tree)

  • 定义:对具有 n 个结点的二叉树按层序编号(从上到下,从左到右)。如果编号为 i 的结点,与同深度的满二叉树中编号为 i 的结点位置完全一致,则称其为完全二叉树。
  • 直观理解:在满二叉树的基础上,只允许在最后一层的最右侧缺失几个连续结点。下图中,如果编号 1~9 的结点有缺失的话,它就是不能算作完全二叉树的。
  • 特征:叶子节点只能在最下两层;最下层的叶子节点是靠左连续排列的;至多存在一个度为 1 的结点,且该结点的孩子只能是左孩子(图中 5)。

一般用数组实现时,下标为 0 的位置空着不用(或者存储树的结点数、伪头节点),从下标为 1 的地方开始。

完全二叉树

(四)二叉树的性质

二叉树有五个主要的性质,了解并记住这些性质可以更好地利用二叉树。

性质一

二叉树在第 ii 层至多有 2i−12^{i - 1} 个结点;

  • 例如:第一层 1 个、第二层 2 个、第三层 4 个、第四层 8 个……
  • 这个很显然,不需要推导。

性质二

深度为 k 的二叉树至多有 2k−12^k - 1 个结点;

  • 例如:一层最多 1 个、两层最多 1+2=3 个、三层最多 1+2+4=7 个……
  • 因为是“至多”,所以算的其实是满二叉树的结点数;
  • 推导:由 性质 1 通过等比数列求和得到。

性质三

对任何一棵二叉树 T,如果其终端(叶子)节点数为 n0n_0,度为 2 的节点数为 n2n_2,则 n0=n2+1n_0=n_2+1;

  • 字面意思:叶子节点的数量永远比有两个孩子的结点多 1;

推导:

假设一棵二叉树中,度为 p 的结点(叶子)数量为 npn_p、总结点数为 nn;

  • 从【结点总数】的角度看,必然有 n=n0+n1+n2n = n_0 + n_1 + n_2;
  • 从【树的边数(分支数)】的角度看:
    • 从下往上看:除了根节点外,其余每个结点( n−1n - 1 个)上方都有一条边连向它,这么看总边数是 n−1n - 1;
    • 从上往下看:每个结点都向下发出 0 / 1 / 2 条边,总边数就是 0⋅n0+1⋅n1+2⋅n2=n1+2n20 ⋅ n_0 + 1 ⋅ n_1 + 2 ⋅ n_2 = n_1 + 2n_2。
  • 另两个式子相等,即 n−1=n1+2n2n - 1 = n_1 + 2n_2;
  • 其中的 n 用上面的式子替换,就能得到 n0+n1+n2−1=n1+2n2n_0 + n_1 + n_2 - 1 = n_1 + 2n_2,化简后得到 n0=n2+1n_0=n_2+1;

性质四

具有 n 个结点的完全二叉树的深度为 ⌊log⁡2n⌋+1\lfloor\log_2 n\rfloor + 1。

  • 类似性质 2 的一个反向版,但性质 4 只针对完全二叉树;

推导:

  • 上界:一颗深度为 k 的完全二叉树,第 k 层可以不满,由性质 2 有 n≤2k−1n \le 2^k-1,也就是 n<2kn < 2^k;
  • 下界:因为前 k−1k -1 层必须满,所以 n>2k−1−1n \gt 2^{k-1}-1,同理 n≥2k−1n \ge 2^{k-1};
  • 合起来看,2k−1≤n<2k2^{k−1}≤n<2^k,两边同时取对数,得到 k−1≤log2​n<kk−1≤log_2​n<k;
  • 由于深度 k 是整数,所以 k−1=⌊log⁡2n⌋k - 1 = \lfloor\log_2 n\rfloor。

性质五

用一句话概括:编号 i 的父结点是 ⌊i/2⌋\lfloor{i / 2}\rfloor,左孩子是 2i2i,右孩子是 2i+12i + 1,编号超过 n 就是孩子不存在。

对于一棵有 n 个结点的完全二叉树,若按层序编号(从 1 到 n),结点编号就对应数组下标,那么对于任意结点 ii:

  • 双亲结点位置:
    • 若 i=1i = 1,则结点 ii 是根结点,无双亲。
    • 若 i>1i > 1,则其双亲结点的编号为 ⌊i/2⌋\lfloor i / 2 \rfloor(向下取整,即整除 i/2i / 2)。
  • 左孩子位置:
    • 若 2i>n2i > n,则结点 ii 无左孩子(说明 ii 是叶子结点,因为对于完全二叉树,如果没有左孩子,也就一定没有右孩子)。
    • 若 2i≤n2i \le n,则其左孩子结点的编号为 2i2i。
  • 右孩子位置:
    • 若 2i+1>n2i + 1 > n,则结点 ii 无右孩子。
    • 若 2i+1≤n2i + 1 \le n,则其右孩子结点的编号为 2i+12i + 1。

性质 5 是数组实现堆(Heap)数据结构(如大顶堆、小顶堆及堆排序)的核心理论依据,无需指针即可直接利用下标计算出左右孩子和双亲结点。以后会详细介绍。


二、二叉树的存储

在上一篇文章【6.3 - 树的存储】中,我们已经了解过,存储树这种一对多的关系结构是比较复杂的。而二叉树是一种特殊的树,有比一般的树更好存储方式。

(一)顺序存储

对每个节点位置进行层序编号,就可以实现顺序存储,无论是否是完全二叉树都可以顺序存储,没有结点的位置留空即可。

但是,顺序存储一般只用于完全二叉树,因为非完全二叉树使用顺序存储会造成空间浪费(最极端的例子是右斜树)。

(二)二叉链表

二叉树的每个结点最多有两个孩子,所以可让每个结点包含一个数据域和两个指针域,分别存储该结点的数据和其左、右孩子的地址。

typedef struct BiTNode
{
    TElemType data;
    struct BiTNode *lchild,*rchild;
} BiTNode,*BiTree;