实 验 报 告 一 、 实 验 目 的 1. 掌 握 二 叉 树 的 数 据 类 型 描 述 及 二 叉 树 的 特 性 。 2. 掌 握 二 叉 树 的 链 式 存 储 结 构 （ 二 叉 链 表 ） 的 建 立 算 法 。 3. 掌 握 二 叉 链 表 上 二 叉 树 的 基 本 运 算 的 实 现 。 二 、 实 验 内 容 1. 实 现 二 叉 树 的 层 次 递 进 。 2. 将 一 颗 二 叉 树 的 所 有 左 右 子 树 进 行 交 换 。 三 、 实 验 与 算 法 分 析 二 叉 树 的 遍 历 二 叉 树 的 层 次 遍 历 采 用 的 是 队 列 。 本 题 用 一 个 一 维 数 组 来 代 替 队 列 ， 同 时 设 置 队 列的 对 头 指 针 和 队 尾 指 针 。 算 法 分 析 ： 自 定 义 3 个 函 数 ： 结 构 stru ct bitree； 建 立 二 叉 链 表 的 函 数 bitree *create()；按 层 次 遍 历 二 叉 链 表 的 函 数 v oid lorder(bitree *t)。 结 构 stru ct bitree 中 包 括 数 据 域 和 两 个 指 针 域 （ 一 个 指 向 左 孩 子 ， 另 一 个 指 向 右 孩子 ）。 建 立 二 叉 链 表 的 函 数 bitree *create() 中 先 建 立 一 个 空 队 列（ 条 件 是 front=1，rear=0）。 然 后 建 立 二 叉 链 表 ， 用 一 个 一 维 数 组 来 代 替 队 列 ， 存 放 输 入 的 结 点 ； 输 入 结 点 时 ， 必 须按 照 完 全 二 叉 树 的 形 式 输 入 ； 如 果 非 完 全 二 叉 树 ， 则 必 须 给 定 一 些 假 象 结 点 （ 虚 结 点 ），使 之 完 全 符 合 完 全 二 叉 树 形 式 。 当我们输 入 “，”时 表 示虚 结 点 （ 结 点 不存 在）； 输 入 结点 值时 ， 存 在的 结 点 则 输 入 它对 应的 字符 ； 最后 以一 个 特 殊字符 “#”作为输 入 的 结 束，表 示二 叉 链 表 已经完 成。 层 次 遍 历 二 叉 链 表 的 函 数 v oid lorder(bitree *t) 中 遍 历 结 束条 件 为头 指 针 下标大于尾 指 针 下标。 将 一 棵二 叉 树 的 所 有 左 右 子 树 进 行 交 换 建 立 二 叉...
