数据结构学习笔记（3）——树

机械工业出版社《数据结构与算法——Python语言实现》学习笔记。
画图工具：draw.io

1 树的基本概念

1.1 树的定义和属性

定义

我们将树T定义为存储一系列元素的有限节点集合，这些节点具有parent-children关系并且满足如下属性：

• 如果树T不为空，则它一定具有一个称为**根节点(root)**的特殊节点，并且该节点没有父节点。
• 每个非根节点 $v$v 都具有唯一的父节点 $w$w ，每个具有父节点 $w$w 的节点都是节点 $w$w 的一个孩子。

同一父节点的孩子节点之间是兄弟关系。一个没有孩子的节点 $v$v 称为外部节点（叶子节点）。一个有一个或多个孩子的节点 $v$v 称为内部节点。

边和路径

树 T 的边指的是一对节点 $(u,v)$(u,v) ，$u$u 是 $v$v 的父节点或 $v$v 是 $u$u 的父节点。树 T 当中的路径指的是一系列的节点，这些节点中任意两个连续的节点之间都是一条边。

有序树

如果树中每个节点的孩子节点都有特定的顺序，则称该树为有序树。通常我们按照从左到右的顺序对兄弟节点进行排序。

1.2 树的抽象数据类型

一棵树的位置对象支持如下方法：

• p.element()：返回存储在位置p中的元素。

树的抽象数据类型支持如下访问方法。允许使用者访问一棵树的不同位置：

• T.root()：返回树T的根节点的位置。如果树为空，则返回None。
• T.is_root()：如果位置p是树T的根，则返回True。
• T.parent(p)：返回位置为p的父节点的位置。如果p的位置为树的根节点，则返回None。
• T.num_children(p)：返回位置为p的孩子节点的编号。
• T.children(p)：产生位置为p的孩子节点的一个迭代。
• T.is_leaf(p)：如果位置p没有任何孩子，则返回True。
• len(T)：返回树T所包含的元素的数量。
• T.is_empty()：如果树T不包含任何节点，则返回True。
• T.positions()：生成树T的所有位置的迭代。
• iter(T)：生成树T中存储的所有元素的迭代。

1.3 计算深度和高度

深度定义和算法

• 如果p是根节点，那么p的深度为0
• 否则，p的深度就是其父节点的深度加1

def depth(self, p):
    '''返回位置p处的深度'''
    if self.is_root(p):
        return 0
    else:
        return 1 + self.depth(self.parent(p))

高度定义和算法

• 如果p是一个叶子节点，那么它的高度为0。
• 否则，p的高度是它孩子节点中的最大高度加1。

def _height(self, p):
    '''返回根为p的子树的高度'''
    if self.is_leaf(p):
        return 0
    else:
        return 1 + max(self._height(c) for c in self.children(p))

def height(self, p=None):
    '''返回根为p的子树的高度，如果p=None则返回整个树的高度'''
    if p is None:
        p = self.root()
    return self._height(p) #调用_height()函数

2 二叉树

二叉树是具有以下属性的有序树：

• 每个节点最多有2个孩子节点。
• 每个孩子节点被命名为左孩子或右孩子。
• 对于每个节点的孩子节点，在顺序上，左孩子先于右孩子。

若子树的根为内部节点 $v$v 的左孩子或右孩子，则该子树相应地被称为节点 $v$v 的左子树或右子树。除了最后一个节点的父节点外，若每个节点都有零个或两个子节点，则这样的二叉树被称为完全二叉树（满二叉树）。若二叉树不完全，则称为不完全二叉树。

如图，决策树是一种完全二叉树。

2.1 二叉树的抽象数据类型

在树的基础上，支持三种额外的访问方法：

• T.left(p)：返回 p 左孩子的位置，若 p 没有左孩子，则返回None。
• T.right(p)：返回 p 右孩子的位置，若 p 没有右孩子，则返回None。
• T.sibling(p)：返回 p 兄弟节点的位置，若 p 没有兄弟节点，则返回None。

2.2 二叉树的属性

• 二叉树的 $d$d 层至多有 $2^{d}$2d 个节点

命题： 设 T 为非空二叉树，$n、n_{E}、n_{I}$n、nE​、nI​ 和 $h$h 分别表示 T 的节点数、外部节点数、内部节点数和高度，则 T 具有如下性质：

1. $h+1 \leq n \leq 2^{h+1} -1$h+1≤n≤2h+1−1
2. $1 \leq n_{E} \leq 2^{h}$1≤nE​≤2h
3. $h \leq n_{I} \leq 2^{h} -1$h≤nI​≤2h−1
4. $log(n+1) -1 \leq h \leq n-1$log(n+1)−1≤h≤n−1

若 T 是完全二叉树，则 T 具有如下性质：

1. $2h+1 \leq n \leq 2^{h+1} -1$2h+1≤n≤2h+1−1
2. $h+1 \leq n_{E} \leq 2^{h}$h+1≤nE​≤2h
3. $h \leq n_{I} \leq 2^{h} -1$h≤nI​≤2h−1
4. $log(n+1) -1 \leq h \leq (n-1)/2$log(n+1)−1≤h≤(n−1)/2

完全二叉树中内部节点与外部节点的关系：

命题 在非空完全二叉树 T 中，有 $n_{E}$nE​ 个外部节点和 $n_{I}$nI​ 个内部节点，则有 $n_{E}=n_{I}+1$nE​=nI​+1

3 树的实现

3.1 链式二叉树结构

省略详细代码

链式二叉树性能

操作	运行时间
len, is_empty	O(1)
root, parent, left, right, sibling, children, num_children	O(1)
is_root, is_leaf	O(1)
depth§	O($d_{p}+1$dp​+1)
height	O(n)
add_root, add_left, add_right, replace, delete, attach	O(1)

3.2 数组表示的二叉树

二叉树的一种表示法是对 T 的位置进行编号。对于 T 的每个位置 p，设 层编号函数 $f(p)$f(p)为整数且定义如下：

• 若 p 是 T 的根节点，则 $f(p)$f(p) 为0。
• 若 p 是位置 q 的左孩子，则 $f(p)=2f(q)+1$f(p)=2f(q)+1
• 若 p 是位置 q 的右孩子，则 $f(p)=2f(q)+2$f(p)=2f(q)+2
  

数组表示的二叉树的性能

• 优势： 位置 p 能用简单的整数 $f(p)$f(p) 来表示，且基于位置的方法（如root、parent、left和right方法）能采用对编号 $f(p)$f(p) 进行简单算术操作的方法来执行。
• 缺点： 空间使用情况极大地依赖于树的形状。不能有效地支持树的一些更新方法（如删除节点且提升自己的孩子节点的编号需要花费O(n)的时间）

3.3 一般树的链式存储结构

与二叉树的链式结构类似，但是对于一般树，一个节点所拥有的孩子节点之间没有优先级限制。因此可以使每个节点都配置一个容器，该容器存储存储指向每个孩子的引用。

4 树的遍历算法

4.1 树的先序和后序遍历

树 T 的 先序遍历（深度优先遍历） 中，首先访问 T 的根，然后递归地访问子树的根。
伪代码：

Algorithm preorder(T, p):
    perform the "visit" action for position p
    for each child c in T,children(p) do
        preorder(T, c)

后序遍历优先遍历子树的根，然后访问根。

Algorithm postorder(T, p):
    for each child c in T,children(p) do
        postorder(T, c)
    perform the "visit" action for position p

4.2 树的广度优先遍历

在访问深度 d+1 的位置之前先访问深度 d 的位置。
算法：

Algorithm breadthfirst(T):
    Initialize queue Q to contain T.root()
    while Q not empty do
        p = Q.dequeue()
        perform the "visit" action for position p
        for each child c in T.children(p) do
            Q.enqueue(c)

4.3 (仅)二叉树的中序遍历

Algorithm inorder(p):
    if p has a left child lc then
        inorder(lc)
    perform the "visit" action for position p
    if p has a right child rc then
        inorder(rc)

中序遍历算法的应用

• 使用二叉树表达一个算术表达式，中序遍历访问的位置与标准的顺序表达式的顺序一致，如上图：$(3+1)\times4\div[(9-5)+2]$(3+1)×4÷[(9−5)+2]。
• 二叉搜索树 T 中的中序遍历可以按照非递减次序访问元素。

4.4 欧拉图

可以非正式地定义为沿着 T “走”，从根开始“走”向最后一个孩子，我们保持在左边，像“墙”一样查看 T 的边缘（下图红色路径）。

根据欧拉图，我们可以在每个子树遍历前、后以及在遍历左子树之后，右子树之前)分别设计所需要调用的方法。对于叶子节点，会连续调用3个方法：

• 子树遍历前：previsit()
• 子树遍历后：postvisit()
• 遍历左子树之后，右子树之前(仅可在二叉树中使用)：invisit()