第五章 树与二叉树

小题考频：30
大题考频：8

5.1 树的基本概念

难度：☆☆

知识总览

5.1.1+5.1.2 树的定义和基本术语

5.1.3 树的性质

5.1.1+5.1.2 树的定义和基本术语

树的基本概念

自然界的树：

数据结构：

对于非空树：
有且只有一个根节点，只有根节点没有前驱；
没有后继的结点称为“叶子结点”；
有后继的结点称为“分支结点”
除了根节点外，任何一个结点都有且仅有一个前驱。
每个结点可以有0个或多个后继。

这样的数据结构就不是树！
应该称为图或者是网，在下一章中学习。

树是n（n≥0）个结点的有限集合，n = 0时，称为空树，这是一种特殊情况。在任意一棵非空树中应满足：
1）有且仅有一个特定的称为根的结点。
2）当n > 1时，其余结点可分为m（m > 0）个互不相交的有限集合 T 1 , T 2 , … , T m T_1, T_2,…, T_m T1​,T2​,…,Tm​，其中每个集合本身又是一棵树，并且称为根结点的子树。

互不相交和每个结点只有一个前驱是同一个意思。

所谓“子树”，又可以把他看作一个新的树。
比如说把左边这个树看做一个新树：

B就成了这个子树的根节点，同样的，可以把这棵树继续分别为两个不相交的子树。

右边的子树只有一个结点：

那么可以把这颗子树看做是一个根节点的同时，它的子树都是空树的这样的一个树。

可以看出树是一种递归定义的数据结构，任何一棵树都可以看作是由根节点和若干个不想交的子树所组成的。

树形逻辑结构的应用

Eg1. 行政区划分

Eg2. 文件系统

Eg3. 思维导图

结点之间的关系描述

结点之间的关系描述来自于，家谱。

接下来看这几个术语：

• 祖先结点：从一个结点出发往上走，直到根节点为止，路上经过的所有结点都是这个结点的祖先结点。
  ——对于“你“”来说：是【父亲、爷爷】

• 子孙结点：从一个结点出发，分支下面的所有结点都是这个结点的子孙结点。
  ——对于“爷爷”来说：是【下面的所有结点】

• 双亲结点（父节点）：一个结点的直接前驱就是它的父节点。
  ——对于“你”来说：是【父亲】

• 孩子结点：一个结点的直接后继就是它的孩子节点。
  ——对于“父亲”来说：是【你】

• 兄弟结点：同一双亲结点的子结点之间互为兄弟结点。
  ——对于“父亲”来说：是【二叔、三叔】
  ——对于“你”来说：是【F】

• 堂兄弟结点：双亲在同一层的结点互为堂兄弟结点的祖先。
  ——对于“你”来说：是【G、H、I、J】

  一般来说，【F】结点会被描述为“你”的兄弟结点，而不称为堂兄弟结点。
  如果说，A是B的堂兄弟，那么意思就是【A和B结点在同一层】

• 两个结点之间的路径：树里面描述两个结点之间的路径的时候，这个路径是单向的【只能从上往下】。

  树里面的边是有向的边，只能从上往下走。
  可以说“爷爷结点”到“你结点”是有路径的。

• 路径长度：指这个路径经过了几条边

  因为结点只能从上往下，所以说“你结点”到“G结点”是没有路径的。

结点、树的属性描述

属性：

• 结点的层次（深度）：从上往下数【默认从1开始】

  A在第1层，BCD在第2层，EF这些在第3层，以此类推，越往下 层数越深。
  从第0层开始计算的话灵活运用。

• 结点的高度：从下往上数

  KLM高度是1，EF这些在第2层，以此类推，越往上 高度越高。

• 树的高度（深度）：总共多少层

  这棵树的高度就是4

• 结点的度：有几个孩子（分支）

  C结点只有一个分支，度为1；
  B结点有两个分支，度为2；
  M结点没有分支，度为0；

  非叶子结点（分支节点）的度 ＞ 0
  叶子结点的度 = 0

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

  这棵树的度就是3

有序树 V.S 无序树

有序树——逻辑上看，树中结点的各子树从左至右是有次序的，不能互换
无序树——逻辑上看，树中结点的各子树从左至右是无次序的，可以互换
具体看你用树存什么，是否需要用结点的左右位置反映某些逻辑关系
 
家谱的顺序是从左到右排列的，结点次序交换会导致含义发生错误。
行政区划分的排序无所谓，为无序树

树 V.S 森林

森林。森林是$m(m＞0)$棵互不相交的树的集合
Eg. 全中国所有人家的家谱

左边这几棵树就可以组成一个森林。
如果把这几棵树都连上同一个根节点的话，那这个森林就变成了一棵树。

树可以有0个结点，即允许有空树的特殊状态；
同样的，森林也可以有0棵树，即m可为0，就是空森林。

5.1.3 树的性质

常见考点1：结点数 = 总度数 + 1

常见考点1：结点数 = 总度数 + 1
结点的度——结点有几个孩子（分支）

除了根节点，每一个分支下面都会连一个孩子

常见考点2：度为m的树、m叉树的区别

常见考点2：度为m的树、m叉树的区别

树的度：树里面各个结点的度的最大值
m叉树：每一个结点最多只能有m个孩子的树

Eg.

度为3的树，意味着至少有一个结点，其度为3；
一定是非空树，因为要保证其有一个结点中有m个孩子。
其至少有m+1个结点，m个孩子+1个根节点。
 
3叉树，指每个结点最多有3个孩子，如果树所有的结点都小于3，其依然是一个合法的三叉树。
m叉空树，也是允许存在的。

常见考点3：度为m的树和m叉树的结点数

常见考点3：
度为m的树第i层至多有 M i − 1 M^{i-1} Mi−1 个结点（i≥1）
也可以说m叉树第i层至多有 M i − 1 M^{i-1} Mi−1 个结点（i≥1）

第一层根节点，1个；
第二层最多每一个有三个，3^1个；
第三层最多每一个有三个，3^2个；

常见考点4：高度为h的m叉树至多有 m h − 1 m − 1 \\frac{m^h-1}{m-1} m−1mh−1​个结点。

常见考点4：高度为h的m叉树至多有 m h − 1 m − 1 \\frac{m^h-1}{m-1} m−1mh−1​个结点。
之前已经算出了每一层有多少个结点，将前h层全部加起来就是结果。

等比数列求和公式：
a + a q + a q 2 + ⋯ + a q n − 1 = a ( 1 − q n ) 1 − q a+aq+aq^2+\\cdots +aq^{n-1}=\\frac{a\\left( 1-q^n \\right)}{1-q} a+aq+aq2+⋯+aqn−1=1−qa(1−qn)​

那么最少有多少个结点呢？

常见考点5：高度为h的m叉树和度为m的树至少有几个结点？

常见考点5：
高度为h的m叉树至少有h个结点。
高度为h、度为m的树至少有h+m-1个结点。

对于m叉树，只规定了每一个结点的孩子数量上限是多少，并没有规定其下限。
节点数最少的情况应该是从根结点一直往下，每个结点都只有一个孩子的情况。

对于度为m的树来说，至少要保证有一个结点有m个孩子，所以至少要有h+m-1个结点。

常见考点6：具有n个结点的m叉树的最小高度为 ⌈ log ⁡ m ( n ( m − 1 ) + 1 ) ⌉ \\lceil \\log _m\\left( n\\left( m-1 \\right) +1 \\right) \\rceil ⌈logm​(n(m−1)+1)⌉

常见考点6：具有n个结点的m叉树的最小高度为 ⌈ log ⁡ m ( n ( m − 1 ) + 1 ) ⌉ \\lceil \\log _m\\left( n\\left( m-1 \\right) +1 \\right) \\rceil ⌈logm​(n(m−1)+1)⌉

$\lceil \Delta \rceil$该符号为向上取整

高度最小的情况——所有结点都有m个孩子

高度最小，就需要保证每一个结点都有尽可能多的孩子，即m个孩子。
树就会长得更宽，高度更小。

假设这个树的最小高度是h，高度为h的m叉树至多有 m h − 1 m − 1 \\frac{m^h-1}{m-1} m−1mh−1​个结点。
假设n个结点至少有h层，那么n的数量肯定要大于h-1层树的上限（h-1的MAX），同时要小于等于h层树的上限（h的MAX）：

进行数学推导，乘(m-1)，取对数，解出h的值：

知识回顾与重要考点

5.1.1+5.1.2 树的定义和基本术语

• 子树的概念：树中每个集合本身又是一棵树，并且称为根结点的子树
• 结点之间的路径：只能从上往下走
• 结点的度：结点的分支数
• 树的度：树中各结点的度的最大值

5.1.3 树的性质

• 注意度为m的树和m叉树之间的区别。