cs

05.Binary Trees.pdf P6

树的定义

oiwiki：

• 有 $n$ 个结点，$n-1$ 条边的连通无向图

• 无向无环的连通图

• 任意两个结点之间有且仅有一条简单路径的无向图

• 任何边均为桥的连通图

• 没有圈，且在任意不同两点间添加一条边之后所得图含唯一的一个圈的图

长子-兄弟表示法

二叉树的结论

对于任意二叉树，$n_0 = n_2 + 1$

$e = n_0 + 2n_2$

$n = n_0 + n_1 + n_2 = 1 + n_0 + 2n_2$

如果一个无向图有 $n$ 个顶点，并有大于 $n - 1$ 条边，则图一定有环

若无环，则考虑此图的连通分量，由树的第二个定义，每个连通分量为一棵树，设有 $k$ 棵树，由树的定义1，应当有 $n - k$ 条边，其中 $k \ge 1$，于是图的边数 $n - k$ 不大于 $n - 1$，矛盾。