形式化:森林到二叉树 把森林F看作树的有序集合,F=(T1,T2,…, T),对应于F的二叉树B(F的定义是: n若n=0,则B(F)为空 n若n>0,则B(F)的根是T1的根W1,B(F)的左子树是 B(T1,T12,…,T1m),其中T1,T12,…,T1m是 W1的子树;B(F)的右子树是B(T2,…,Tn) 此定义精确地确定了从森林到二叉树的转换 北京大学信息学院 张铭编写 版权所有,转载或翻印必究 Page 21
北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 21 形式化：森林到二叉树 把森林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)是一棵树T1加上森林 F(R),其中树T的根为t,t的子树为F(L) 北京大学信息学院 张铭编写 版权所有,转载或翻印必究 Page 22
北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 22 形式化：二叉树到森林 设B是一棵二叉树，rt是B的根，L是rt的左 子树，R是rt的右子树，则对应于B的森林 F(B)的定义是： 若B为空，则F(B)是空的森林。 若B不为空，则F(B)是一棵树T1加上森林 F(R)，其中树T1的根为rt，rt的子树为F(L)
51.3树/森林的结点ADT(1) template<class T> class TreeNode public: TreeNode( const T&)//拷贝构造函数 virtual~ Treenode({}//析构函数 bool isLeafoi /如果结点是叶,返回true T ValueOr /返回结点的值 TreeNode<T>* LeftMostchild(;∥/返回第一个左孩子 TreeNode<T>* Rightsibling o;//返回右兄弟 北京大学信息学院 张铭编写 版权所有,转载或翻印必究 Page 23
北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 23 5.1.3 树/森林的结点ADT(1) template<class T> class TreeNode { public: TreeNode(const T&);//拷贝构造函数 virtual ~TreeNode(){}; //析构函数 bool isLeaf(); //如果结点是叶，返回true T Value(); //返回结点的值 TreeNode<T>* LeftMostChild(); //返回第一个左孩子 TreeNode<T>* RightSibling(); //返回右兄弟
树/森林的结点ADT(2) void setValue(T&);//设置结点的值 /设置左子结点 void setChild(treeNode<T>* pointer)i /设置右兄弟 void setsibling (treeNode<T>* pointer) /以第一个左子结点身份插入结点 void InsertFirst(TreeNode<T>* node); /以右兄弟的身份插入结点 void InsertNext(TreeNode<T>k node) Fi 北京大学信息学院 张铭编写 版权所有,转载或翻印必究 Page 24
北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 24 树/森林的结点ADT(2) void setValue(T&); //设置结点的值 //设置左子结点 void setChild(TreeNode<T>* pointer); //设置右兄弟 void setSibling(TreeNode<T>* pointer); //以第一个左子结点身份插入结点 void InsertFirst(TreeNode<T>* node); //以右兄弟的身份插入结点 void InsertNext(TreeNode<T>* node); };
树/森林的ADT(1) template <class t> class tree { public: TreeO /构造函数 virtual~Tree(;//析构函数 ∥/返回树中的根结点 TreeNode<T>k getRooto /创建树中的根结点,使根结点元素的值为 rootvalue void CreateRoot(const T& rootValuei /判断是否为空树,如果是则返回true bool isEmpty or 北京大学信息学院 张铭编写 版权所有,转载或翻印必究
北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 25 树/森林的ADT(1) template <class T> class Tree { public: Tree(); //构造函数 virtual ~Tree(); //析构函数 //返回树中的根结点 TreeNode<T>* getRoot(); //创建树中的根结点，使根结点元素的值为rootValue void CreateRoot(const T& rootValue); //判断是否为空树，如果是则返回true bool isEmpty();