数据结构实验报告树.docx

1、数据结构实验报告树数据结构实验报告实验名称:实验三树学生姓名：*班 级：2010211119班内序号：07学 号:*日 期：2011年11月27号1 实验目的通过选择下面五个题目之一进行实现，掌握如下内容：进一步掌握指针、模板类、异常处理的使用掌握栈的操作的实现方法掌握队列的操作的实现方法学习使用栈解决实际问题的能力学习使用队列解决实际问题的能力2.实验内容根据二叉树的抽象数据类型的定义，使用二叉链表实现一个二叉树。 二叉树的基本功能：1、二叉树的建立2、前序遍历二叉树3、中序遍历二叉树4、后序遍历二叉树5、按层序遍历二叉树6、求二叉树的深度7、求指定结点到根的路径8、二叉树的销毁9、其他：自

2、定义操作编写测试main()函数测试线性表的正确性3.存储结构：采用的是栈的存储结构4.程序的分析和代码重现源程序#includeusing namespace std;template struct Binode T data; Binode *lch; Binode *rch;templateclass Bitree private: void create(Binode*&R,T data,int i); void Destroy(Binode *R); public: Binode*root; Bitree(T data); Bitree(); void preorder(Binode

3、*R); void Inorder(Binode*R); void Postorder(Binode*R); void Levelorder(Binode*R); /*void find(T data);*/ int Depth(Binode *R,int d); void path(Binode* root,char); Bitree();templatevoid Bitree:create(Binode*&R,T data,int i) if(datai-1!=0) R=new Binode; R-data=datai-1; R-lch=R-rch=NULL; create(R-lch,d

4、ata,2*i); create(R-rch,data,2*i+1); /*templatevoid Bitree:find(T data)*/template Bitree:Bitree(T data) create(root,data,1);template void Bitree:preorder(Binode*R) if(R!=NULL) coutdata; preorder(R-lch); preorder(R-rch); template void Bitree:Inorder(Binode*R) if(R!=NULL) Inorder(R-lch); coutdata; Inor

5、der(R-rch); template void Bitree:Postorder(Binode*R) if(R!=NULL) Postorder(R-lch); Postorder(R-rch); coutdata; templatevoid Bitree:Levelorder(Binode*R) Binode* queue10000; int f=0,r=0; if(R!=NULL) queue+r=R; while(f!=r) Binode*p=queue+f; coutdata; if(p-lch!=NULL) queue+r=p-lch; if(p-rch!=NULL) queue

6、+r=p-rch; /销毁二叉树template void Bitree:Destroy(Binode *R) if (R!=NULL) Destroy(R-lch); Destroy(R-rch); delete R; template Bitree:Bitree() Destroy(root);template int Bitree:Depth(Binode *R,int d) if (R=NULL) return d; if (R-lch=NULL) & (R-rch=NULL) return d+1; else int m = Depth(R-lch,d+1); int n = Dep

7、th(R-rch,d+1); return nm? n:m; templatevoid Bitree:path(Binode* root,char m)/求路径 Binode* stack10000; Binode*s; int tag10000; int top=0; s=root; do while(s!=NULL) top+; stacktop=s; tagtop=0; s=s-lch; if(top 0) if(tagtop=1) if(stacktop-data=m) cout 路径: ; for(int i=1;i =top;i+) coutdata; break; top-; e

8、lse s=stacktop; if(top 0) s=s-rch; tagtop=1; while(s!=NULL|top!=0); void main() char buf400=0; for(int i = 0;i5;i+) bufi = i+65; Bitree ChBiTree(buf); cout前序遍历是endl; ChBiTree.preorder(ChBiTree.root); coutendl; cout中序遍历是endl; ChBiTree.Inorder(ChBiTree.root); coutendl; cout后序遍历是endl; ChBiTree.Postorde

9、r(ChBiTree.root); coutendl; cout层序遍历是endl; ChBiTree.Levelorder(ChBiTree.root); coutendl; cout此二叉树的深度是ChBiTree.Depth(ChBiTree.root,0)endl; ChBiTree.path(ChBiTree.root,buf4); 整个程序采用的是递归的方法，其中层序遍历的函数采用的是列的存储结构。 算法设计：首先建立一个二叉树，每一个节点都必须包含他本身的数值，他的左孩子和有孩子，所以用一个结构体来存储每个节点的属性，之后用一个类类实现对于二叉树的各种操作。类的创建：templa

10、teclass Bitree private: void create(Binode*&R,T data,int i);/创建二叉树 void Destroy(Binode *R);/销毁二叉树 public: Binode*root;/根节点 Bitree(T data);/构造函数 Bitree(); void preorder(Binode*R);/前序遍历 void Inorder(Binode*R);/中序遍历 void Postorder(Binode*R);/后续遍历 void Levelorder(Binode*R);/层序遍历 int Depth(Binode *R,int

11、d);/求树的深度 void path(Binode* root,char);/求指定路径 Bitree();/析构函数;前序遍历：template void Bitree:preorder(Binode*R) if(R!=NULL) coutdata; preorder(R-lch); preorder(R-rch); 后续遍历：template void Bitree:Postorder(Binode*R) if(R!=NULL) Postorder(R-lch); Postorder(R-rch); coutdata; 中序遍历：template void Bitree:Inorder(

12、Binode*R) if(R!=NULL) Inorder(R-lch); coutdata; Inorder(R-rch); 二叉树的创建：templatevoid Bitree:create(Binode*&R,T data,int i) if(datai-1!=0) R=new Binode; R-data=datai-1; R-lch=R-rch=NULL; create(R-lch,data,2*i); create(R-rch,data,2*i+1); 求二叉树的深度：template int Bitree:Depth(Binode *R,int d) if (R=NULL) re

13、turn d; if (R-lch=NULL) & (R-rch=NULL) return d+1; else int m = Depth(R-lch,d+1); int n = Depth(R-rch,d+1); return nm? n:m; 二叉树的销毁：template void Bitree:Destroy(Binode *R) if (R!=NULL) Destroy(R-lch); Destroy(R-rch); delete R; template Bitree:Bitree() Destroy(root);求根节点到指定节点的路径：templatevoid Bitree:pa

14、th(Binode* root,char m)/求路径 Binode* stack10000; Binode*s; int tag10000; int top=0; s=root; do while(s!=NULL) top+; stacktop=s; tagtop=0; s=s-lch; if(top 0) if(tagtop=1) if(stacktop-data=m) cout 路径: ; for(int i=1;i =top;i+) coutdata; break; top-; else s=stacktop; if(top 0) s=s-rch; tagtop=1; while(s!=NULL|top!=0); 运行结果测试：1.函数流程：5.感想：这次程序的难点是求指定节点的路径，我采用的是遍历二叉树的方法，把整个二叉树都遍历一遍，并采用的是栈的存储方式，直到找到要求的那个节点，就把整个路径打印出来，最主要的实现方法是那两个循环结构，在代码重现里已经写清楚了，还有这次充分体现了递归函数的巨大作用。