二叉树操作实验报告.docx
XX学院实验报告课程名称数据结构实验名称二叉树操作系计算机与信息科学系班级专业班级教育技术学学号姓名实验日期2009-10-23实验教室多媒体实验室指导教师评阅意见一、实验目的和要求：（本次实验所涉及并要求掌握的知识点）二叉树是“数据结构”课程中的第一种非线性结构，通过本次实验帮助学生加深理解二 叉树的特点及其存储表示的理解；帮助学生熟练掌握二叉树的基本操作在链式存储结构表示 下的实现。要求：每位同学独立完成。二、实验环境：（本次实验所需要的平台和相关软件）可以在Visual C+、Turboc2.0、WinTC191下编程实现均可三、实验内容及步骤：（本次实验计划安排的实验内容和具体实现步骤）编写实现以下操作的算法，并上机调试、运行：1、实现对二叉树的先序、中序、后序遍历操作；2、求二叉树中结点数；3、求二叉树的深度；4、求二叉树的叶结点数；5、将二叉树中所有结点的左、右子树相互交换；提示：1、以二叉链表树表示二叉树，其类型定义如下：typedef struct BiTNode（ElemType data;struct BiTNode *lchild,*rchild;BiTNode,*BiTree;2、结点元素类型可以自由选取；3、一定注意，建立二叉链表树时结点数据输入顺序及结束符的添加。四、实验过程和结果：（记录实验过程和结果、以及所出现的问题和解决方法）1. 在windowsXP中打开wintc 191应用平台2. 编写一个菜单函数menu.3. 编写二叉树创建函数createbitree.4. 编写二叉树先序遍历函数preordertraverse.5. 编写二叉树中序遍历函数inordertraverse.6. 编写二叉树后序遍历函数postordertraverse.7. 编写求二叉树结点数的函数lnodenum.8. 编写求二叉树深度的函数height。9. 编写求二叉树叶结点数的函数leafnum。10. 编写二叉树左右子树函数changelr.11. 编写主函数main，并在其中调用以上函数。12. 调试并运行程序！实验的结果如下：1, 建树成功：D:PROGRA 1wintc¥in-TCprojectslqlTREE1. EXE*4.post trauer the tree * *5.the depth of the tree * *6.the leafs of the tree * *7.change the rchild and Ichild of the tree * *8.help * *9.exit *hplease input your choice -278963456*1.create the tree *2.preorder trauerse the tree * *3.inorder trauer the tree * *4.post trauer the tree *5.the depth of the tree * *6.the leafs of the tree * *7.change the rchild and Ichild of the tree *.help * *9.exit *网 D:PROGRA"lTintc¥in-TCprojectslqlTREEl.EIE*3.inorder trauer the tree。土 D: XPROGRAlXTintcXlin-TCXprojectsMqlXTKEE 1. EXE.post trauer the tree .the depth of the tree .the leafs of the tree .change the rcliild and .help .exitthe tree after change the left and right is: 78963456*1.create the tree * *2.preorder trauerse the tree * *3.inorder trauer the tree * *4.post trauer the tree * *5.the depth of the tree * 6.the leafs of the tree * *7.change the rchild and Icliild of the tree * *fl .help * *9 .exit *lease input uoiip choice*4.post trauer the tree*5.the depth of the tree*6.the leafs of the tree*7.change the rcliild and Ichild of the tree * «S . he Ip*9.exit*k>lease input your choice ：6the leafs of the tree is:2*1.create the tree*2.preorder trauerse thetree*3.inorder trauer the tree*4.post trauer the tree*5.the depth of the tree*6.the leafs of the tree*7.change the rcliild and Ichild of the tree *8 . he Ip*.exit*hplease input your cho ice : 7Icliild ofthe treek)lease input your cho ice :五、实验总结和思考：（填写收获和体会，分析成功或失败的原因）收获：只有通过不断练习，才能获取经验，避免下次犯同样的错误！成功和失败：在实验过程中，遇到了一些细节性的问题，不好寻找，导致结果错误。结果：找到了问题所在，发现了一些平时不曾注意的问题。附件：（源代码）/*说明1、树的元素类型为字符形；2、实现对二叉树的先序遍历操作；3、实现对二叉树的中序遍历操作；4、实现对二叉树的后序遍历操作；5、求二叉树的深度；6、求二叉树的叶结点数；7、将二叉树中所有结点的左、右子树相互交换;*/#include "stdio.h"#include "conio.h"#define OVERFLOW -1typedef char telemtype;typedef struct bitnodetelemtype data;struct bitnode *lchild,*rchild;bitnode,*bitree;void createbitree(bitree *t)telemtype ch;scanf("%c",&ch);if(ch=' ') *t=NULL;else*t=(bitnode *)malloc(sizeof(bitnode);if(!(*t) exit(OVERFLOW);(*t)->data=ch;createbitree(&(*t)->lchild);createbitree(&(*t)->rchild);return;void preordertraverse(bitree t)if(t)printf("%c ”,t->data);preordertraverse(t->lchild);preordertraverse(t->rchild);void inordertraverse(bitree t)if(t)inordertraverse(t->lchild);printf("%c ”,t->data);inordertraverse(t->rchild);void postordertraverse(bitree t)if(t)postordertraverse(t->lchild);postordertraverse(t->rchild);printf("%c ”,t->data);int height(bitree t)if(t=NULL) return 0;elsereturn(height(t->lchild)>(height(t->rchild)?(height(t->lchild)+1):(height(t->rchild)+1);int leafnum(bitree t)if(t=NULL) return 0;elseif(t->lchild=NULL)&&(t->rchild=NULL) return 1;else return(leafnum(t->lchild)+leafnum(t->rchild);void changelr(bitree *t)bitnode *p;if(*t)p=(*t)->lchild;(*t)->lchild=(*t)->rchild;(*t)->rchild=p;changelr(&(*t)->lchild);changelr(&(*t)->rchild); return ;int menu()printf("ttt*n");printf("ttt*1.create the tree*n");printf("ttt*2.preorder traverse the tree*n");printf("ttt*3.inorder traver the tree*n");printf("ttt*4.post traver the tree*n");printf("ttt*5.the depth of the tree*n");printf("ttt*6.the leafs of the tree*n");printf("ttt*7.change the rchild and lchild of the tree *n");printf("ttt*8.help*n");printf("ttt*9.exit*n");printf("ttt*n");printf("n");printf("please input your choice:");main() int a,i;bitree t;while(1)menu();scanf("%d”,&a);switch(a)case 1:printf("please input the elem of the tree inpreorder:n");createbitree(&t);printf("n");break;case 2: printf("n");preordertraverse(t);printf("n");break;case 3: printf("n");inordertraverse(t);printf("n");break;case 4: printf("n");postordertraverse(t);printf("n");break;case 5: printf("n the depth of the tree is:");i=height(t);printf("%dn”,&i);break;case 6: printf("n the leafs of the tree is:");i=leafnum(t);printf("%dn”,&i);break;case 7: printf("n the tree after change the left and right is:"); preordertraverse(t);printf("n");break;case 8: printf("help");break;case 9: exit(0);getch();
