数据结构--树（1）

数据结构基础（11）

树的定义

树：从树根生长，逐级分支

• ∅ 空树 – 结点数为0的树

• 非空数的特点：

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

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

有且仅有一个特定的称为根的结点。

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

树是一种递归定义的数据结构

• 祖先节点，子孙节点，双亲结点（父节点）、孩子节点、兄弟节点、堂兄弟结点-- > 可参照族谱的关系来判断

• 路径：只能从上往下

• 路径长度：经过几条边

结点、树的属性

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

非叶子结点的度 > 0

叶子结点的度 = 0

有序树与无序树

有序树 – 逻辑上看，树中结点的各子树从左至右是有次序的，不能互换

无序树 – 逻辑上看，树中结点的各子树从左至右是无次序的，可以互换

• 森林 ：是 m（m > 0）棵互不相交的树的集合，当 m = 0 时，为空森林

eg:全中国所有人家的家谱

常考性质

常见考点：2

• 树的度 ———— 各结点的度的最大值

度为 m 的树
任意结点的度 <= m (最多m个孩子)
至少有一个结点度 = m (有m个孩子)
一定是非空树，至少有m + 1个结点

• m叉树 ———— 每个结点最多只能有 m 个孩子的树

m叉树
任意结点的度 <= m (最多m个孩子)
允许所有结点的度都 < m
可以是空树

常见考点：3

• 度为 m 的树第 i 层至多有 $m^{i-1}$ 个结点（(i > 1) ）
• m 叉树第 i 层至多有 $m^{i-1}$个结点（(i > 1) ）

常见考点：4

• 高度为 h 的 m 叉树至多有 $\frac{m^h-1}{m-1}$ 个结点。

常见考点：5

• 高度为 h 的 m 叉树至少有 h 个结点。
• 高度为 h、度为 m 的树至少有 (h + m - 1) 个结点。

常见考点：6

有 n 个结点的 m 叉树的最小高度为$\lceil {\log }_m(n(m-1)+1)\rceil$

二叉树的基本概念

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

​ 或者为空二叉树，即 n = 0。

​ 或者由一个根结点和两个互不相交的被称为根的左子树和右子树组成。左子树和右子树又分别是一棵二叉树。

​ 特点：①每个结点至多只有两棵子树 ②左右子树不能颠倒（二叉树是有序树）

注意：要注意区别度为2的有序树

二叉树是递归定义的数据结构

满二叉树

• 一棵高度为 h，且含有$ 2^h - 1$ 个结点的二叉树

特点：

1. 只有最后一层有叶子结点
2. 不存在度为 1 的结点
3. 按层序从 1 开始编号，结点 i 的左孩子为 2i，右孩子为 (2i + 1)；结点 i 的父节点为 $\lfloor i/2\rfloor$（如果有的话）

注：满二叉树是完全二叉树的一种

完全二叉树

• 当且仅当其每个结点都与高度为 h 的满二叉树中编号为 (1 \sim n) 的结点一一对应时，称为完全二叉树

特点：

1. 只有最后两层可能有叶子结点
2. 最多只有一个度为 1 的结点
3. 同左 ③（即按层序从 1 开始编号，结点 i 的左孩子为 2i，右孩子为 (2i + 1)；结点 i 的父节点为$\lfloor i/2\rfloor$（如果有的话） ）
4. $i\le \lfloor n/2\rfloor$为分支结点，$i>\lfloor n/2\rfloor$为叶子结点

二叉排序树

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

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

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

平衡二叉树

• 树上任一结点的左子树和右子树的深度不超过1

平衡二叉树能有更高的搜索效率

二叉树的常考性质

常见考点 1：

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

常见考点2：

• 二叉树第 i 层至多有 $2^{i-1}$ 个结点（(i > 1) ）
• m 叉树第 i 层至多有 $m^{i-1}$个结点（(i > 1) ）

常见考点3：

• 高度为 h 的二叉树至多有 $\frac{m^h-1}{m-1}$ 个结点。

• 高度为 h 的二叉树至多有$2^h-1$ 个结点（满二叉树）

完全二叉树的常考性质

常见考点 1：

具有 n 个（(n > 0) ）结点的完全二叉树的高度 h 为 $\lceil {\log }_2(n+1)\rceil$ 或 $\lfloor {\log }_{2}n\rfloor +1$

• 高为 h 的满二叉树共有 $2^h-1$ 个结点 — n的上限

• 高为 (h - 1) 的满二叉树共有 $2^{h-1}-1$个结点 —n的下限

• 第 i 个结点所在层次为 $\lceil {\log }_2(n+1)\rceil$ 或 $\lfloor {\log }_{2}n\rfloor +1$

常见考点2：

对于完全二叉树，可由结点数 n 推出度为 0、1 和 2 的结点个数 $n_0$、$n_1 $和 $n_2$

• 完全二叉树最多只有一个度为 1 的结点，即 $n_1=0$ 或 1
• 由二叉树通用性质$n_0=n_2+1$，———— > $n_0+n_2$ 一定是奇数

1. 若完全二叉树有 2k 个（偶数）结点： 必有$ n_1 = 1$，$n_0 = k$，$n_2 = k - 1$
2. 若完全二叉树有 (2k - 1) 个（奇数）结点： 必有 $n_1=0$，$n_0=k$，$n_2=k-1$

二叉树的存储结构

• 顺序存储
• 链式存储

二叉树的顺序存储：

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

TreeNode t[MaxSize];

存储规则：

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

数组下标：

• 可以让第一个位置（t[0]）空缺，保证数组下标和结点编号一致。
• 初始化时所有结点标记为空：

for (int i=0; i<MaxSize; i++){t[i].isEmpty = true;
}

几个重要常考的基本操作：

• i 的左孩子 —— 2i
• i 的右孩子 ——$ 2i + 1$
• i 的父节点 —— $\lfloor i/2\rfloor$
• i 所在的层次 ——$\lceil {\log }_2(n+1)\rceil$ 或 $\lfloor {\log }_{2}n\rfloor +1$

若 完全二叉树共有 n 个结点：

• 判断 i 是否有左孩子？—— $2i\le n$?
• 判断 i 是否有右孩子？—— $2i+1\le n$?
• 判断 i 是否是叶子 / 分支结点？—— $i>\lfloor n/2\rfloor$?

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

• 最坏情况：高度为 h 且只有 h 个结点的单支树（所有结点只有右孩子），也至少需要 $2^h-1$ 个存储单元
• 结论：二叉树的顺序存储结构，只适合存储完全二叉树

二叉树的链式存储

//二叉树的结点（链式存储）
typedef struct BiTNode{ElemType data;                   //数据域struct BiTNode *lchild,*rchild;  //左、右孩子指针
}BiTNode,*BiTree;

n个结点的二叉链表共有n + 1个空链域 – > 可以用于构造线索二叉树

链式存储

struct ElemType{int value;
};typedef struct BiTNode{ElemType 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;  //作为根节点的左孩子

同样的方法可以插入更多的结点

有时找父节点比较复杂，可以用一个三叉链表来实现

三叉链表 – > 方便找父结点

Tips：根据实际需求决定要不要加父结点指针
//二叉树的结点（链式存储）
typedef struct BiTNode{ElemType data;           //数据域struct BiTNode *lchild,*rchild;  //左、右孩子指针struct BiTNode *parent;         //父节点指针 
}BiTNode,*BiTree;

tips:根据实际情况需求决定要不要加父结点指针