数据结构二叉树实验.doc

《数据结构二叉树实验.doc》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、二、【实验设计(Design)】(20%)（本部分应包括：抽象数据类型的功能规格说明、主程序模块、各子程序模块的伪码说明，主程序模块与各子程序模块间的调用关系）二叉树的存储结构：typedefstructBiTNode{chardata;structBiTNode*lchild,*rchild;}BiTNode,*BiTree;子程序模块：BiTreeCreate(BiTreeT){charch;ch=getchar();if(ch=='#')T=NULL;else{if(!(T=(BiTNode*)malloc(sizeof(B

2、iTNode))))printf("Error!");T->data=ch;T->lchild=Create(T->lchild);T->rchild=Create(T->rchild);}returnT;}voidPreorder(BiTreeT){if(T){printf("%c",T->data);Preorder(T->lchild);Preorder(T->rchild);}}intSumleaf(BiTreeT){intsum=0,m,n;if(T){if((!T->lchild)&&(!T->rchild))sum+

3、+;m=Sumleaf(T->lchild);sum+=m;n=Sumleaf(T->rchild);sum+=n;}returnsum;}voidInorder(BiTreeT){if(T){Inorder(T->lchild);printf("%c",T->data);Inorder(T->rchild);}}voidPostorder(BiTreeT){if(T){Postorder(T->lchild);Postorder(T->rchild);printf("%c",T->data);}}intDepth(BiTreeT

4、){intdep=0,depl,depr;if(!T)dep=0;else{depl=Depth(T->lchild);depr=Depth(T->rchild);dep=1+(depl>depr?depl:depr);}returndep;}主程序模块：intmain(){BiTreeT=0;intsum,dep;printf("请输入你需要建立的二叉树");printf("例如输入序列ABC##DE#G##F###（其中的“#”表示空）并且输入过程中不要加回车输入完之后可以按回车退出");T=Create(T)

5、;printf("先序遍历的结果是：");Preorder(T);printf("");printf("中序遍历的结果是：");Inorder(T);printf("");printf("后序遍历的结果是：");Postorder(T);printf("");printf("统计的叶子数：");sum=Sumleaf(T);printf("%d",sum);printf("统计树的深度：");dep=Depth(T);printf("%d",dep);}三、【实现描述（Implement

6、）】(30%)（本部分应包括：抽象数据类型具体实现的函数原型说明、关键操作实现的伪码算法、函数设计、函数间的调用关系，关键的程序流程图等，给出关键算法的时间复杂度分析。）各函数原型说明：BiTreeCreate(BiTreeT)//构造二叉树TvoidPreorder(BiTreeT)//对二叉树T进行先序遍历voidInorder(BiTreeT)//对二叉树T进行中序遍历voidPostorder(BiTreeT)//对二叉树T进行后序遍历intSumleaf(BiTreeT)//求二叉树T的叶子节点数目intDepth(Bi

7、TreeT)//求二叉树T的深度函数间的调用关系：intmain(){调用Create函数，构造二叉树T调用Preorder函数，对二叉树进行先序遍历调用Inorder函数，对二叉树进行中序遍历调用Postorder函数，对二叉树进行后序遍历调用Sumleaf函数，统计二叉树的叶子节点数调用Depth函数，统计二叉树的深度}时间复杂度分析：在对二叉树进行遍历的过程中，用到了递归的思想，对于二叉树中的每一个结点，从头到尾只访问过一次，所以，对于含有N个结点的二叉树，其遍历的时间复杂度为o(n)。四、【测试结果（Testing）】(1

8、0%)（本部分应包括：对实验的测试结果，应具体列出每次测试所输入的数据以及输出的数据，并对测试结果进行分析总结）测试中输入abc##d##ef#g###，构造了二叉树：abecdfg测试结果表明程序对二叉树进行的先序，中序，后序遍历都是正确的，都输