(28)王道数据结构-树的基本概念

定义

树是n(n≥0)个节点的有限集合，n=0时，称为空树,这是一种特殊情况。在任意一个非空树种应满足:
1)有且仅有一个特点的称为根的节点。
2)当n>1时，其余节点可分为m(m>0)个互不相交的有限集合
$$
T_1,T_2,..T_m
$$
其中每个集合又是一颗树，并且称为根节点的子树

基本概念

节点的层次(深度): 从上往下数
节点的高度: 从下往上数
树的高度(深度): 总共多少层
节点的度: 有几个孩子(分支),非叶子节点度>0，叶子节点的度=0
树的度: 各节点度的最大值

有序树: 逻辑上看，树种节点的各子树从左至右是有次序的，不能互换
无需树: 逻辑上看，书中节点的各子树从左至右是无序的，可以互换
森林: 森林是m(m≥0)棵互不相交树的集合

性质

性质一: 节点数 = 总度数 + 1
性质二: 度为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}个节点,等比数列求和: a + aq + aq^2 + … + aq^{n-1} = \frac{a(1-qn)}{1-q}
$$

性质五:
高度为h的m叉树至少有h个节点。高度为h、度为m的数至少有h+m-1个节点

性质六:
具有n个节点的m叉树的最小高度为
$$
log_m[{n(m-1)+1}]
$$
高度最小情况-所有节点都有m个孩子，左边为前h-1层最多有几个节点，右边为前h层最多有几个节点
$$
\begin{align*}
\frac{m^{h-1}}{m-1} &< n ≤ \frac{m^h - 1}{m -1} \\[2ex]
m^{h-1} &< n(m-1) + 1 ≤ mh \\[2ex]
h - 1 &< log_m[{n(m-1)+1}] ≤ h \\[2ex]
h_{min} &= log_m[{n(m-1)+1}]
\end{align*}
$$