树(Tree)

n(n≥0)个结点构成的有限集合

n=0时，称为空树

对于任意一颗非空树，它具有以下性质：

  • 树中有一个称为"根(root)"的特殊节点，用root表示
  • 其余结点可分为m(m>0)个互不相交的有限集$T_1$ $T_2$…$T_m$，其中每个集合本身又是一棵树。称为原来树的"
    子树(SubTree)"

子树不相交

除根节点外，每个结点有且仅有一个父结点

一棵N个结点的树有N-1条边

（树是保证所有结点连通的一种最小连通方式之一）

相关术语

结点的度 ：结点的子树个数

树的度：树的所有结点中最大的度数

叶结点：度为0的点

父结点：有子树的结点是其子树的根结点的父结点

子结点：若A结点是B结点的父结点，则称B结点是A结点的子结点

兄弟结点：具有同一父结点的各结点彼此是兄弟结点

路径和路径长度：从结点$n_1$到$n_k$的路径为一个结点序列$n_1$，$n_2$，…，$n_k$，$n_i$是$n_i+1$的父结点。路径所包含边的个数为路径的长度

祖先结点(Ancestor)：沿树根到某一结点路径上的所有结点都是这个结点的祖先结点

子孙结点(Descendant)：某一结点的子树中的所有结点是这个结点的子孙。

结点的层次(Level)：规定根结点在1层， 其它任一结点的层数是其父结点的层数加1

树的深度(Depth)：树中所有结点中的最大层次是这棵树的深度。

二叉树（Binary tree）

针对完全二叉树

是完全二叉树

由于D结点的断层，其不是完全二叉树

  • 二叉树的第i层的最大结点数为:2^i-1，i≥1

  • 深度为k的二叉树有最大结点总数为：(2^k)-1，k≥1

  • 对任何非空二叉树T,若$n_0$表示叶结点的个数，$n_2$是度为2的非叶结点个数，那么两者满足关系$n_0$ = $n_2$ + 1

    第三个结论可以这样得来：

    $n_0$ + $n_1$ + $n_2$ - 1 = 0 * $n_0$ + 1 * $n_1$ + 2 * $n_2$

    即：$n_0$ = $n_2$ + 1