森林与二叉树的等价转换 G ○○○ E 11 l○ K h J 12 G 北京大学信息学院 版权所有,转载或翻印必究 Page 16
北京大学信息学院 ©版权所有，转载或翻印必究 Page 16 森林与二叉树的等价转换
森林到二叉树的等价转换 把森林F看作树的有序集合,F=(T1,T2,…, Tn),对应于F的二又树B(F)的定义是: 若n=0,则B(F)为空 若n>0,则B(F)的根是T的根W1,B(F)的左子树是 B(T1,T12,…,T1m),其中T1,T12,…,T1m是 W1的子树;B(F)的右子树是B(T2,…,T 此定义精确地确定了从森林到二叉树的转换 北京大学信息学院 版权所有,转载或翻印必究 Page 17
北京大学信息学院 ©版权所有，转载或翻印必究 Page 17 森林到二叉树的等价转换 ◼ 把森林F看作树的有序集合，F=(T1，T2，…， Tn)，对应于F的二叉树B(F)的定义是： ◼ 若n=0，则B（F）为空 ◼ 若n>0，则B(F)的根是T1的根W1，B(F)的左子树是 B(T11，T12，…，T1m)，其中T11，T12，…，T1m是 W1的子树；B(F)的右子树是B(T2，…，Tn) ◼ 此定义精确地确定了从森林到二叉树的转换
森林到二叉树的等价转换 设B是一棵二叉树,tt是B的根,L是rt的左 子树,R是rt的右子树,则对应于B的森林 F(B)的定义是: 若B为空,则F(B)是空的森林。 若B不为空,则F(B是一棵树T加上森林F(R), 其中树T的根为t,的子树为F(L) 北京大学信息学院 版权所有,转载或翻印必究 Page 18
北京大学信息学院 ©版权所有，转载或翻印必究 Page 18 森林到二叉树的等价转换 ◼ 设B是一棵二叉树，rt是B的根，L是rt的左 子树，R是rt的右子树，则对应于B的森林 F(B)的定义是： ◼ 若B为空，则F(B)是空的森林。 ◼ 若B不为空，则F(B)是一棵树T1加上森林F(R)， 其中树T1的根为rt，rt的子树为F(L)
树/森林的抽象数据类型 template<class T> class tree node public: TreeNode( const t&)//拷贝构造函数 virtual|~ TreeNodeo{};/析构函数 bool isLeafO; /如果结点是叶,返回true T; /返回结点的值 Treenode<T>* LeftMostchildo//返回第一个左孩子 TreeNode<T>* Rightsibling;∥/返回右兄弟 北京大学信息学院 版权所有,转载或翻印必究 Page 19
北京大学信息学院 ©版权所有，转载或翻印必究 Page 19 树/森林的抽象数据类型 template<class T> class TreeNode { public: TreeNode(const T&);//拷贝构造函数 virtual ~TreeNode(){}; //析构函数 bool isLeaf(); //如果结点是叶，返回true T Value(); //返回结点的值 TreeNode<T>* LeftMostChild(); //返回第一个左孩子 TreeNode<T>* RightSibling(); //返回右兄弟
树/森林的抽象数据类型 void setvalue(T&x)/设置结点的值 /设置左子结点 void setchild(treeNode<T>*k pointer) /设置右兄弟 void setsibling (TreeNode<T>* pointer)i /以第一个左子结点身份插入结点 void InsertFirst(TreeNode<T>*k node); /以右兄弟的身份插入结点 void InsertNext(TreeNode<t>k node)i 北京大学信息学院 版权所有,转载或翻印必究 Page 20
北京大学信息学院 ©版权所有，转载或翻印必究 Page 20 树/森林的抽象数据类型 void setValue(T&); //设置结点的值 //设置左子结点 void setChild(TreeNode<T>* pointer); //设置右兄弟 void setSibling(TreeNode<T>* pointer); //以第一个左子结点身份插入结点 void InsertFirst(TreeNode<T>* node); //以右兄弟的身份插入结点 void InsertNext(TreeNode<T>* node); };