树/森林的抽象数据类型 template <class t> class Tree public: Tree()i //构造函数 virtual~ Treeo;//析构函数 ∥/返回树中的根结点 TreeNode<T>* getRootOi /创建树中的根结点,使根结点元素的值为 rootvalue void CreateRoot(const T& rootValue) /判断是否为空树,如果是则返回true bool isEmptyo 北京大学信息学院 版权所有,转载或翻印必究 Page 21
北京大学信息学院 ©版权所有，转载或翻印必究 Page 21 树/森林的抽象数据类型 template <class T> class Tree { public: Tree(); //构造函数 virtual ~Tree(); //析构函数 //返回树中的根结点 TreeNode<T>* getRoot(); //创建树中的根结点，使根结点元素的值为rootValue void CreateRoot(const T& rootValue); //判断是否为空树，如果是则返回true bool isEmpty();
树/森林的抽象数据类型 7返回 current结点的父结点 TreeNode<T>k Parent(TreeNode<T>k current); /返回 current结点的前一个邻居结点 TreeNode<T>* Prev sibling (treenode<t>x current); //删除以 subroot为根的子树的所有结点 void Delete SubTree(TreeNode<T>x subroot); ∥/先根深度优先周游树 void RootFirstTraverse(TreeNode<T>* root; /后根深度优先周游树 void RootLastTraverse(TreeNode<T>*k root) ∥/宽度优先周游树 void widthTraverse (TreeNode<T>k root; 北京大学信息学院 版权所有,转载或翻印必究 Page 22
北京大学信息学院 ©版权所有，转载或翻印必究 Page 22 树/森林的抽象数据类型 //返回current结点的父结点 TreeNode<T>* Parent(TreeNode<T>* current); //返回current结点的前一个邻居结点 TreeNode<T>* PrevSibling(TreeNode<T>* current); //删除以subroot为根的子树的所有结点 void DeleteSubTree(TreeNode<T>* subroot); //先根深度优先周游树 void RootFirstTraverse(TreeNode<T>* root); //后根深度优先周游树 void RootLastTraverse(TreeNode<T>* root); //宽度优先周游树 void WidthTraverse(TreeNode<T>* root); };
森林的周游 按深度的方向周游 先根次序: a)访问头一棵树的根 b)在先根次序下周游头一棵树树根的子树 c)在先根次序下周游其他的树 后根次序: a)在后根次序下周游头一棵树树根的子树 b)访问头一棵树的根 c)在后根次序下周游其他的树 北京大学信息学院 版权所有,转载或翻印必究 Page 23
北京大学信息学院 ©版权所有，转载或翻印必究 Page 23 森林的周游 ◼ 按深度的方向周游 ◼ 先根次序： a)访问头一棵树的根 b)在先根次序下周游头一棵树树根的子树 c)在先根次序下周游其他的树 ◼ 后根次序： a)在后根次序下周游头一棵树树根的子树 b)访问头一棵树的根 c)在后根次序下周游其他的树
先根深度优先周游森林 template <class T> void Tree<T>: RootFirstTraverse(TreeNode<t>k root while(root!=NULL) Visit(rot> Valued)//访问当前结点 /周游头一棵树树根的子树 RootFirstTraverse (root->LeftMostchildo) root=root-> Rightsibling(://周游其他的树 北京大学信息学院 版权所有,转载或翻印必究 Page 24
北京大学信息学院 ©版权所有，转载或翻印必究 Page 24 先根深度优先周游森林 template <class T> void Tree<T>::RootFirstTraverse(TreeNode<T>* root) { while(root!=NULL) { Visit(root->Value()); //访问当前结点 //周游头一棵树树根的子树 RootFirstTraverse(root->LeftMostChild()); root=root->RightSibling();//周游其他的树 } }
后根深度优先周游森林 template <class T> void Tree<t>: RootlastTraverse( Treenode<t>* root) { while (root ! ENULL) /周游头一棵树树根的子树 RootLastTraverse(root->LeftMostChildoi Visit(root->vaue()//访问当前结点 root=root-> Rightsibling(;//周游其他的树 北京大学信息学院 版权所有,转载或翻印必究 Page 25
北京大学信息学院 ©版权所有，转载或翻印必究 Page 25 后根深度优先周游森林 template <class T> void Tree<T>::RootLastTraverse ( TreeNode<T>* root) { while (root !=NULL) { //周游头一棵树树根的子树 RootLastTraverse (root->LeftMostChild()); Visit (root->Value());//访问当前结点 root=root->RightSibling();//周游其他的树 } }