【数据结构】树与二叉树的基本概念及性质

一、树的基本概念

1️⃣树的定义

2️⃣基本术语

3️⃣树的性质

二、二叉树的概念

1️⃣二叉树的定义

2️⃣特殊二叉树

3️⃣二叉树的性质

参考资料

一、树的基本概念

1️⃣树的定义

数据结构中的树是什么❓
1. 树是 $n(n\geqslant 0)$ 个结点的有限集。
2. 有且仅有一个特定的称为根(上图A结点)的结点。
3. 当 n>1 时，其余结点可分为 m(m>0) 个不相交的有限集 $T_1,T_2,...,T_m$ ，其中每个集合本身又是一棵树，并且称为根的子树。
💡空树：n=0
树有哪些特点❓
1. 树的根结点没有前驱,除根结点外的所有结点有且只有一个前驱。
2. 树中所有结点都可以有零个或多个后继。

2️⃣基本术语

结点类术语

名称	含义	例子
祖先结点	从根到该节点所经分支上的所有结点，包含父节点。	J的祖先结点：A、B、E
子孙结点	一个结点的直接后继和间接后继，包含子节点。	B的子孙结点：E、F、J、K
双亲结点	一个结点的直接前驱结点，又称父结点	E的父结点：B
孩子结点	一个结点的直接后继结点	D的孩子结点：H、I
兄弟结点	同一双亲结点的孩子结点之间互称兄弟结点	J的兄弟结点：K
堂兄弟结点	父结点是兄弟关系或堂兄关系的结点	F的堂兄弟结点：G、H、I
叶子结点	度为0，无后继结点，也称终端结点。	叶子结点：橙色
分支结点	度不为0，有后继结点，也称非终端结点。	分支结点：蓝色

其他

名称		含义	例子
度	结点的度	树中一个结点的孩子个数(树杈的数量)	A的度=3，B的度=2
度	树的度	树中结点的最大度数	树的度=3
深度		从根结点开始自顶向下逐层累加	深度：4
高度		从叶结点开始子底向上逐层累加	高度：4
层次		从根结点开始定义，根结点的层次=1。
路径		两个结点连成的边
路径长度		路径上所经的边的个数

3️⃣树的性质

度为m的树（以度为3的树为例）	m叉树（以3叉树为例）

结点数 = 总度数 + 1（总度数：第2层到最后一层的结点；加1：根结点）
各结点的度的最大值	每个结点最多只能有m个孩子
任意结点的度 $\leqslant m$
至少有一个结点度 $=m$	允许所有结点的度都 $<m$
一定是非空树，至少有 $m+1$ 个结点	可以是空树
第 $i$ 层至多有 $m^{i-1}$ 个结点 $(i\geqslant 1)$
高度为 $h$ 、度为m的树至少有 $h+m-1$ 个结点	高度为 $h$ 的 m叉树至少有 $h$ 个结点
高度为 $h$ 的树至多有 $\frac{m^h-1}{m-1}$ 个结点
n个结点的树的最小高度为 $log_m(n(m-1)+1)$

💤思考一：为什么度为m的树、m叉树第 $i$ 层至多有 $m^{i-1}$ 个结点 $(i\geqslant 1)$ ❓

以3叉树为例，假如为满三叉树，如下图：
第一层：1个结点，m^0(m的0次幂)
第二程：3个结点，m^1
第三层：9个结点，m^2
...
第i层：m^{i-1}个结点(m的n-1次幂)

💤思考二：为什么高度为 $h$ ，度为 m 的树至少有 $h+m-1$ 个结点，而 m 叉树至少有 $h$ 个结点❓

以高度为3，度为3的树、3叉树为例：

我们首先复习一下什么是度为m的树，什么是m叉树

度为m的树：各结点的度的最大值。————等价于只要有一个结点的度 = 3 ，其余的度都最小 = 1
m叉树：每个结点最多只能有m个孩子，允许所有结点的度都 $< m$ 。————等价于将每个结点都设成最小 = 1

根据上述分析得到下图：
度为3的树：5 ————> h+m-1
3叉树    ：3 ————> h

💤思考三：为什么高度为 $h$ 为m的树、m叉树至多有 $\frac{m^h-1}{m-1}$ 个结点 ❓

高度为 3 为3的树、3叉树最多有多少个结点：

由上图知，共有结点数： $3^0+3^1+3^2=1+3+9=13$

高度为 $h$ 为m的树、m叉树最多有多少个结点： $m^0+m^1+m^2+...+m^{h-1}=\frac{1*(1-m^h)}{1-m}=\frac{1-m^{h}}{1-m}=\frac{m^h-1}{m-1}$ （等比公式求和）

💤思考四：为什么n个结点的树的最小高度为 $log_m(n(m-1)+1)$ ❓

二、二叉树的概念

1️⃣二叉树的定义

二叉树：每个结点至多只有两颗子树，且有左右之分，其次序不能颠倒。
空二叉树：n=0
二叉树的5种形态

因为二叉树具有左右之分、且允许所有结点的度<2，所以二叉树具有多种形态。

空二叉树只有根结点只有左子树只有右子树左右子树都有

2️⃣特殊二叉树

满二叉树
1. 概念：一棵树高为 h，且含有 $2^h-1$ 个结点的二叉树（每层树都含有最多的结点）
2. 图示:
3. 特点：
  1. 从根结点(根编号为1)，自上而下，自左向右，依次编号。
  2. 对于编号为 i 的结点，若有双亲，则双亲为 $\large {\color{Magenta} \frac{i}{2}}$ ；若有左孩子，则左孩子为 $\large {\color{Magenta} 2i}$ ；若有右孩子，则右孩子为 $\large {\color{Magenta} 2i+1}$ 。
完全二叉树
1. 概念：高度为h、有n个结点的二又树,当且仅当其每个结点都与高度为 h 的满二又树中编号为 1~n 的结点一一对应时,称为完全二又树。
2. 图示：
3. 特点：
  1. 若 $\large i\leq \frac{n}{2}$ ，则结点 i 为分支结点，否则为叶子结点。
  2. 叶子结点只可能在层次最大的两层上出现。对于最大层出现的叶子结点，都依次排列在该层的最左边。
  3. 若有度为1 的结点，则该结点只能有左孩子，无右孩子。
  4. 按层编号后，若某结点只有左结点或为叶子结点，则编号大于该结点的均为叶子结点。
  5. 若 n 为奇数，则每个分支结点都有左右孩子；若 n 为偶数，则编号最大的分支结点 $\large \frac{n}{2}$ ，只有左孩子，没有右孩子，其余分支结点都有左右孩子。
二叉排序树：左子树上所有结点的关键字均小于根结点的关键字:右子树上的所有结点的关键字均大于根结点的关键字:左子树和右子树又各是一棵二又排序树。
平衡二叉树：树上任意一个结点的左子树和右子树的深度之差不超过1。

3️⃣二叉树的性质

🍀性质一：非空二又树上的叶结点数等于度为2的结点数加1,即 $\large n_0=n_2+1$ 。

🍀性质二：非空二叉树上第 k 层上至多有 $\large 2^{k-1}$ 个结点 $\large (k\geq 1)$

m叉树的具体化性质

🍀性质三：高度为 h 的二叉树至多有 $\large 2^{h}-1$ 个结点 $\large (h\geq 1)$

m叉树的具体化性质

🍀性质四：对完全二又树按从上到下、从左到右的顺序依次编号1,2,…,n，则有以下关系;

        ①当 $\large i>1$ 时，结点 i 的双亲的编号为 $\large \frac{i}{2}$ ，即当 i 为偶数时，其双亲的编号为 $\large \frac{i}{2}$ ，它是双亲的左孩子；当 i 为奇数时，其双亲的编号为 $\large \frac{i-1}{2}$ ，它是双亲的右孩子。
②当    $\large 2i\leqslant n$ 时，结点 i 的左孩子编号为 $\large 2i$ ，否则无左孩子。
        ③当 $\large 2i+1\leqslant n$ 时，结点 i 的右孩子编号为 $\large 2i+1$ ，否则无右孩子。
        ④结点 i 所在层次(深度)为 $\large log_2i+1$ 。