mirror of
https://github.com/oxyanyano/2022-WangDao-CS-DS-Notes.git
synced 2026-02-02 18:29:00 +08:00
62 lines
2.9 KiB
Markdown
62 lines
2.9 KiB
Markdown
## 树 —— Tree
|
||
|
||
### 一、树的定义：
|
||
|
||
`树`是η(n≥0)个结点的有限集合,n≡o时,称为空树,这是一种特殊情况。在任意一棵非空树中应满足:
|
||
①有且仅有一个特定的称为根的`结点`。
|
||
②当n>1时,其余结点可分为m(m>0)个互不相交的有限集合T1,T2…,Tn,其中每个集合本身又是一棵树,并且称为根结点的`子树`。
|
||
|
||
|
||
|
||
### 二、树的术语
|
||
|
||
`父结点`：若一个结点含有子结点，则这个结点称为其子结点的父结点
|
||
`子结点`：一个结点含有的子树的根结点称为该结点的子结点
|
||
`兄弟结点`：拥有共同父结点的结点互称为兄弟结点
|
||
`祖先`：对任意结点x，从根结点到结点x的所有结点都是x的祖先（结点x也是自己的祖先）
|
||
`后代`：对任意结点x，从结点x到叶子结点的所有结点都是x的后代（结点x也是自己的后代）
|
||
|
||
`两结点的路径`：对任意结点x，从结点x到结点y的`从上到下`的路
|
||
`两结点的路径长度`：对任意结点x，从结点x到结点y经过的边数
|
||
|
||
`结点的层次`：对任意结点x，从根结点到结点x的`从上到下`经过的边数
|
||
`结点高度`：对任意结点x，叶子结点到x结点的路径长度就是结点x的`高度`
|
||
`树的深度`：一棵树中结点的最大深度就是树的深度，也称为`高度`
|
||
|
||
`结点的度`：有几个子结点（分支）
|
||
`树的度`：各结点的度的最大值
|
||
`叶子结点`：度为零的结点就是叶子结点
|
||
|
||
`森林`：m颗互不相交的树构成的集合就是森林
|
||
|
||
### 三、树的分类
|
||
|
||
有序树和无序树
|
||
|
||
`有序树`一一逻辑上看，树中结点的各子树从左至右是有次序的，不能互换
|
||
|
||
|
||
|
||
`无序树`一一逻辑上看，树中结点的各子树从左至右是无次序的，可以互换
|
||
|
||
|
||
|
||
### 四、树的性质
|
||
|
||
考点1：结点数=总度数+1
|
||
|
||
考点2：度为m的树和m叉树
|
||
`度为m的树`：至少有一个结点度=m，一定是非空树
|
||
`m叉树`：允许所有结点的度都≤m，可以是空树
|
||
|
||
考点3：度为m的树第i层至多有几个结点？ $$m^{i-1}$$
|
||
|
||
考点4：高度为h的m叉树至多有几个结点？ $$\frac{(m^{h}-1)}{(m-1)}$$
|
||
|
||
考点5：
|
||
高度为h的m叉树至少有多少个结点？ $$h$$
|
||
|
||
高度为h、度为m的树至少有多少个结点？ $$h+m-1$$
|
||
|
||
考点6：具有n个结点的m叉树的最小高度为？ $$log_m\lceil (n(m-1)+1) \rceil$$
|