《树与二叉树的转换》PPT课件.ppt

1、2020/10/9,1,本课内容,1.遍历二叉树的算法（复习） 2.建立二叉树的算法 3.恢复二叉树 4.树、森林与二叉树的转换,遍历二叉树的递归算法,算法6.1前序遍历二叉树的递归算法 void preorder(bitree root) /* root为根结点，visit()为访问结点的函数 */ if ( root !=0)/* 二叉树非空 */ visit(root-data);/* 访问根结点 */ preorder(root-lchild);/* 遍历左子树（递归调用） */ preorder(root-rchild);/* 遍历右子树（递归调用） */ ,中序遍历二叉树的递归算法

2、 void Inorder(bitree root) /* root为根结点，visit()为访问结点的函数 */ if ( root !=0)/* 二叉树非空 */ Inorder(root-lchild);/* 遍历左子树（递归调用） */ visit(root-data);/* 访问根结点 */ Inorder(root-rchild);/* 遍历右子树（递归调用） */ ,后序遍历二叉树的递归算法 void PostOrder(bitree root) /* root为根结点，visit()为访问结点的函数 */ if ( root !=0)/* 二叉树非空 */ PostOrder(

3、root-lchild);/* 遍历左子树（递归调用） */ PostOrder(root-rchild);/* 遍历右子树（递归调用） */ visit(root-data);/* 访问根结点 */ ,4.二叉树的层次遍历,二叉树的层次遍历:即按照“从上到下，从左至右”的次序访问所有结点一次且仅一次。对一棵非空的二叉树，先访问根结点，再依次访问左孩子、右孩子，并记录该层结点的访问次序；依次访问各结点的左孩子和右孩子，直到访问到最右端的叶子结点。 层次遍历存在容易理解的非递归算法。这里有一个“依序访问下层结点”的问题，为了记录上一层结点的访问次序，需要使用队列。算法描述如下： 1）初始化队列Q

4、； 2）将根结点入队列； 3）当队列Q不空时，重复以下过程： 对头元素出队列，并访问该结点； 若该结点左孩子非空，访问左孩子并将左孩子入队； 若结点右孩子非空，访问右孩子并将右孩子入队； 实际上，结点的访问次序就是其进入队列的次序。,二叉树层次遍历的算法（应用辅助队列） void BTlayer( bitree root) linkqueue Q; /辅助队列 bitree P=root;/* P指向根结点 */ Init_queue(Q);/* 初始化队列 */ if (root) In_queue(Q,root); /* 根结点入队 */ while ( Q.front) /* 队列Q不空

5、时继续 */ P=dele_queue(Q);/* 出队，队头元素=P */ printf(“%c”,P-data);/* 访问结点数据 */ if (P-lchild) In_queue(Q,P-lchild);/* 左孩子入队 */ if (P-rchild) In_queue(Q,P-rchild); /* 右孩子入队 */ ,二、二叉树的建立算法（实验需掌握）,按扩展的先序序列建立二叉树的算法 要求输入时表示出叶子结点。 如图所示： 输入序列为： A B D # G L # # # E # # C F H # # K # # # 其中的 # 表示空,算法6.4 按扩展先序序列建立二叉树

6、的算法,typedef char elemtype ;/* 结点数据为char型 */ bitree creatbit() /* 按输入的前序序列建立二叉树，输入以回车表示结束 */ /* 若创建成功，返回该二叉树的根，否则返回空指针 */ char ch; bitree T; scanf(“%c”,/* 返回根 */ ,遍历算法的应用,在遍历算法的基础上完成以下算法： 1.统计二叉树中的叶子结点个数 2.求二叉树的深度 3.统计二叉树中的结点总数,/统计二叉树深度的算法 int deepth(tnode *root) int lh,rh; if (root) /二叉树非空 lh=deepth

7、(root-lchild); /统计左子树深度 rh= deepth(root-rchild); /统计右子树深度 return (lhrh? lh: rh)+1; /最大深度+1 else return 0; ,三、构造二叉树,给定二叉树的一种遍历结果是无法确定二叉树的; 恢复二叉树指：根据给定的两种遍历结果，反推出该二叉树。 给定2 种遍历结果(中序、先序；或中序、后序）可唯一确定一棵二叉树； 注意：必须包括中序遍历。,练习：,1.由前序和中序遍历的序列构造二叉树 2.由后序和中序遍历的序列构造二叉树,2020/10/9,2020/10/9,13,树与二叉树的对应关系 树与二叉树均可用二叉

8、链表作为存储结构，因此给定一棵树，用二叉链表存储，可唯一对应一棵二叉树，反之亦然。 2树转换成二叉树 将一棵树转化为等价的二叉树方法如下： (1) 在树中各兄弟（堂兄弟除外）之间加一根连线。 (2) 对于任一结点，只保留它与最左孩子的连线，删去它与其余孩子之间的连线。 (3) 以树根为轴心，将整棵树按顺时钟方向旋转约45。 特点：根结点无右子树,6.4 树、森林与二叉树的转换,2020/10/9,14,图6-15树转换成二叉树,2020/10/9,15,3森林转换成二叉树 树和森林都可转换成二叉树，但树转换成二叉树后根结点无右分支，而森林转换后的二叉树，其根结点有右分支。 将森林转化为二叉树方

9、法如下： (1) 将森林中的每一棵树转换成等价的二叉树。 (2) 保留第一棵二叉树，自第二棵二叉树始，依次将后一棵二叉树的根结点作为前一棵二叉树根结点的右孩子，当所有的二叉树依此相连后，所得到的二叉树就是由森林转化成的二叉树。 (3) 以树根为轴心，将整棵树按顺时钟方向旋转约45。 转换过程如图图6-16 。,2020/10/9,16,图6-16 森林和对应的二叉树,2020/10/9,17,4二叉树转换成森林 将当前根结点和其左子树作为森林的一棵树,并将其右子树作为 森林的其他子树； 重复上面直到某结点的右子树为空。,2020/10/9,18,6.4.3树与森林的遍历,1. 树的遍历 按访问

10、根结点和访问子树的次序不同，可以定义以下所述两种遍历方法: （1）先根遍历（或先序遍历） 若树非空，则遍历过程为： 第一步：访问根结点； 第二步：从左到右，依次先根遍历根结点的每一棵子树。 （2）后根遍历（或后序遍历） 若树非空，则遍历过程为： 第一步：从左到右，依次后根遍历根的每一棵子树； 第二步：访问根结点。 对照转换后所得二叉树可以发现：树的先根遍历与其转换后所得的二叉树的先根遍历结果一样，而树的后根遍历则对应该二叉树的中序遍历。所以，可以用二叉树的遍历算法解决树的遍历问题。,2020/10/9,19,2020/10/9,20,练习,1. 已知一棵二叉树的先序序列为E B A D C F H G I K J，中序序列为A B C D E F G H I J K，请画出该二叉树，并写出后序遍历的结果。 2. 已知二叉树有50个叶子结点，则该二叉树的总结点数至少应有多少个