树
- 树中的节点数等于所有节点的度数之和+1（一个节点的孩子个数称为该节点的度）
- 度为m的树中第i层上至多有 m i − 1 m^{i-1} mi−1个节点
- 高度为h的m叉树至多有 m h − 1 m − 1 \frac{m^h-1}{m-1} m−1mh−1个节点
- 具有n个节点的m叉树的最小高度是 ⌈ l o g m ( n ( m − 1 ) + 1 ) ⌉ \lceil log_m(n(m-1)+1)\rceil ⌈logm(n(m−1)+1)⌉
- 度为m的树中，设度为k的节点个数为 n k n_k nk，则树中叶子节点个数为 ∑ k = 1 m ( k − 1 ) n k + 1 \sum_{k=1}^{m}(k-1)n_k+1 ∑k=1m(k−1)nk+1（ n 0 + n 1 + . . . + n m = 1 n 1 + 2 n 2 + . . . + m n m + 1 n_0+n_1+...+n_m=1n_1+2n_2+...+mn_m+1 n0+n1+...+nm=1n1+2n2+...+mnm+1，即节点个数=所有节点的度数之和+1=边的个数+1）
二叉树
- 满二叉树定义：高度为h，且含有
2
h
−
1
2^h-1
2h−1个节点的二叉树（除叶节点外每个节点度数均为2）。下面的性质既适用于满二叉树，又适用于完全二叉树
- 若根节点从1开始编号，对于编号i的节点，若有双亲，则双亲为 ⌊ i 2 ⌋ \lfloor \frac{i}{2}\rfloor ⌊2i⌋；若有左孩子，则左孩子为2i；若有右孩子，则右孩子为2i+1。节点i所在层次（深度）为 ⌊ l o g 2 i ⌋ + 1 \lfloor log_2 i\rfloor+1 ⌊log2i⌋+1
- 若根节点从0开始编号，对于编号i的节点，若有双亲，则双亲为 ⌊ i − 1 2 ⌋ \lfloor \frac{i-1}{2}\rfloor ⌊2i−1⌋；若有左孩子，则左孩子为2i+1；若有右孩子，则右孩子为2i+2
- 非空二叉树上的叶节点数等于度为2的节点数+1，即 n 0 = n 2 + 1 n_0=n_2+1 n0=n2+1
- 具有n个节点的完全二叉树的高度为 ⌈ l o g 2 ( n + 1 ) ⌉ \lceil log_2(n+1)\rceil ⌈log2(n+1)⌉或 ⌊ l o g 2 n ⌋ + 1 \lfloor log_2n\rfloor+1 ⌊log2n⌋+1
- 若 i ≤ ⌊ n 2 ⌋ i\leq \lfloor \frac{n}{2} \rfloor i≤⌊2n⌋，则节点i为分支节点（节点 ⌊ n 2 ⌋ \lfloor \frac{n}{2} \rfloor ⌊2n⌋是编号最大的分支节点），否则为叶子结点
- 含有n个节点的二叉树必定存在n+1个空链域（n个节点共有 2 n 2n 2n个链域），除了根节点以外的每个节点（n-1个）都向上引出一条边（链域），因此空链域一共有 2 n − ( n − 1 ) = n + 1 2n-(n-1)=n+1 2n−(n−1)=n+1个
- 含有n个节点的二叉树最多有
C
2
n
n
n
+
1
=
(
2
n
)
!
n
!
(
n
+
1
)
!
\frac{C_{2n}^{n}}{n+1}=\frac{(2n)!}{n!(n+1)!}
n+1C2nn=n!(n+1)!(2n)!种形态（记住即可），等价说法：
- 对于n个不同元素进栈，出栈序列的个数为 C 2 n n n + 1 \frac{C_{2n}^{n}}{n+1} n+1C2nn
- 以序列a, b, c, d为入栈次序，则出栈序列的个数为14
- 先序序列为a, b, c, d的不同二叉树的个数为14
- 不同形态的二叉树的数目恰好是前序序列均为a,b,c,d的二叉树所能得到的中序序列的数目。而中序遍历的过程实质上是一个节点进栈和出栈的过程。二叉树的形态确定了其节点进栈和出栈的顺序，也确定了其节点的中序序列。由此，由前序序列a,b,c,d所能得到的中序序列的数目恰为数列a,b,c,d按不同顺序进栈和出栈所能得到的排列的数目，这个数目为 C 2 n n − C 2 n n − 1 = C 2 n n n + 1 C_{2n}^n-C_{2n}^{n-1}=\frac{C_{2n}^{n}}{n+1} C2nn−C2nn−1=n+1C2nn
- （前序序列和中序序列的关系相当于以前序序列为入栈次序，以中序序列为出栈次序）
- 平衡二叉树的深度与节点个数之间的极限关系：
考虑深度为h的平衡二叉树的最小节点数（或称为含有xx个节点的平衡二叉树的最大深度）： C h = C h − 1 + C h − 2 + 1 ， C 1 = 1 ， C 2 = 2 C_h=C_{h-1}+C_{h-2}+1，C_1=1，C_2=2 Ch=Ch−1+Ch−2+1，C1=1，C2=2，其中 C h C_h Ch为高度为h的平衡二叉树的最少节点个数
由此可得， C 3 = 4 , C 4 = 7 , C 5 = 12 , C 6 = 20 C_3=4, C_4=7, C_5=12, C_6=20 C3=4,C4=7,C5=12,C6=20，即含有20个节点的平衡二叉树的最大深度为6，具有五层节点的AVL树至少有12个节点
k叉树
- 严格的k叉树中只包含度为k、度为0的节点。即 n = n 0 + n k n=n_0+n_k n=n0+nk
- k n k = n − 1 kn_k=n-1 knk=n−1，因为总共有 n k n_k nk个分支节点，共发出 k k k个分叉（为k叉树总分叉数量）。除了根节点外所有的节点头上都会有一个分叉。
- 由2得，
n
k
=
n
0
−
1
k
−
1
n_k=\frac{n_0-1}{k-1}
nk=k−1n0−1，即如果是严格k叉树，则该式右面一定除得尽。因此与下面的m叉哈夫曼树构造类似，最佳归并树需要添加虚段的数量为：
- 若 (初始归并段数量-1)%(k-1) = 0，说明刚好可以构成严格k叉树，此时不需要添加虚段
- 若 (初始归并段数量-1)%(k-1) = u ≠ \ne = 0，则需要补充 (k-1)-u 个虚段
哈夫曼树
- 若哈夫曼树中有
n
0
n_0
n0个叶节点，则总共有
2
×
n
0
−
1
2\times n_0-1
2×n0−1 个节点，且度为2的节点数为
n
0
−
1
n_0-1
n0−1
- 思路：每次归并，少了两个节点，多出一个非叶子节点，整体节点数-1。最后归并结果是剩下一个节点（根节点），所以是归并了n-1次。因此最终的非叶子节点是n-1个
- 若度为m的哈夫曼树中，叶子节点个数为n，则非叶子节点的个数为
⌈
n
−
1
m
−
1
⌉
\lceil \frac{n-1}{m-1}\rceil
⌈m−1n−1⌉
- 思路：类似上述思路，每次归并，少了m个节点，多出一个非叶子节点，整体节点数-1。最后归并结果是剩下一个根节点，所以是归并了 ⌈ n − 1 m − 1 ⌉ \lceil \frac{n-1}{m-1}\rceil ⌈m−1n−1⌉次，因此最终的非叶子节点数也是 ⌈ n − 1 m − 1 ⌉ \lceil \frac{n-1}{m-1}\rceil ⌈m−1n−1⌉个
- m叉哈夫曼树的构造：设有
n
0
n_0
n0个初始节点
- 首先计算 t = ( n 0 − 1 ) m o d ( m − 1 ) t=(n_0-1) mod (m-1) t=(n0−1)mod(m−1). 若t不为零，则补充 m − t m-t m−t个权为0的节点到初始节点中；若t为零，则无需添加节点。
B树
- 除根节点外的所有非叶节点至少有 ⌈ m 2 ⌉ \lceil \frac{m}{2} \rceil ⌈2m⌉棵子树，即至少含有 ⌈ m 2 ⌉ − 1 \lceil \frac{m}{2}\rceil-1 ⌈2m⌉−1个关键字
- n个关键字的B树必有n+1个叶子节点（n个关键字将数域切分成n+1个区间）
- 含有n个关键字的m阶B树，树的高度h满足：
l
o
g
m
(
n
+
1
)
≤
h
≤
l
o
g
⌈
m
2
⌉
n
+
1
2
+
1
log_m(n+1)\le h \le log_{\lceil \frac{m}{2}\rceil}\frac{n+1}{2}+1
logm(n+1)≤h≤log⌈2m⌉2n+1+1
- 最小高度：让每个节点尽可能满（即有m-1个关键字，m个分叉）。即 n ≤ ( m − 1 ) ( 1 + m + m 2 + . . . + m h − 1 ) = m h − 1 n\le (m-1)(1+m+m^2+...+m^{h-1})=m^h-1 n≤(m−1)(1+m+m2+...+mh−1)=mh−1
- 最大高度：让每个节点尽可能空（即根节点只有1个关键字，其他节点只有 ⌈ m 2 ⌉ − 1 \lceil \frac{m}{2}\rceil-1 ⌈2m⌉−1个关键字、 ⌈ m 2 ⌉ \lceil \frac{m}{2} \rceil ⌈2m⌉个分叉）。即第一层1个节点，第二层2个，第三层 2 ⌈ m 2 ⌉ 2\lceil \frac{m}{2}\rceil 2⌈2m⌉个…第h层 2 ( ⌈ m 2 ⌉ ) h − 2 2(\lceil \frac{m}{2} \rceil)^{h-2} 2(⌈2m⌉)h−2个。由于n个关键字的B树必有n+1个叶子节点，因此有 n + 1 ≥ 2 ( ⌈ m 2 ⌉ ) h − 1 n+1\ge 2(\lceil \frac{m}{2} \rceil)^{h-1} n+1≥2(⌈2m⌉)h−1，即 h ≤ l o g ⌈ m 2 ⌉ n + 1 2 + 1 h \le log_{\lceil \frac{m}{2}\rceil}\frac{n+1}{2}+1 h≤log⌈2m⌉2n+1+1
红黑树
- 从根节点到叶节点的所有路径中，最长路径不会超过最短路径的两倍（保证红黑树大致上是平衡的）
- 具有n个内部节点的红黑树高度不超过 2 l o g 2 ( n + 1 ) 2log_2(n+1) 2log2(n+1)
- 在一个黑高是k的红黑树中，内部节点最多有 2 2 k − 1 2^{2k}-1 22k−1个（即红黑节点相间隔情形），最少是 2 k − 1 2^k-1 2k−1个节点
- 具有n个关键字的红黑树中红的内部节点数与黑的内部节点数之比最大是2：1
- 插入n（n>1）个节点形成的红黑树，至少有1个红节点
文章来源地址https://www.toymoban.com/news/detail-638667.html
文章来源：https://www.toymoban.com/news/detail-638667.html
到了这里，关于树、二叉树、哈夫曼树、B树、B+树、红黑树相关计算的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
