数据结构二叉树实验

1、数据结构二叉树实验二、【实验设计 ( Design) 】(20%)(本部分应包括：抽象数据类型的功能规格说明、主程序模块、各子程序模块的伪码 说明，主程序模块与各子程序模块间的调用关系)二叉树的存储结构：typedef struct BiTNodechar data;struct BiTNode *lchild,*rchild; BiTNode,*BiTree;子程序模块： BiTree Create(BiTree T)char ch;ch=getchar();if(ch='#')T=NULL;elseif(!(T=(BiTNode *)malloc(sizeof(BiTNod

2、e)printf("Error!");T->data=ch;T->lchild=Create(T->lchild);T->rchild=Create(T->rchild);return T;void Preorder(BiTree T)if(T)printf("%c",T->data);Preorder(T->lchild);Preorder(T->rchild);int Sumleaf(BiTree T)int sum=0,m,n;if(T)if(!T->lchild)&&(!T-&

3、gt;rchild) sum+;m=Sumleaf(T->lchild); sum+=m;n=Sumleaf(T->rchild);sum+=n;return sum;void Inorder(BiTree T)if(T)Inorder(T->lchild);printf("%c",T->data);Inorder(T->rchild);void Postorder(BiTree T)if(T)Postorder(T->lchild);Postorder(T->rchild); printf("%c",T->

4、;data);int Depth(BiTree T)int dep=0,depl,depr;if(!T)dep=0;elsedepl=Depth(T->lchild); depr=Depth(T->rchild); dep=1+(depl>depr?depl:depr); return dep;主程序模块： int main()BiTree T = 0;int sum,dep;printf("请输入你需要建立的二叉树 n");printf("例如输入序列ABC#DE#G#F#其中的“ #”表示空)n并且输入过程中不要加回车 n 输入完之后可以按回

5、车退出 n");T=Create(T);printf("先序遍历的结果是：n");Preorder(T);printf("n");printf("中序遍历的结果是：n");Inorder(T);printf("n");printf("后序遍历的结果是：n");Postorder(T);printf("n");printf(" 统计的叶子数： n");sum=Sumleaf(T);printf("%d",sum);printf(

6、"n 统计树的深度： n");dep=Depth(T);printf("n%dn",dep);、【实现描述( Implement )】(30%) (本部分应包括：抽象数据类型具体实现的函数原型说明、 关键操作实现的伪码算 法、 函数设计、函数间的调用关系，关键的程序流程图等，给出关键算法的时间复 杂度分析。)各函数原型说明： BiTree Create(BiTree T)/ 构造二叉树 Tvoid Preorder(BiTree T)/ void Inorder(BiTree T)/ void Postorder(BiTree T)/ int Sumle

7、af(BiTree T)/ int Depth(BiTree T)/ 函数间的调用关系： int main()对二叉树 T 进行先序遍历对二叉树 T 进行中序遍历对二叉树 T 进行后序遍历 求二叉树 T 的叶子节点数目 求二叉树 T 的深度调用 Create 函数，构造二叉树 T调用 Preorder 函数，对二叉树进行先序遍历 调用 Inorder 函数，对二叉树进行中序遍历 调用 Postorder 函数，对二叉树进行后序遍历 调用 Sumleaf 函数，统计二叉树的叶子节点数 调用 Depth 函数，统计二叉树的深度 时间复杂度分析：在对二叉树进行遍历的过程中，用到了递归的思想，对于二叉

8、树中 的每一个结点，从头到尾只访问过一次，所以，对于含有N个结点的二叉树，其遍历的时间复杂度为 o(n) 。四、【测试结果( Testing)】(10%)(本部分应包括： 对实验的测试结果， 应具体列出每次测试所输入的数据以及输出的数据，并对测试结果进行分析总结）请怖入你需更逹立的二爰树2例如输入序列ABCilltDE«Git#Fltlt#其中的S "表不空） 弃且鐘入址程卬不要加回车 输入尧之后可啪回车退由abcttttdnttBfirsVIttt 先序遍历的结果是 ahcdeFg 甲序遍历的结杲是= cbdaFe 后序遠历的结杲是.cdbgFea 统计的叶子数= 知f树

9、的跟4请按任意键继续测试中输入abc#d#ef#g#，构造了二叉树：abec d fg测试结果表明程序对二叉树进行的先序，中序，后序遍历都是正确的， 都输出了正确的结果，统计的叶子数与树深度均正确，所以该程序达到 了实验的要求。四、【实验总结】（10%）（本部分应包括：自己在实验中完成的任务，注意组内的任意一位同学都必须独立完 成至少一项接口的实现；对所完成实验的经验总结、心得）通过这次实验，让我对树有了更深入的认识，让我熟悉了树以及二叉树的结构，掌握 了树以及二叉树的存储以及各种操作。在这次实验中，多次应用到了递归，这样让我 进一步掌握了递归的算法思想。总的来说，这次实验让我对树有了更多的认

10、识。五、【项目运作描述（Operate ）】（10%）（本部分应包括：项目的成本效益分析，应用效果等的分析。）六、【代码】 (10%)(本部分应包括： 完整的代码及充分的注释。 注意纸质的实验报告无需包括此部分 格式统一为，字体 : Georgia , 行距: 固定行距 12，字号 : 小五 )#include <stdio.h>#include <string.h>#include<malloc.h>#define NULL 0typedef struct BiTNodechar data;struct BiTNode *lchild,*rchild;Bi

11、TNode,*BiTree;BiTree Create(BiTree T)char ch;ch=getchar();if(ch='#')T=NULL;elseif(!(T=(BiTNode *)malloc(sizeof(BiTNode)printf("Error!");T->data=ch;T->lchild=Create(T->lchild);T->rchild=Create(T->rchild);return T;void Preorder(BiTree T)if(T)printf("%c",T->

12、;data);Preorder(T->lchild);Preorder(T->rchild);int Sumleaf(BiTree T)int sum=0,m,n;if(T)if(!T->lchild)&&(!T->rchild)sum+;m=Sumleaf(T->lchild);sum+=m;n=Sumleaf(T->rchild);sum+=n;return sum;void Inorder(BiTree T)if(T)Inorder(T->lchild);printf("%c",T->data);Inor

13、der(T->rchild);void Postorder(BiTree T)if(T)Postorder(T->lchild);Postorder(T->rchild);printf("%c",T->data);int Depth(BiTree T)int dep=0,depl,depr;if(!T)dep=0;elsedepl=Depth(T->lchild);depr=Depth(T->rchild);dep=1+(depl>depr?depl:depr); return dep;int main()BiTree T = 0;int sum,dep;printf(" 请输入你需要建立的二叉树 n");printf(" 例如输入序列 ABC#DE#G#F#(其中的 “ #”表示空) n 并且输入过程中不要加回车 n 输入完之后可以按回车退出 n");T=Create(T);printf(" 先序遍历的结果是： n");Preorder(T);printf("n");printf(" 中序遍历的结果是： n");Inorder(T);printf("n&quo