树与二叉树的转换

《树与二叉树的转换》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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

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

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

4、孩子并将左孩子入队；若结点右孩子非空，访问右孩子并将右孩子入队；}实际上，结点的访问次序就是其进入队列的次序。二叉树层次遍历的算法（应用辅助队列）voidBTlayer(bitreeroot){linkqueueQ;//辅助队列bitreeP=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_q

5、ueue(Q,P->lchild);/*左孩子入队*/if(P->rchild)In_queue(Q,P->rchild);/*右孩子入队*/}}二、二叉树的建立算法（实验需掌握）按扩展的先序序列建立二叉树的算法要求输入时表示出叶子结点。如图所示：输入序列为：ABD#GL###E##CFH##K###其中的#表示空ABCDEFHGKL算法6.4按扩展先序序列建立二叉树的算法typedefcharelemtype;/*结点数据为char型*/bitreecreatbit()/*按输入的前序序列建立二叉树，输入以回车表示结束*//*若创建成功，返回该二叉树的根，否则返回空指针*/{charch;

6、bitreeT;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.统计二叉树中的叶子结点个数2.求二叉树的深度3.统计二叉树中的结点总数//统计二叉树深度的算法intdeepth(tnode*root){intlh,rh;if(

7、root)//二叉树非空{lh=deepth(root->lchild);//统计左子树深度rh=deepth(root->rchild);//统计右子树深度return(lh>rh?lh:rh)+1;//最大深度+1}elsereturn0;}}三、构造二叉树给定二叉树的一种遍历结果是无法确定二叉树的;恢复二叉树指：根据给定的两种遍历结果，反推出该二叉树。给定2种遍历结果(中序、先序；或中序、后序）可唯一确