第7课 树及二叉树的转换.pptVIP

* * 本课内容 　遍历二叉树的递归算法 　中序遍历二叉树的递归算法 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(root-lchild); /* 遍历左子树（递归调用） */ PostOrder(root-rchild); /* 遍历右子树（递归调用） */ visit(root-data); /* 访问根结点 */ } } 4.　二叉树的层次遍历 二叉树的层次遍历:即按照“从上到下，从左至右”的次序访问所有结点一次且仅一次。对一棵非空的二叉树，先访问根结点，再依次访问左孩子、右孩子，并记录该层结点的访问次序；依次访问各结点的左孩子和右孩子，直到访问到最右端的叶子结点。 层次遍历存在容易理解的非递归算法。这里有一个“依序访问下层结点”的问题，为了记录上一层结点的访问次序，需要使用队列。算法描述如下： 1）初始化队列Q； 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不空时继续 */ { 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 # # # 其中的 # 表示空 A B C D E F H G K L 算法6.4 按扩展先序序列建立二叉树的算法 typedef char elemtype ; /* 结点数据为char型 */ bitree creatbit() /* 按输入的前序序列建立二叉树，输入以回车表示结束 */ /* 若创建成功，返回该二叉树的根，否则返回空指针 */ { char ch; bitree T; scanf(“%c”,ch); if (ch==’#’) return (0); /* 返回空二叉树 */ else { T=(bitree)malloc(sizeof(bnode)); /* 生成“根”结点 */ T-data=ch; T-lchild=creatbit(); /* 创建左子树 */ T-rchild=creatbit(); /* 创建右子树 */ return (T); /* 返回根 */ } } 遍历算法的应用 在遍历算法的基础上完成以下算法： 1.统计二