软件基础实验报告之二叉树

软件基础上机题之二叉树PAGEPAGE3

年级10级班号5

学号

10064132专业自动化

姓名

刘满实验名称

二叉树的相关操作实验类型设计型综合型创新型实验目的或要求实验目的：1.掌握二叉树的二叉链表存储结构；2.掌握利用二叉树创建方法3.掌握各种二叉树的遍历实现方法。实验要求：1.编写递归实现二叉树的中序、先序和后序遍历算法以及层次遍历算法和二叉树高度算法；2.编写主函数测试以上二叉树的创建和遍历函数。实验原理（算法流程）开始

开始输出主菜单选择界面输出主菜单选择界面输入x的值其他：输入x的值输入项无效，x=?请重新选择！x=?退出二叉树高度层次遍历后序遍历中序退出二叉树高度层次遍历后序遍历中序遍历先序遍历创建二叉树输入rturn的值输入rturn的值rturn=N假rturn=N真结束结束组内分工（可选）无实验结果分析及心得体会成绩评定教师签名：2010年月日#include"stdafx.h"#include<stdio.h>#include<stdlib.h>#include<string.h>#defineMAX(a,b)((a)>(b)?(a):(b))/*对比较函数进行宏定义*/#definelength100typedefchardatatype;typedefstructnode/*定义二叉树的存储方式*/{ datatypedata; structnode*lchild,*rchild;}bitree;bitree*creat_tree();/*创建二叉树*/voidpreorder(bitree*p);/*对二叉树进行先序遍历，p指向二叉树的根结点*/voidinorder(bitree*p);/*对二叉树进行中序遍历，p指向二叉树的根结点*/voidpostorder(bitree*p);/*对二叉树进行后序遍历，p指向二叉树的根结点*/voidlevelorder(bitree*p);/*对二叉树进行层次遍历，p指向二叉树的根结点*/intdepth_bitree(bitree*root);/*计算二叉树的深度*/voidmenu(){ printf("****************************************************\n"); printf("****************1.按先序递归方式创建二叉树**********\n"); printf("****************2.先序遍历二叉树********************\n"); printf("****************3.中序遍历二叉树********************\n"); printf("****************4.后序遍历二叉树********************\n"); printf("****************5.层次遍历二叉树********************\n"); printf("****************6.输出二叉树的高度******************\n"); printf("****************7.退出******************************\n"); printf("****************************************************\n");}voidmain(){ intx,k; charrturn; bitree*root; while(1) { system("cls");//清屏 menu(); printf("请选择相应功能："); fflush(stdin); scanf("%d",&x); switch(x) { case1://按先序递归方式创建二叉树 printf("请输入各结点以完成二叉树的创建：\n"); fflush(stdin); root=creat_tree(); printf("二叉树创建完成,是否继续？（N退出，任意键继续）\n"); fflush(stdin); scanf("%c",&rturn); if(rturn=='N') exit(0); break; case2://先序遍历二叉树 printf("先序遍历结果如下：\n"); preorder(root); printf("\n"); printf("先序遍历完成,是否继续？（N退出，任意键继续）\n"); fflush(stdin); scanf("%c",&rturn); //fflush(stdin); if(rturn=='N') exit(0); break; case3://中序遍历二叉树 printf("中序遍历结果如下：\n"); inorder(root); printf("\n"); printf("中序遍历完成,是否继续？（N退出，任意键继续）\n"); fflush(stdin); scanf("%c",&rturn); //fflush(stdin); if(rturn=='N') exit(0); break; case4://.后序遍历二叉树 printf("后序遍历结果如下：\n"); postorder(root); printf("\n"); printf("后序遍历完成,是否继续？（N退出，任意键继续）\n"); fflush(stdin); scanf("%c",&rturn); //fflush(stdin); if(rturn=='N') exit(0); break; case5://层次遍历二叉树 printf("层次遍历结果如下：\n"); levelorder(root); printf("\n"); printf("层次遍历完成,是否继续？（N退出，任意键继续）\n"); fflush(stdin); scanf("%c",&rturn); if(rturn=='N') exit(0); break; case6://输出二叉树的高度 k=depth_bitree(root); printf("二叉树的高度为：\n"); printf("%d",k); printf("\n"); printf("二叉树的高度输出完成,是否继续？（N退出，任意键继续）\n"); fflush(stdin); scanf("%c",&rturn); if(rturn=='N') exit(0); break; case7://退出 return; default: printf("输入选项无效！请重新输入！\n"); system("pause"); } } return;}bitree*creat_tree()/*创建二叉树*/{ charc; bitree*root; scanf("%c",&c); if(c=='@')root=NULL;/*此时为空树*/ else { root=(bitree*)malloc(sizeof(bitree));/*递归算法创建二叉树*/ root->data=c; root->lchild=creat_tree(); root->rchild=creat_tree();}return(root);/*返回根结点指针*/}voidpreorder(bitree*p)/*对二叉树进行先序遍历，p指向二叉树的根结点*/{ if(p!=NULL)/*判断二叉树为非空树*/ { printf("%c",p->data);/*采用递归算法先序遍历二叉树*/ preorder(p->lchild); preorder(p->rchild); } return;}voidinorder(bitree*p)/*对二叉树进行中序遍历，p指向二叉树的根结点*/{ if(p!=NULL)/*判断二叉树为非空树*/ { inorder(p->lchild);/*采用递归算法中序遍历二叉树*/ printf("%c",p->data); inorder(p->rchild); } return;}voidpostorder(bitree*p)/*对二叉树进行后序遍历，p指向二叉树的根结点*/ { if(p!=NULL)/*判断二叉树为非空树*/ { postorder(p->lchild);/*采用递归算法后序遍历二叉树*/ postorder(p->rchild); printf("%c",p->data); } return;}voidlevelorder(bitree*p)/*对二叉树进行层次遍历，p指向二叉树的根结点*/{ bitree*queue[length],*q; intfront,rear; front=rear=0; if(p!=NULL)/*判断二叉树为非空树*/ { queue[rear++]=p;/*采用队列，及递归算法对二叉树进行层次遍历*/ while(front!=rear) { q=queue[front++]; printf("%c",q->data); if(q->lchild!=NULL)queue[rear++]=q->lchild; if(q-