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

年级11级班号 2学号11064061专业自动化姓名马俊杰实验名称二叉树的创建和遍历实验类型设计型综合型创新型实验目的或要求实验要求：1）从键盘输入二叉树的各结点值，按先序递归方式创建二叉树2）分别实现先序、中序、后序递归遍历二叉树3）输出二叉树的高度4）输出二叉树的按层次遍历序列*5）以菜单方式运行先序方式创建二叉树： 输入结点值的顺序必须对应二叉树先序遍历的顺序，并约定以某个字符（如 或等）作为空子树. 例如：对于右图中的二叉树, 按下列顺序输入字符: ABCDEGF ，创建二叉树。ABCDEFG实验原理（算法流程）#include #include #include #define maxsize 1024typedef char datatype;typedef struct nodedatatype data;struct node *lchild,*rchild;bitree;void menu()printf(本代码实现二叉树的如下基本功能，请选择对应的功能选项进行相应操作：n);printf(1.按先序递归方式创建二叉树n);printf(2.先序递归遍历n);printf(3.中序递归遍历n);printf(4.后序递归遍历n);printf(5.按层次遍历n);printf(6.输出二叉树高度n);printf(0.退出程序n);bitree *Creat()char ch;bitree *T;scanf(%c,&ch);if(ch=)T=NULL;elseT=(bitree*)malloc(sizeof(bitree);T-data=ch;T-lchild=Creat();T-rchild=Creat();return T; void preorder(bitree *T)if(T!=NULL)printf(%c,T-data);preorder(T-lchild);preorder(T-rchild);return;void inorder(bitree *T)if(T!=NULL)inorder(T-lchild);printf(%c,T-data);inorder(T-rchild);return;void postorder(bitree *T)if(T!=NULL)postorder(T-lchild);postorder(T-rchild);printf(%c,T-data);return;void levelorder(bitree *T) bitree *q20;int front=0,rear=0;if(T!=NULL) rear+;qrear=T;while(front!=rear)front+;T=qfront; printf(%c,T-data);if(T-lchild)rear+;qrear=T-lchild;if(T-rchild)rear+;qrear=T-rchild;int fstdepth(bitree *T)int d1,d2;if(T=NULL) return 0;elsed1=fstdepth(T-lchild);d2=fstdepth(T-rchild);return 1+(d1d2?d1:d2); void main()int choice=0,dep;bitree *T;menu();printf(本代码实现二叉树的几个基本功能，请选择对应的功能选项进行相应操作：);fflush(stdin);scanf(%d,&choice);getchar();while(1)switch(choice)case 1:printf(请按先序递归方式输入二叉树各结点：n);T=Creat();printf(二叉树创建n);break;case 2:preorder(T);break;case 3:inorder(T);break;case 4:postorder(T);break;11111111111111case 5:levelorder(T);break;case 6:dep=fstdepth(T);printf(二叉树的深度dep=%dn,dep);break;case 0:exit(0);menu();printf(本代码实现二叉树的几个基本功能，请选择对应的功能选项进行相应操作：);