612森林与二叉树的等价转换 森林或树转化成二叉树的形式定义如下: 设有序集合F={T1,T2,…,T表示由树T1,T2,…,T组成的 森林,则森林F可以按如下规则递归转换成二叉树B(F): 口若F为空,即n=0,则B(F)为空。 口若F非空,即n>0,则B(F)的根是森林中第一棵 树T的根W1,B(F的左子树是树T1中根结点w1 的子树森林F={T1,T12,…,T1m}转换成的二 叉树B(T1,;T12,…,T1m);B(F的右子树是从森 林F”={I2,…,Tn}转换而成的二叉树。 “十一五”国家缀规划教材。张铭,王腾蛟,赵海￡,《飙据结构与算法》,高教社,B0.6
“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 6.1.2 森林与二叉树的等价转换 ◼ 森林或树转化成二叉树的形式定义如下： 设有序集合F = {T1，T2，…，Tn }表示由树T1，T2，…，Tn组成的 森林，则森林F可以按如下规则递归转换成二叉树B(F)： ❑ 若F为空，即n = 0，则B(F)为空。 ❑ 若F非空，即n > 0，则B(F)的根是森林中第一棵 树T1的根W1，B(F)的左子树是树T1中根结点W1 的子树森林F = {T11，T12，…，T1m}转换成的二 叉树B(T11，T12，…，T1m)；B(F)的右子树是从森 林F’ = {T2，…，Tn }转换而成的二叉树
612森林与二叉树的等价转换 二叉树转换为树或森林的操作 口旋转:以根为轴,平面逆时针方向旋转 口补线:若结点x是父结点y的左子结点, 则把x的右子结点,右子结点的右孩子, 依此类推,直到最右孩子,用连线与y连 起来 口删线:去掉所有父结点到右孩子的连线。 “十一五”国家缀规划教材。张铭,王腾蛟,赵海￡,《飙据结构与算法》,高教社,B0.6
“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 6.1.2 森林与二叉树的等价转换 ◼ 二叉树转换为树或森林的操作： ❑ 旋转：以根为轴，平面逆时针方向旋转。 ❑ 补线：若结点x是父结点y的左子结点， 则把x的右子结点，右子结点的右孩子， 依此类推，直到最右孩子，用连线与y连 起来。 ❑ 删线：去掉所有父结点到右孩子的连线
612森林与二叉树的等价转换 Q ① 图64二叉树转换为森林 “十一五”国家缀规划教材。张铭,王腾蛟,赵海￡,《飙据结构与算法》,高教社,B0.6
“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 6.1.2 森林与二叉树的等价转换 图6.4 二叉树转换为森林 A B C D E F G H I J A B C D E F G H J I (a) (b) (T1) (T2) (T3)
612森林与二叉树的等价转换 二叉树转化成森林或树的形式定义如下 设B是一棵二叉树,root是B的根,BL是 root的左子树,BR是root的右子树,则对 应于二叉树B的森林或树F(B的形式定义 是: 口若B为空,则F(B)是空的森林 口若B不为空,则F(B)是一棵树T加上森林 F(BR),其中树T1的根为root,root的子 树为F(BL) “十一五”国家缀规划教材。张铭,王腾蛟,赵海￡,《飙据结构与算法》,高教社,B0.6
“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 6.1.2 森林与二叉树的等价转换 ◼ 二叉树转化成森林或树的形式定义如下： 设B是一棵二叉树，root是B的根，BL是 root的左子树，BR是root的右子树，则对 应于二叉树B的森林或树F(B)的形式定义 是： ❑ 若B为空，则F(B)是空的森林 ❑ 若B不为空，则F(B)是一棵树T1加上森林 F(BR)，其中树T1的根为root，root的子 树为F(BL)
61.3树的抽象数据类型 【代码6.1】树结点的抽象数据类型 template<class t> class treeNode i public: TreeNode(const T& value); ∥拷贝构造函数 virtual -TreeNode0 0; ∥析构函数 bool is Leaf; ∥判断当前结点是否为叶结点 T Value0; ∥返回结点的值 TreeNode<t> leftMostchildo; ∥返回第一个左孩子 TreeNode<t>* rightsibling0; ∥返回右兄弟 void setvalue(const T& value); ∥设置当前结点的值 void getchild( TreeNode<I>* pointer;∥设置左孩子 void setsibling(treeNode<t>*pointer); ∥设置右兄弟 void insert first( TreeNode<T*node);∥以第一个左孩子身份插入结点 void InsertNext( TreeNode<T>*node);∥/以右兄弟的身份插入结点 十一五”国家級规划教材。张铭,王膳腾蛟,赵海燕,《数据结构与算法》,高教社,B08.6
“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 6.1.3 树的抽象数据类型 【代码6.1】树结点的抽象数据类型 template<class T> class TreeNode { public: TreeNode(const T& value); // 拷贝构造函数 virtual ~TreeNode() {}; // 析构函数 bool isLeaf(); // 判断当前结点是否为叶结点 T Value(); // 返回结点的值 TreeNode<T> *LeftMostChild(); // 返回第一个左孩子 TreeNode<T> *RightSibling(); // 返回右兄弟 void setValue(const T& value); // 设置当前结点的值 void setChild(TreeNode<T> *pointer); // 设置左孩子 void setSibling(TreeNode<T> *pointer); // 设置右兄弟 void InsertFirst(TreeNode<T> *node); // 以第一个左孩子身份插入结点 void InsertNext(TreeNode<T> *node); // 以右兄弟的身份插入结点 };