二叉树的创建与遍历操作.doc

年级11级班号 2 学号 11064061专业自动化 姓名 马俊杰实验名称 二叉树的创建和遍历实验类型设计型综合型创新型实验目的或要求实验要求:1)从键盘输入二叉树的各结点值,按先序递归方式创建二叉树2)分别实现先序、中序、后序递归遍历二叉树3)输出二叉树的高度4)输出二叉树的按层次遍历序列*5)以菜单方式运行先序方式创建二叉树:输入结点值的顺序必须对应二叉树先序遍历的顺序,并约定以某个字符(如’’或‘@’等):对于右图中的二叉树,按下列顺序输入字符:ABC@***@******@G@***@F@@@,创建二叉树。ABCDEFG实验原理(算法流程)#include<>#include<>#include<>#definemaxsize1024typedefchardatatype;typedefstructnode{ datatypedata; structnode*lchild,*rchild;}bitree;voidmenu(){ printf("本代码实现二叉树的如下基本功能,请选择对应的功能选项进行相应操作:\n"); printf("\n"); printf("\n"); printf("\n"); printf("\n"); printf("\n"); printf("\n"); printf("\n");}bitree*Creat(){ charch; bitree*T; scanf("%c",&ch); if(ch=='@') T=NULL; else { T=(bitree*)malloc(sizeof(bitree)); T->data=ch; T->lchild=Creat(); T->rchild=Creat(); } returnT;}voidpreorder(bitree*T){ if(T!=NULL) { printf("%c",T->data); preorder(T->lchild); preorder(T->rchild);} return;}voidinorder(bitree*T){ if(T!=NULL) { inorder(T->lchild); printf("%c",T->data); inorder(T->rchild); } return;}voidpostorder(bitree*T){ if(T!=NULL) { postorder(T->lchild); postorder(T->rchild); printf("%c",T->data); } return;}voidlevelorder(bitree*T){ bitree*q[20]; intfront=0,rear=0; if(T!=NULL) { rear++;q[rear]=T; } while(front!=rear) { front++; T=q[front]; printf("%c",T->data); if(T->lchild) { rear++;q[rear]=T->lchild;} if(T->rchild) { rear++;q[rear]=T->rchild;} }}intfstdepth(bitree*T){ intd1,d2; if(T==NULL)return0; else { d1=fstdepth(T->lchild); d2=fstdepth(T->rchild); return1+(d1>d2?d1:d2); }}voidmain(){ intchoice=0,dep; bitree*T; menu(); printf("本代码实现二叉树的几个基本功能,请选择对应的功能选项进行相应操作:"); fflush(stdin); scanf("%d",&choice); getchar(); while(1) { switch(choice) { case1: { printf("请按先序递归方式输入二叉树各结点:\n"); T=Creat(); printf("二叉树创建\n"); break; } case2: { preorder(T); break; } case3: { inorder(T); break; } case4: { postorder(T); break; }111********** case5: { levelorder(T); break; } case6: { dep=fstdepth(T); printf("二叉树的深度dep=%d\n",dep); break; } case0: exit(