1 数 据 结 构 (本 )课 程 辅 导 与 练 习 -第 6章 第 6章 树 和 二 叉 树 树 是 一 种 重 要 的 非 线 性 结 构 ， 从 逻 辑 角 度 看 ， 其 数 据 元 素 之 间 体 现 的 是 一 对 多 的 非 线 性关 系 ， 一 切 具 有 层 次 关 系 的 问 题 都 可 以 用 树 来 描 述 。 一 、 相 关 术 语 树 、 二 叉 树 、 树 根 、 子 树 、 有 序 树 、 无 序 数 、 森 林 、 终 端 结 点 （ 叶 子 ）、 非 终 端 结 点 、结 点 的 度 、 结 点 的 层 次 、 树 的 深 度 、 满 二 叉 树 、 完 全 二 叉 树 、 理 想 二 叉 树 、 孩 子 、 双 亲 、 左孩 子 、 右 孩 子 、 先 序 遍 历 、 中 序 遍 历 、 后 序 遍 历 、 层 次 遍 历 、 哈 夫 曼 树 、 最 优 二 叉 树 、 路 径 、路 径 长 度 、 权 、 带 权 路 径 长 度 、 哈 夫 曼 编 码 。 二 、 树 的 概 念 树 的 定 义 树 的 递 归 定 义 ： 树 (Tree)是n(n≥ 0)个 结 点 的 有 限 集T， T为 空 时 称 为 空 树 ， 否 则 它 满 足 如 下 两 个 条件 ： (1)有 且仅有 一 个 特定 的 称 为 根 (Root)的 结 点 ； (2)其 余的 结 点 可 分为 m(m≥ 0)个 互不相 交的 子 集 Tl， T2， …， Tm， 其 中 每个 子 集 本 身又是 一棵树 ， 并称 其 为 根 的 子 树 (Subree)。 注意： 树 的 递 归 定 义 刻画了树 的 固有 特性 ： 一 棵非 空 树 是 由若干棵子 树 构 成的 ， 而子 树 又可 由若干棵更小的 子 树 构 成。 三、 二 叉 树 的 定 义 二 叉 树 是 树 形结 构 的 一 个 重 要 类型。许多 实际问 题 抽象出来 的 数 据 结 构 往往是 二 叉 树 的形式， 即使是 一 般的 树 也能简单地转换为 二 叉 树 ， 而且二 叉 树 的 存储结 构 及其 算法都 较为 简单， 因此二 叉 树 显得特别重 要 。 （ 1） 二 叉 树 与 无 序 树 不同 二 叉 树 中 ， 每个 结 点 最 多 只能有 两 棵子 树 ， 并且有 左 右 之 分。 二 叉 树 并非 是 树 的 ...
