数据结构实验报告树(3)董华伟.doc

《数据结构实验报告树(3)董华伟.doc》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、数据结构实验报告院系名称：信息学院专业班级：计科1001班姓名：董华伟学号：201046830104一.需求分析：掌握二叉树的存储结构以及其各种操作，包括二叉树的建立，二叉树的前序遍历，中序遍历和后序遍历。二.概要设计存储结构的定义如下：typedefstructBinTNode{chardata;structBinTNode*lch,*rch;}BinTNode,*BinTree功能函数：voidCreatBinTree(BinTree&t)功能：创建二叉树voidPreOrderTraverse(Bin

2、Treet)功能：前序遍历二叉树voidInOerderTraverse(BinTreet)功能：中序遍历二叉树ivoidLevelOrder(BinTreet)功能：层次遍历二叉树intBinTreeLeaf(BinTNode*t)功能：计算二叉树的叶子个数三、源程序#include#includeintf=0;typedefstructBinTNode{chardata;structBinTNode*lch,*rch;}BinTNode,*BinTree;//创建二

3、叉树voidCreatBinTree(BinTree&t){charch;fflush(stdin);printf("请输入二叉树元素，用*表示空节点");scanf("%c",&ch);if(ch=='*')t=NULL;else{if(!(t=(BinTNode*)malloc(sizeof(BinTNode))))exit(-2);t->data=ch;CreatBinTree(t->lch);CreatBinTree(t->rch);}}//前序遍历二叉树voidPreOrderTraverse

4、(BinTreet){if(t){printf("%c",t->data);PreOrderTraverse(t->lch);PreOrderTraverse(t->rch);}}//中序遍历二叉树voidInOerderTraverse(BinTreet){BinTrees[100];inttop=0;inta=1;do{while(t){s[top]=t;top++;t=t->lch;}if(top==0)a=0;else{top--;t=s[top];printf("%c",t->data);t=t-

5、>rch;}}while(a);}//层次遍历二叉树voidLevelOrder(BinTreet){BinTreequeue[100];intfront=-1;intrear=0;BinTreep=t;queue[rear]=p;while(front!=rear){p=queue[++front];printf("%c",p->data);if(p->lch)queue[++rear]=p->lch;if(p->rch)queue[++rear]=p->rch;}}//计算二叉树的叶子个数intBi

6、nTreeLeaf(BinTNode*t){if(t){if(t->lch==NULL&&t->rch==NULL){f=+1;}else{BinTreeLeaf(t->lch);BinTreeLeaf(t->rch);}}returnf;}voidmain(){structBinTNode*t=NULL;intk;do{printf("-------------");printf("0.退出");printf("1.创建二叉树");printf("2.先序遍历");printf("3.中序

7、遍历");printf("4.层次遍历");printf("5.计算叶子个数");printf("----------------");printf("pleaseselectthenum：");scanf("%d",&k);switch(k){case1:CreatBinTree(t);break;case2:PreOrderTraverse(t);break;case3:InOerderTraverse(t);break;case4:LevelOrder(t);break;case5:B

8、inTreeLeaf(t);printf("该二叉树叶子节点个数为:%d",f);break;case0:break;default:printf("Error.Pleaseinputagain.");break;}}while(k!=0);}四.实验结果