数据结构与算法 ( 六 ) 张铭主讲 采用教材 : 张铭, 王腾蛟, 赵海燕编写高等教育出版社,2008. 6 ( 十一五 国家级规划教材 ) http://www.jpk.pku.edu.cn/pkujpk/course/sjjg
第 6 章树 C 树的定义和基本术语 树的链式存储结构 子结点表 表示方法 静态 左孩子 / 右兄弟 表示法 动态表示法 动态 左孩子 / 右兄弟 表示法 父指针表示法及其在并查集中的应用 I J H 树的顺序存储结构 K 叉树 2
子结点表 表示方法 list of children, 就是图的邻接表 索引值父结点 子结点 0 1 2 1 0 3 4 2 C 0 6 7 3 1 8 9 4 1 5 2 6 2 10 11 7 H 2 8 I 3 9 J 3 10 K 6 11 L 6 5 3
静态 左孩子 / 右兄弟 表示法 在数组中存储的 子结点表 C H J I 左子结点 父值结点 0 C 0 0 2 2 H 6 I 6 J 7 右兄弟结点 4
动态表示法 每个结点分配可变的存储空间 子结点数目发生变化, 需要重新分配存储空间 2 C 2 C 3 H 2 0 0 2 H 0 I J K L (a) 树 I 0 J 0 K (b) 树的实现 0 L 0 5
动态 左子 / 右兄 二叉链表示法 左孩子在树中是结点的最左子结点, 右子结点是结点原来的右侧兄弟结点 根的右链就是森林中每棵树的根结点 pchild info psibling C C K H K H J J 6
动态二叉链表树的关键实现细节 // 在 TreeNode 的抽象类中增加以下私有数据成员 private: T m_value; // 树结点的值 TreeNode<T> *pchild; // 第一个左孩子指针 TreeNode<T> *psibling; // 右兄弟指针 7
寻找当前结点的父结点 template<class T> TreeNode<T>* Tree<T>::Parent(TreeNode<T> *current) { using std::queue; // 使用 STL 队列 queue<treenode<t>*> aqueue; TreeNode<T> *pointer = root; TreeNode<T> *father = upperlevelpointer = NULL; // 记录父结点 if (current!= NULL && pointer!= current) { while (pointer!= NULL) { // 森林中所有根结点进队列 if (current == pointer) // 森林中所有第一层根的父为空 break; aqueue.push(pointer); // 当前结点进队列 pointer=pointer-> RightSibling(); // 指针指向右 8
寻找当前结点的父结点 while (!aqueue.empty()) { C pointer = aqueue.front(); // 取队列首结点指针 aqueue.pop(); // 当前元素出队列 K H upperlevelpointer = pointer; // 指向上一层的结点 pointer = pointer-> LeftMostChild(); // 指向最左孩子 while (pointer) { // 当前结点的子结点进队列 J if (current == pointer) { father = upperlevelpointer; // 返回父 break; else { aqueue.push(pointer); pointer = pointer->rightsibling(); aqueue. clear( ); // 清空队列, 也可以不写 ( 局部变量 ) return father; 9 X W Y
template <class T> void Tree<T>::estroyNodes(TreeNode<T>* root) { 删除以 root 为代表的森林的所有结点 if (root) { estroynodes(root->leftmostchild());// 递归删除第一子树 estroynodes(root->rightsibling()); // 递归删除其他子树 delete root; // 删除根结点 10
删除以 subroot 为根的子树 template<class T> void Tree<T>::eleteSubTree(TreeNode<T> *subroot) { if (subroot == NULL) return;// 若待删除的子树为空则返回 TreeNode<T> *pointer = Parent (subroot); // 找 subroot 的父结点 if (pointer == NULL) {// subroot 没有父, 则是某个树根 pointer = root; while (pointer->rightsibling()!= subroot)// 顺右链找左邻树根 pointer = pointer->rightsibling(); pointer->setsibling(subroot->rightsibling()); // 前后挂接, 脱链 else if (pointer->leftmostchild() == subroot) // subroot 为最左子 pointer->setchild(subroot->rightsibling()); // 挂新的最左 else {// subroot 有左兄弟的情况 pointer = pointer->leftmostchild(); // 下降到最左兄弟 while (pointer->rightsibling()!= subroot)// 顺右链找左邻兄弟 pointer = pointer->rightsibling(); pointer->setsibling(subroot->rightsibling()); // 前后挂接, 脱链 subroot->setsibling(null);// 非常重要, 丢了会出错 estroynodes(subroot); // 删除以 subroot 代表的子森林的所有结点 11
思考 : 下面的算法是否能遍历森林? template <class T> void Traverse(TreeNode <T> * rt) { if (rt==null) return; C Visit(rt); TreeNode * temp = rt-> LeftMostChild(); while (temp!= NULL) { Traverse(temp); temp = temp->rightsibling(); K J I X L N M L 12
思考 : 灵活应用遍历框架 例 : 森林镜面映射 13
映射后 14
思考 : 删除以 subroot 为根的子树 请注意待删除的子树是否为空 subroot 有无父指针等情况的判断 考虑删除以后各项相关链接的修改顺序 15
数据结构与算法 谢谢聆听 国家精品课 数据结构与算法 http://www.jpk.pku.edu.cn/pkujpk/course/sjjg/ 张铭, 王腾蛟, 赵海燕高等教育出版社,2008. 6 十一五 国家级规划教材