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

《二叉树的创建与遍历操作.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、年级11级班号 2 学号 专业自动化 姓名 马俊杰实验名称 二叉树的创建和遍历实验类型设计型综合型创新型实验目的或要求实验要求：1）从键盘输入二叉树的各结点值，按先序递归方式创建二叉树2）分别实现先序、中序、后序递归遍历二叉树3）输出二叉树的高度4）输出二叉树的按层次遍历序列*5）以菜单方式运行先序方式创建二叉树：输入结点值的顺序必须对应二叉树先序遍历的顺序，并约定以某个字符（如’’或‘@’等）作为空子树.例如：对于右图中的二叉树,按下列顺序输入字符:ABC@@DE@G@@F@@@，创建二叉树。ABCDEFG实验原理（算法流程）#include#i

2、nclude#include#definemaxsize1024typedefchardatatype;typedefstructnode{datatypedata;structnode*lchild,*rchild;}bitree;voidmenu(){printf("本代码实现二叉树的如下基本功能，请选择对应的功能选项进行相应操作：");printf("1.按先序递归方式创建二叉树");printf("2.先序递归遍历");printf("3.中序递归遍历");printf("4.后序递归遍历");pr

3、intf("5.按层次遍历");printf("6.输出二叉树高度");printf("0.退出程序");}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(

4、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

5、];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->rc

6、hild);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("请按先序递归方式输入二叉树各结点：");T=Creat();printf("二叉树创建");break;}case2:{preorder(T);break;}cas

7、e3:{inorder(T);break;}case4:{postorder(T);break;}111case5:{levelorder(T);break;}case6:{dep=fstdepth(T);printf("二叉树的深度dep=%d",dep);break;}case0:exit(0);}menu();printf("本代码实现二叉树的几个基本功能，请选择对应的功能选项进行相应操作：");fflush(stdin);scanf("%d",&choice);getchar();}}组内分工（可选）无实验结果分析及心得体会成绩评定教师签名：2010