数据结构二叉树实验.doc

二、【实验设计(Design)】(20%)（本部分应包括：抽象数据类型的功能规格说明、主程序模块、各子程序模块的伪码说明，主程序模块与各子程序模块间的调用关系）二叉树的存储结构：typedef struct BiTNode char data; struct BiTNode *lchild,*rchild; BiTNode,*BiTree; 子程序模块：BiTree Create(BiTree T) char ch; ch=getchar(); if(ch=#) T=NULL; else if(!(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-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); Inorder(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; else depl=Depth(T-lchild); depr=Depth(T-rchild); dep=1+(depldepr?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); printf(后序遍历的结果是：n); Postorder(T); printf(n); printf(统计的叶子数：n); sum=Sumleaf(T); printf(%d,sum); printf(n统计树的深度：n);dep=Depth(T); printf(n%dn,dep); 三、【实现描述（Implement）】(30%)（本部分应包括：抽象数据类型具体实现的函数原型说明、 关键操作实现的伪码算法、 函数设计、函数间的调用关系，关键的程序流程图等，给出关键算法的时间复杂度分析。）各函数原型说明：BiTree Create(BiTree T)/构造二叉树T void Preorder(BiTree T)/对二叉树T进行先序遍历 void Inorder(BiTree T)/对二叉树T进行中序遍历 void Postorder(BiTree T)/对二叉树T进行后序遍历 int Sumleaf(BiTree T)/求二叉树T的叶子节点数目 int Depth(BiTree T)/求二叉树T的深度函数间的调用关系：int main() 调用Create函数，构造二叉树T调用Preorder函数，对二叉树进行先序遍历调用Inorder函数，对二叉树进行中序遍历调用Postorder函数，对二叉树进行后序遍历调用Sumleaf函数，统计二叉树的叶子节点数调用Depth函数，统计二叉树的深度时间复杂度分析：在对二叉树进行遍历的过程中，用到了递归的思想，对于二叉树中的每一个结点，从头到尾只访问过一次，所以，对于含有N个结点的二叉树，其遍历的时间复杂度为o(n)。四、【测试结果（Testing）】(10%)（本部分应包括：对实验的测试结果，应具体列出每次测试所输入的数据以及输出的数据，并对测试结果进行分析总结）测试中输入abc#d#ef#g#，构造了二叉树： a b e c d f g测试结果表明程序对二叉树进行的先序，中序，后序遍历都是正确的，都输出了正确的结果，统计的叶子数与树深度均正确，所以该程序达到了实验的要求。四、【实验总结】(10%)（本部分应包括：自己在实验中完成的任务，注意组内的任意一位同学都必须独立完成至少一项接口的实现；对所完成实验的经验总结、心得）通过这次实验，让我对树有了更深入的认识，让我熟悉了树以及二叉树的结构，掌握了树以及二叉树的存储以及各种操作。在这次实验中，多次应用到了递归，这样让我进一步掌握了递归的算法思想。总的来说，这次实验让我对树有了更多的认识。五、【项目运作描述（Operate）】(10%)（本部分应包括：项目的成本效益分析，应用效果等的分析。）六、【代码】(10%)（本部分应包括：完整的代码及充分的注释。 注意纸质的实验报告无需包括此部分。格式统一为，字体: Georgia , 行距: 固定行距12，字号: 小五）#include #include #include#define NULL 0 typedef struct BiTNode char data; struct BiTNode *lchild,*rchild; BiTNode,*BiTree; BiTree Create(BiTree T) char ch; ch=getchar(); if(ch=#) T=NULL; else if(!(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-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); Inorder(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; else depl=Depth(T-lchild); depr=Depth(T-rchild); dep=1+(depldepr?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(中