一、 树的基本定义和性质

1. 树的逻辑结构定义

树是 n（n >= 0）个结点的有限集合。

  • 当 n=0 时，称为空树，这是一种特殊情况。
  • 在任意一棵非空树中，应满足：有且仅有一个特定的结点称为根结点。
  • 当 n > 1 时，其余结点可分为 m（m > 0）个互不相交的有限集合 T1, T2, …, Tm，其中每个集合本身又是一棵树，并称为根结点的子树。

2. 二叉树的特点

二叉树是 n（n >= 0）个结点的有限集合。

  • 它或者为空二叉树（n=0）。
  • 或者由一个根结点和两个互不相交的被称为根的左子树和右子树组成，左子树和右子树又分别是一棵二叉树。
  • 二叉树的特点包括：每个结点至多只有两棵子树。
  • 左右子树不能颠倒（二叉树是有序树）。

二、 m 叉树的常见考点性质及其推导

以下是关于高度为 h 的 m 叉树（m-ary tree）的常见性质：

1. m 叉树至多拥有的结点数

性质： 高度为 h 的 m 叉树至多有 (m^h - 1) / (m - 1) 个结点。

推导：

  • 这个结论基于每一层结点数最大化（即所有非叶子结点都拥有 m 个孩子）的情况。
  • 第 1 层有 m^0 个结点。
  • 第 2 层有 m^1 个结点。
  • 第 3 层有 m^2 个结点。
  • 第 h 层有 m^(h-1) 个结点。
  • 总的结点数是这些层结点数的总和，构成一个等比数列求和：m^0 + m^1 + m^2 + … + m^(h-1)。
  • 根据等比数列求和公式 a + aq + aq^2 + … + aq^(n-1) = a(q^n - 1) / (q - 1)（其中 a=1, q=m, n=h），得到最大结点数为 (m^h - 1) / (m - 1)。

2. m 叉树最少拥有的结点数

性质： 高度为 h 的 m 叉树至少有 h 个结点。

3. 具有 n 个结点的 m 叉树的最小高度

性质： 具有 n 个结点的 m 叉树的最小高度为 h_min = log_m(n(m - 1) + 1) 向上取整。

推导过程（基于最大结点数）：

  • 要找到最小高度，必须假设树的结构是最丰满的（即每层节点尽可能多）。
  • 确定 n 的范围： 具有 h 层的 m 叉树的结点数 n 必须满足：
    (m^(h-1) - 1) / (m - 1) < n <= (m^h - 1) / (m - 1)
    • 其中，左侧不等式表示 n 必须大于前 h-1 层满 m 叉树的结点总数。
    • 右侧不等式表示 n 最多是 h 层满 m 叉树的结点总数。
  • 提取 m^h 的关系： 关注右侧不等式 (m^h - 1) / (m - 1) >= n。
    • 变形得到：m^h - 1 >= n(m - 1)。
    • 进一步得到：m^h >= n(m - 1) + 1。
  • 提取 m^(h-1) 的关系： 关注左侧不等式 (m^(h-1) - 1) / (m - 1) < n。
    • 变形得到：m^(h-1) - 1 < n(m - 1)。
    • 进一步得到：m^(h-1) < n(m - 1) + 1。
  • 合并和取对数： 将两个不等式合并：
    m^(h-1) < n(m - 1) + 1 <= m^h
    • 对两侧取以 m 为底的对数（log_m）：
      h - 1 < log_m(n(m - 1) + 1) <= h
  • 结论： 由于 h 必须是一个整数，根据这个关系，最小高度 h_min 等于 log_m(n(m - 1) + 1) 向上取整。

4. 高度为 h、度为 m 的树的最小结点数

性质： 高度为 h、度为 m 的树至少有 h+m-1 个结点。

三、 图中的生成树性质

在图论中，连通图的生成树（spanning tree）具有以下性质：

  • 存在性： 只有连通图才有生成树。非连通图只有生成森林。
  • 边数限制： 最小生成树的边数等于顶点数 - 1。如果在生成树中砍掉一条边则图将不连通；如果增加一条边则会出现回路。
  • 最小生成树（MST）的权值： 最小生成树可能有多个，但所有最小生成树的边的权值之和总是唯一且最小的。
  • 特殊情况： 如果一个连通图本身就是一棵树，则其最小生成树就是它本身。