离散数学笔记：树

学不完辣

好看的

树：基本知识

• 树的定义：不包含简单回路的连通无向图。
• 树中的任意两点之间存在唯一的通路。
• 删除树中的任意一条边，则树将不再是连通图。
• 在树中加一条边可以构成一条唯一的简单回路。
• 树是边数最少的连通图（从连通图中任意删去一个点，再施以归纳法），也是边数最多的没有简单回路的图。
• 树的结点的数量是边的数量 - 1.（任意删去一边，对结点的数量施以归纳法）
• 底图为树的有向图称为有向树。
• 如果有向树中恰好含有一个入度为0的点，则该点称为该有向树的根，称该树为 （有）根树。

根树

根树的图形表示

按照每个节点到根节点的距离来一层层向下排列。

有子女的节点称为 内点， 无子女的点称为树叶。 从树根到树叶的最大通路长度称为树高。
根节点在非平凡树中也是内点。

关于根树的术语

• m元树：每个内点均至多有m个子女的树。
• 完全m元树：每个内点恰好均有m个子女。
• 树的层数：定义根节点的层数为0，某节点的层数定义为根节点到此节点的唯一通路的长度。
• 平衡：设树高为h，若树叶均在第h - 1层或第h层，则该树是平衡的。
• 有序：同一层中每个节点都（按照某种偏序）有序排列。
• 根子树：根树T中的任一顶点v及其所有后代的导出子图也是根树，称之为T的根子树。
  特别的，有序二叉树的子树分别为左子树和右子树。
• 满（树、节点）：每个内点都有m个子节点的根树。
• 完全（树）：除最后一层的节点外其他节点均为满状态，且最后一层的节点从左向右填充的根树。
• 计算完全m元树的顶点数(n)、内点数(i)、树叶数(l)之间的两个公式：
  • (n - 1) = m * i - 入度 = 出度
  • n = i + l - 顶点数 = 内点数 + 树叶数
• 有序根树的前序(preorder(tree))/后序遍历postorder(tree)/中序遍历inorder(tree)
  • 前序遍历：遍历顺序为[T, preorder(T1), preorder(T2)...preorder(Tn)].
  • 后序遍历：遍历顺序为[postorder(T1), postorder(T2), ..., postorder(Tn), T].
  • 中序遍历（适用于二叉树）：遍历顺序为[inorder(T1), T, inorder(T2)].