数 据 结 构 与 算 法 ( 六 ) 张 铭 主 讲 采 用 教 材 : 张 铭, 王 腾 蛟, 赵 海 燕 编 写 高 等 教 育 出 版 社,2008. 6 ( 十 一 五 国 家 级 规 划 教 材 ) http://www.jpk.pku.edu.cn/pkujpk/course/sjjg
A 第 6 章 树 B 树 的 定 义 和 基 本 术 语 树 的 链 式 存 储 结 构 J H 树 的 顺 序 存 储 结 构 K 叉 树 2
树 的 顺 序 存 储 结 构 带 右 链 的 先 根 次 序 表 示 带 双 标 记 的 先 根 次 序 表 示 带 双 标 记 的 层 次 次 序 表 示 带 度 数 的 后 根 次 序 表 示 3
带 右 链 的 先 根 次 序 表 示 结 点 按 先 根 次 序 顺 序 连 续 存 储 ltag info rlink info: 结 点 的 数 据 rlink: 右 指 针 指 向 结 点 的 下 一 个 兄 弟 即 对 应 的 二 叉 树 中 结 点 的 右 子 结 点 ltag: 标 记 树 结 点 没 有 子 结 点, 即 二 叉 树 结 点 没 有 左 子 结 点,ltag 为 1 否 则 为 0 4
带 右 链 的 先 根 次 序 表 示 法 X J X K H J K 下 标 0 1 2 3 4 5 6 7 8 9 L rlink 7 5 3 4-1 6-1 -1 9-1 info J K L X ltag 0 0 1 1 1 1 1 0 1 1 5
从 先 根 rlink-ltag 到 树 下 标 0 1 2 3 4 5 6 7 8 9 rlink 7 5 3 4-1 6-1 -1 9-1 info J K L X ltag 0 0 1 1 1 1 1 0 1 1 J X K X L K H J 6
带 双 标 记 的 先 根 次 序 表 示 带 右 链 的 先 根 次 序 表 示 中 rlink 也 有 冗 余, 可 以 把 rlink 指 针 替 换 为 一 个 标 志 位 rtag, 成 为 带 双 标 记 的 先 根 次 序 表 示 其 中, 每 个 结 点 包 括 结 点 本 身 数 据, 以 及 两 个 标 志 位 ltag 和 rtag, 其 结 点 的 形 式 为 : ltag info rtag 由 结 点 的 先 根 次 序 以 及 ltag rtag 两 个 标 志 位, 就 可 以 确 定 树 左 孩 子 / 右 兄 弟 链 表 中 结 点 的 llink 和 rlink 值 其 中 llink 的 确 定 与 带 右 链 的 先 根 次 序 表 示 法 相 同 7
B 带 双 标 记 位 的 先 根 次 序 表 示 法 A A B K H rtag info ltag K H J J 0 0 1 1 1 0 1 0 1 1 A B K H J 0 1 0 1 0 0 1 0 1 1 8
从 rtag-ltag 先 根 序 列 到 树 下 标 0 1 2 3 4 5 6 7 8 9 rtag 0 0 0 0 1 0 1 1 0 1 info J K L X ltag 0 0 1 1 1 1 1 0 1 1 J X K X stack X J K L K H J 9
从 双 标 记 的 先 根 次 序 恢 复 树 template<class T> class ualtagtreenode { public: T info; int ltag, rtag; ualtagtreenode(); virtual ~ualtagtreenode(); }; 10 // 双 标 记 位 先 根 次 序 树 结 点 类 // 结 点 数 据 信 息 // 左 右 标 记 // 构 造 函 数 template <class T> Tree<T>::Tree(ualTagTreeNode<T> *nodearray, int count) { // 利 用 带 双 标 记 位 的 先 根 次 序 表 示 构 造 左 孩 子 右 兄 弟 表 示 的 树 using std::stack; // 使 用 STL 中 的 栈 stack<treenode<t>* > astack; TreeNode<T> *pointer = new TreeNode<T>; // 准 备 建 立 根 结 点 root = pointer;
for (int i = 0; i < count-1; i++) { // 处 理 一 个 结 点 pointer->setvalue(nodearray[i].info); // 结 点 赋 值 if (nodearray[i].rtag == 0) // 若 右 标 记 为 0 则 将 结 点 压 栈 astack.push(pointer); else pointer->setsibling(null); // 右 标 记 为 1, 则 右 兄 弟 指 针 为 空 TreeNode<T> *temppointer = new TreeNode<T>; // 预 先 准 备 下 一 个 if (nodearray[i].ltag == 0) // 左 标 记 为 0, 则 设 置 孩 子 结 点 pointer->sethild(temppointer); else { // 若 左 标 记 为 1 pointer->sethild(null); // 孩 子 指 针 设 为 空 pointer = astack.top(); // 取 栈 顶 元 素 astack.pop(); pointer->setsibling(temppointer); } // 为 栈 顶 设 置 一 个 兄 弟 结 点 pointer = temppointer; } pointer->setvalue(nodearray[count-1].info); // 处 理 最 后 一 个 结 点 pointer->sethild(null); pointer->setsibling(null); } 11
带 双 标 记 的 层 次 次 序 表 示 法 结 点 按 层 次 次 序 顺 序 存 储 在 连 续 存 储 单 元 ltag info rtag info 是 结 点 的 数 据 ltag 是 一 个 一 位 的 左 标 记, 当 结 点 没 有 子 节 点, 即 对 应 的 二 叉 树 中 结 点 没 有 左 子 结 点 时, ltag 为 1, 否 则 为 0 rtag 是 一 个 一 位 的 右 标 记, 当 结 点 没 有 下 一 个 兄 弟, 即 对 应 的 二 叉 树 中 结 点 没 有 右 子 结 点 时, rtag 为 1, 否 则 为 0 12
带 双 标 记 的 层 次 次 序 转 换 为 树 ltag info rtag 0 0 0 1 1 1 1 1 1 1 X K H J 0 1 0 0 1 0 1 0 0 1 queue K H J X 13 K H X J
目 录 页 带 双 标 记 位 的 层 次 次 序 构 造 template <class T> Tree<T>::Tree(ualTagWidthTreeNode<T>* nodearray, int count) { using std::queue; // 使 用 STL 队 列 queue<treenode<t>*> aqueue; TreeNode<T>* pointer=new TreeNode<T>; // 建 立 根 root=pointer; for(int i=0;i<count-1;i++) { // 处 理 每 个 结 点 pointer->setvalue(nodearray[i].info); if(nodearray[i].ltag==0) aqueue.push(pointer); // 入 队 else pointer->sethild(null); // 左 孩 子 设 为 空 TreeNode<T>* temppointer=new TreeNode<T>; 14
目 录 页 } if(nodearray[i].rtag == 0) pointer->setsibling(temppointer); else { pointer->setsibling(null); } pointer=aqueue.front(); aqueue.pop(); pointer->sethild(temppointer); pointer=temppointer; // 右 兄 弟 设 为 空 // 取 队 列 首 结 点 指 针 // 队 首 元 素 出 队 列 } pointer->setvalue(nodearray[count-1].info); // 最 后 一 个 结 点 pointer->sethild(null); pointer->setsibling(null); 15
带 度 数 的 后 根 次 序 表 示 在 带 度 数 的 后 根 次 序 表 示 中, 结 点 按 后 根 次 序 顺 序 存 储 在 一 片 连 续 的 存 储 单 元 中, 结 点 的 形 式 为 info degree 其 中 info 是 结 点 的 数 据,degree 是 结 点 的 度 数 16
带 度 数 的 后 根 次 序 表 示 法 degree info 0 0 0 3 0 0 3 0 0 2 K H J X K H J X 17
带 度 数 的 后 根 次 序 变 成 树 degree 0 0 0 3 0 0 3 0 0 2 info K H J X J H X K K H J X 18
带 标 记 的 满 二 叉 树 前 序 序 列 A B H J K A 带 标 记 的 伪 满 二 叉 树 前 序 序 列 A B / H J / K A B B K K H H J J 19
思 考 : 森 林 的 顺 序 存 储 信 息 冗 余 问 题 树 的 其 他 顺 序 存 储 带 度 数 的 先 根 次 序? 带 度 数 的 层 次 次 序? 二 叉 树 的 顺 序 存 储? 二 叉 树 与 森 林 对 应, 但 语 义 不 同 带 右 链 的 二 叉 树 前 序 带 左 链 的 二 叉 树 层 次 次 序 20
6.4 K 叉 树 K 叉 树 定 义 K 叉 树 T 是 具 有 下 列 性 质 的 有 限 结 点 集 : (a) 集 合 可 以 为 空 ; (b) 非 空 集 合 是 由 一 个 根 结 点 root 及 K 棵 互 不 相 交 的 K 叉 树 构 成 其 余 结 点 被 划 分 成 T 0,T 1,,T K - 1 (K 1) 个 子 集, 每 个 子 集 都 是 K 叉 树, 使 得 T = {R, T 0,T 1,,T K - 1 } K 叉 树 的 各 分 支 结 点 都 有 K 个 子 结 点 21
6.4 K 叉 树 满 K 叉 树 和 完 全 K 叉 树 K 叉 树 (K-ary Tree) 的 结 点 有 K 个 子 结 点 二 叉 树 的 许 多 性 质 可 以 推 广 到 K 叉 树 满 K 叉 树 和 完 全 K 叉 树 与 满 二 叉 树 和 完 全 二 叉 树 是 类 似 的 也 可 以 把 完 全 K 叉 树 存 储 在 一 个 数 组 中 满 3 叉 树 22 完 全 3 叉 树
数 据 结 构 与 算 法 谢 谢 聆 听 国 家 精 品 课 数 据 结 构 与 算 法 http://www.jpk.pku.edu.cn/pkujpk/course/sjjg/ 张 铭, 王 腾 蛟, 赵 海 燕 高 等 教 育 出 版 社,2008. 6 十 一 五 国 家 级 规 划 教 材