树
树是n个节点的有限集。当n=0时，称为空树。在任意一颗非空树中应满足：
- 有且仅有一个特定的称为根的节点
- 当n>1时，其余节点可分为m个互不相交的有限集T1，T2，…，Tm，其中每个集合本身时一棵树，并且称为根的子树。
其他术语如度、深度等等不做详细阐述
性质
- 树中的结点数等于所有节点的度数加1
- 度为m的树中第i层之多有
m
i
?
1
m^{i-1}
mi?1个节点(
i
≥
1
i \geq 1
i≥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)?
二叉树
二叉树与度为2的有序树的区别
- 度为2的树至少有三个节点，而二叉树可以为空
- 度为2的有序树的孩子的左右次序是相对于另一孩子而言的，若某个节点只有一个孩子节点，则这个孩子就无须区分其左右次序，而二叉树无论其孩子数是否为2，均需确定其左右次序，即二叉树的节点次序是确定的
特殊的二叉树
- 满二叉树
- 完全二叉树：对于最大层次中的叶子节点，都依次排列在该层的最左边的位置上
- 二叉排序树：左子树上所有节点的关键字均小于根节点的关键字；右子树上的所有节点的关键字都大于根节点的关键字；左右子树又各是一颗二叉排序树
- 平衡二叉树：树上任一节点的左子树和右子树的深度之差不超过1
性质
- 非空二叉树上的叶子结点数等于度为2的结点数加1，即
n
0
=
n
2
+
1
n_0= n_2+1
n0?=n2?+1。即结点数=边数+1
- 非空二叉树上第
k
k
k层上至多有
2
k
?
1
2^{k-1}
2k?1个结点
(
k
≥
1
)
(k≥1)
(k≥1)。
- 高度为
h
h
h的二叉树至多有
2
h
?
1
2^{h-1}
2h?1个结点
(
h
≥
1
)
(h≥1)
(h≥1)。
- 对完全二叉树按从上到下、从左到右的顺序依次编号1,2,…,n，则有以下关系:
- 当
i
>
1
i>1
i>1时，结点i的双亲的编号
?
i
/
2
?
\lfloor i/2 \rfloor
?i/2?，即当i为偶数时，其双亲的编号为
i
/
2
i/2
i/2，它是双亲的左孩子;当i为奇数时，其双亲的编号为
(
i
?
1
)
/
2
(i- 1)/2
(i?1)/2，它是双亲的右孩子。
- 当
2
i
≤
n
2i≤n
2i≤n时，结点i的左孩子编号为
2
i
2i
2i，否则无左孩子。
- 当
2
i
+
1
≤
n
2i+1≤n
2i+1≤n时，结点i的右孩子编号为
2
i
+
1
2i+1
2i+1，否则无右孩子。
- 结点i所在层次（深度）为
?
l
o
g
2
i
?
+
1
\lfloor log_2i \rfloor +1
?log2?i?+1。
- 具有n个(n>0)结点的完全二叉树的高度为
?
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
?log2?n?+1.
存储结构
- 线性存储
- 链式存储
|