树与二叉树转换.pptxVIP

第1页/共20页　遍历二叉树的递归算法算法6.1　前序遍历二叉树的递归算法void preorder(bitree root)/* root为根结点，visit()为访问结点的函数 */{ if ( root !=0) /* 二叉树非空 */ { visit(root->data); /* 访问根结点 */ preorder(root->lchild); /* 遍历左子树（递归调用） */ preorder(root->rchild); /* 遍历右子树（递归调用） */ }}第2页/共20页　中序遍历二叉树的递归算法void Inorder(bitree root)/* root为根结点，visit()为访问结点的函数 */{ if ( root !=0) /* 二叉树非空 */ { Inorder(root->lchild); /* 遍历左子树（递归调用） */ visit(root->data); /* 访问根结点 */ Inorder(root->rchild); /* 遍历右子树（递归调用） */ }}第3页/共20页　后序遍历二叉树的递归算法void PostOrder(bitree root)/* root为根结点，visit()为访问结点的函数 */{ if ( root !=0) /* 二叉树非空 */ { PostOrder(root->lchild); /* 遍历左子树（递归调用） */ PostOrder(root->rchild); /* 遍历右子树（递归调用） */ visit(root->data); /* 访问根结点 */ }}第4页/共20页4.　二叉树的层次遍历二叉树的层次遍历:即按照“从上到下，从左至右”的次序访问所有结点一次且仅一次。对一棵非空的二叉树，先访问根结点，再依次访问左孩子、右孩子，并记录该层结点的访问次序；依次访问各结点的左孩子和右孩子，直到访问到最右端的叶子结点。层次遍历存在容易理解的非递归算法。这里有一个“依序访问下层结点”的问题，为了记录上一层结点的访问次序，需要使用队列。算法描述如下：1）初始化队列Q；2）将根结点入队列；3）当队列Q不空时，重复以下过程：{ 对头元素出队列，并访问该结点； 若该结点左孩子非空，访问左孩子并将左孩子入队； 若结点右孩子非空，访问右孩子并将右孩子入队；}实际上，结点的访问次序就是其进入队列的次序。 第5页/共20页二叉树层次遍历的算法（应用辅助队列）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); /* 右孩子入队 */ }} 第6页/共20页ABCDEFGHKL二、二叉树的建立算法（实验需掌握）按扩展的先序序列建立二叉树的算法要求输入时表示出叶子结点。如图所示：输入序列为：A B D # G L # # # E # # C F H # # K # # #其中的 # 表示空第7页/共20页算法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); /* 返回根