Skip to content

Latest commit

 

History

History
268 lines (203 loc) · 9.89 KB

10 树与二叉树.md

File metadata and controls

268 lines (203 loc) · 9.89 KB

#数据结构 #C

[40] 树的定义和基本术语

数据结构树，与自然界的树类似，从树根生长，逐级分支。 树分为空树和非空树，空树是指结点为0的树。

非空树的特性

  • 有且仅有一个根结点
  • 没有后继的结点称为“叶子结点”（或终端结点）
  • 有后继的结点称为“分支结点”（或非终端结点）
  • 除了根结点外，任何一个结点都有且仅有一个前驱
  • 每个结点可以有0个或多个后继 除了根结点外，任何一个结点都有且仅有一个前驱。

树的基本概念

树是 $n(n ≥ 0)$ 个结点的有限集合。当 $n = 0$ 时，称为空树，这是一种特殊情况。
因此在任意一棵非空树中应满足：

  1. 有且仅有一个特定的称为根的结点。
  2. 当 $n > 1$ 时，其余结点可分为 $m(m > 0)$ 个互不相交的有限集合 $T_1, T_2,…, T_m$ ，其中每个集合本身又是一棵树，并且称为根结点的子树。

由树的特点可以容易得出，树天然是一种递归定义的数据结构。

结点、树的属性描述

属性：

  • 结点的层次（深度）—— 从上往下数
  • 结点的高度—— 从下往上数
  • 树的高度（深度）——总共多少层
  • 结点的度——有几个孩子（分支）
  • 树的度——各结点的度的最大值

森林。森林是m（m ≥ 0）棵互不相交的树的集合。
森林在机器学习算法中有随机森林算法。

树有空树的状态，森林也有空森林（m ≥ 0）的状态。

[41] 树的性质

树的度

树的结点个数 = 总度数 + 1

由于根结点不是任何结点的分支，所以上式成立。

度为m的树 与 m叉树

首先概念明确：

  • 树的度是指 ----> 各个结点的度的最大值
  • m叉树是指 ----> 每个结点最多能够有m个孩子的树
度是m的树 m叉树
任意结点的度 ≤ m（最多m个孩子） 任意结点的度 ≤ m（最多m个孩子）
至少有一个结点度 = m（有m个孩子） 允许所有结点的度都 ＜ m
一定是非空树，至少有m+1个结点 可以是空树

树最多的结点数目

度为m的树第i层最多有 $m^{i-1}$个结点 $(i≥1)$
m叉的树第i层最多有 $m^{i-1}$个结点 $(i≥1)$

高度为h的m叉树最多有结点个数: $$\frac{M^h-1}{m-1}$$

树最少的结点数目

高度为h的m叉树至少有 $h$ 个结点
高度为h，度为m的树，至少有 $h + m - 1$ 个结点

树的最小高度

具有n个结点的m叉树的最小高度为: $$⌈\log_{m}{(n(m - 1) + 1) }⌉$$

[42] 二叉树的定义和基本术语

二叉树的概念

二叉树是 $n（n≥0）$个结点的有限集合：

  • 可能情况1：空二叉树，即n = 0。
  • 可能情况2：由一个根结点和两个互不相交的被称为根的左子树和右子树组成。 左子树和右子树又分别是一棵二叉树。

特点：

  1. 每个结点至多只有两棵子树
  2. 左右子树不能颠倒（二叉树是有序树）

二叉树由于其左右子树的状态，存在以下五种类型。

满二叉树

  1. 一棵高度为h，且含有 $2^{h - 1}$ 个结点的二叉树。
  2. 只有最后一层有叶子结点
  3. 不存在度为 1 的结点
  4. 按层序从 1 开始编号，结点 $i$ 的左孩子为 $2i$，右孩子为 $2i+1$；结点 i 的父结点为 $⌊i/2⌋$ （如果有的话）

完全二叉树

当且仅当其每个结点都与高度为h的满二叉树中编号为1～n的结点一一对应时，称为完全二叉树。 特点：

  1. 只有最后两层可能有叶子结点
  2. 最多只有一个度为1的结点（上图中的6结点）
  3. 按层序从 1 开始编号，结点 $i$ 的左孩子为 $2i$，右孩子为 $2i+1$；结点 i 的父结点为 $⌊i/2⌋$ （如果有的话）
  4. $i≤ ⌊n/2⌋$ 为分支结点， $i≥ ⌊n/2⌋$ 为叶子结点。

二叉排序树

一棵二叉树或者是空二叉树，或者是具有如下性质的二叉树：

  1. 左子树上所有结点的关键字均小于根结点的关键字；
  2. 右子树上所有结点的关键字均大于根结点的关键字。
  3. 左子树和右子树又各是一棵二叉排序树。

二叉排序树可用于元素的排序、搜索。

平衡二叉树

平衡二叉树。树上任一结点的左子树和右子树的深度之差不超过1。他是一个“胖胖的、丰满的树”。 平衡二叉树能有更高的搜索效率。

[43] 二叉树的性质

度0、度1、度2 结点关系

结论： 设非空二叉树中度为0、1和2的结点个数分别为 $n_0$ 、 $n_1$ 和 $n_2$，则: $$n_0 = n_2 + 1$$ 即，叶子结点比二分支结点多一个。

理由：假设树中结点总数为 n，则

  1. $n = n_0 + n_1 + n_2$
  2. $n = n_1 + 2*n_2 +1$ (树的结点数 = 总度数 + 1，除去根结点的其他是度)

例如上图中，叶子结点（蓝色）5个，二分支结点（红色）4个，满足上图。

完全二叉树高度

结论：

具有n(n > 0)个结点的完全二叉树的高度h为:
$$⌈ \log_{2}{(n+1)}⌉$$ 或者 $$⌊\log_{2}{n}⌋ + 1$$

  • 高为 $h$ 的满二叉树共有 $2^{h} − 1$ 个结点，
  • 高为 $h - 1$ 的满二叉树共有 $2^{h-1}−1$ 个结点，

联立上式即可推导出。

完全二叉树度i的个数

对于完全二叉树，可以由的结点数 n 推出度为0、1和2的结点个数为 $n_0, n_1$ 和 $n2$ 完全二叉树最多只有一个度为1的结点，即: $n_1=0$ 或 $1$， $n_0 = n_2 + 1$，所以 $n_0 + n_2$ 一定是奇数。

如果完全二叉树有 $2k$ 个（偶数）个结点，则必有 $n_1=1， n_0 = k， n_2 = k-1$

如果完全二叉树有 $2k-1$ 个（奇数）个结点，则必有 $n_1=0， n_0 = k， n_2 = k-1$

例如，上图完全二叉树结点数12个，叶子结点6个，二分支5个，一分支1个。

[44] 二叉树的存储结构

以二叉树为例子，以两种不同的存储方式，展示树这一种数据结构的特点。

1. 顺序存储

使用数组存储元素，并添加标志位，代表该位置是否有数据。

#define MaxSize 100
typedef struct {
    Element value;      // 结点中的数据元素
    bool isEmpty;       // 结点是否为空
} TreeNode;

TreeNode tree[MaxSize];

定义一个长度为 MaxSize 的数组 tree ，按照从上至下、从左至右的顺序依次存储完全二叉树中的各个结点。

// 初始化时所有结点标记为空
void BiTreeSeqInit()
{
    for (int i = 0; i < MaxSize; i++) {
        tree[i].isEmpty = true;
        tree[i].value = 0;
    }
}

让第一个位置空缺，保证数组下标和结点编号一致。

在完全二叉树中：

  • i 的左孩子是 2i
  • i 的右孩子是 2i + 1；
  • i 的父结点 $⌊i / 2⌋$
  • i 所在的层次：$⌈\log_{2}{(n+1)}⌉$ 或者 $⌊\log_{2}{(n+1)}⌋$
判断场景 条件
判断i是否有左孩子？ $2 × i ≤ n$
判断i是否有右孩子？ $2 × i + 1 ≤ n$
判断i是否是叶子/ 分支结点？ $i&gt; ⌊n / 2⌋$

二叉树的顺序存储中，一定要把二叉树的结点编号与完全二叉树对应起来。

最坏情况：高度为 h 且只有 h 个结点的单支树（所有结点只有右孩子），也至少需要 $2^h-1$ 个存储单元。

最坏情况是指同样的存储空间下，存储的数据更少，密度更低。

2. 链式存储

同样，二叉树也可以使用链表的形式存储。

typedef struct BiTNode {
    ElemType data;
    struct BiTNode *lchild, *rchild;  // 左右孩子指针
} BiTNode, *BiTree;

n 个结点的二叉链表共有 n + 1 个空链域。 实际举例：

// 假设结点存储数据时int类型
typedef struct BiTNode {
    int data;
    struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree;

// 定义一个空树
BiTree root = NULL;

// 插入根结点
root = (BiTree)malloc(sizeof(BiTNode));
root->data = 1;
root->lchild = NULL;
root->rchild = NULL;

// 插入新结点
BiTNode *p = (BiTNode*)malloc(sizeof(BiTNode));
p->data = 2;
p->lchild = NULL;
p->rchild = NULL;
root->lchild = p; // 作为根结点的左孩子

/* ..code.. */

对于这样的二叉链表而言，找对应结点的子结点相对容易，而对于给定结点找到其父结点，相对较难。只能通过从头结点开始遍历查找。

因此，需要在原有的结构体上新增指向父结点的指针，这就是三叉链表表示树的数据结构：

typedef struct BiTNode {
    ElemType data;                
    struct BiTNode *lchild, *rchild;    // 左、右孩子指针
    struct BiTNode *parent;             // 父结点指针
} BiTNode, *BiTree;                     // 三叉链表，方便找父结点