二叉树实验报告-15

实验报告实验目的与要求1.建立二叉树；2.对二叉树的先、中、后序遍历并输出遍历序列；3.实现二叉树的中序遍历非递归算法；4.实现二叉树交换其左右子女的算法。实验内容1.系统功能需求分析：由实验的目的与要求可知，本系统要主要是用于实现以上功能基于先序遍历的构造方法，建立图4-13（a）所示二叉树。并输入其扩充的先序序列（AB#C#D##EF##G##）输出二叉树的先、中、后序遍历序列非递归算法，实现二叉树的中序遍历交换其左右子女2.存储结构设计：二叉树可采用顺序存储结构，也可以采用链式存储结构对数据进行存储。但考虑到顺序存储结构比较适合于完全二叉树、满二叉树。对于图4-13（a）所示的二叉树，采用二叉链表存储结构较为合适。二叉链表结点除数据域外，还有两个链域：左孩子域、右孩子域分别指向其左右孩子。其结点类型定义如下：typedefstructnode{chardata;structnode*lchild,*rchild;}Node;3.我的源程序如下:#include"stdio.h"#include<malloc.h>typedefstructnode/*定义结点类型*/{chardata;structnode*lchild,*rchild;}Node;Node*createbintree()/*建立二叉树*/{Node*t;charx;scanf("%c",&x);if(x=='#')t=NULL;else{t=(Node*)malloc(sizeof(Node));t->data=x;t->lchild=createbintree();t->rchild=createbintree();}return(t);}voidpreorder(Node*t)/*先序遍历*/{if(t!=NULL){printf("%c",t->data);preorder(t->lchild);preorder(t->rchild);}}voidinorder(Node*t)/*中序遍历*/{if(t!=NULL){inorder(t->lchild);printf("%c",t->data);inorder(t->rchild);}}voidpostorder(Node*t)/*后序遍历*/{if(t!=NULL){postorder(t->lchild);postorder(t->rchild);printf("%c",t->data);}}voidinorder1(Node*t)/*非递归中序遍历*/{Node*p;Node*stack[20];inttop=0;p=t;while(p||top!=0){while(p){stack[top++]=p;p=p->lchild;}p=stack[--top];printf("%c",p->data);p=p->rchild;}}voidexchangeLR(Node*t)/*交换其左右子女*/{Node*tmp;if(t!=NULL){tmp=t->lchild;t->lchild=t->rchild;t->rchild=tmp;exchangeLR(t->lchild);exchangeLR(t->rchild);}}voidmain(){Node*t=NULL;inta;while(1){printf("\n\n\n\n\n\n\n\n\n\t\t按任意键进入主菜单....");getch();system("cls");printf("\t\t*****************09信管(1)班-关配-3109005656*************\n");printf("\n");printf("\t\t=======================================\n");printf("\t\t1.建立图4-13(a)所示二叉树\n");printf("\t\t2.二叉树的先序遍历\n");printf("\t\t3.二叉树的中序遍历\n");printf("\t\t4.二叉树的后序遍历\n");printf("\t\t5.二叉树的中序非递归遍历\n");printf("\t\t6.二叉树交换其左右子女\n");printf("\t\t=======================================\n");printf("\n\t请选择（0-6):");scanf("%d",&a);getchar();switch(a){case1:system("cls");printf("\n\n\n\n请输入图4-13(a)扩充的先序序列为:(AB#C#D##EF##G##):");t=createbintree();if(t==NULL)printf("创建二叉树失败!");break;case2:system("cls");printf("\n\n先序遍历为:");preorder(t);printf("\n");break;case3:system("cls");printf("\n\n中序遍历为:");inorder(t);printf("\n");break;case4:system("cls");printf("\n\n后序遍历为:");postorder(t);printf("\n");break; case5:system("cls");printf("\n\n中序非递归遍历为:");inorder1(t);printf("\n");break;case6:system("cls");exchangeLR(t);if(t)printf("\n\n已成功交换其左右子树");printf("\n");break;default:printf("输入错误,请重新输入!\n");} }}三、实验结果和数据处理1.所要建立的二叉如下图：BBECGFDD其先、中、后序序为：ABCDEFG，BCDAFEG，DCBFGEA交换左右子树后的先、中、后序列为：AEGFBCD，GEFADCB，GFEDCBA2.测试结果：运行程序(2)进行主菜单选择1，建立二叉树回到主菜单，依次分分别选择2、3、4，输出其先中后序递归遍历，其运行结果如下图，实验结果正确。回到主菜单选择5，其非递归中序遍历，如下图，结果正确。回到主菜单，选择6，将它的左右子树交换。回到主菜单，依次分分别选择2、3、4，输出其先中后序递归遍历，其运行结果如下图，交换后，实验结果正确。总结本次实验主要遇到两个问题，一个是自己解决的，另一个请教同学解决的。第一个问题是我编写好源程序后，编译没有问题。但在输入二叉树的扩充序列时没有问题，就无法输出，弹出对话框是“内存不能READ”，我在猜想：与内存相关的，应该是指针的问题吧。我认真检查了一下源程序，原来是遍历的函数出了问题，我忘记在if语句后三个语句加“{}”。第二个问题是我对程序进行改进时遇到的，我想对程序设计二级菜单，要用到“switch”语句。但在建立二叉树时即无法将扩充的先序序列输入去，请教了同学之后，原来是在“switch”后面的括号的整型数据的输入和建立二叉树输入的字符发生了冲突。加入了一个“getchar()”语