数据结构实验报告三二叉树

1、数 据 结 构实验报告实验名称： 实验四 题目1 用二叉链表实现一个二叉树学生姓名： 班 级： 2013211128班内序号： 学 号： 2013210771日 期： 2014/12/051. 实验目的掌握二叉树基本操作的实现方法根据二叉树的抽象数据类型的定义，使用二叉链表实现一个二叉树。二叉树的基本功能：1、二叉树的建立2、前序遍历二叉树3、中序遍历二叉树4、后序遍历二叉树5、按层序遍历二叉树6、求二叉树的深度7、求指定结点到根的路径8、二叉树的销毁9、其他：自定义操作编写测试 main()函数测试二叉树的正确性2. 程序分析2.1 存储结构采用二叉树的存储结构，其中每个二叉树的结点定义了一

2、个结构体，该结构体包含三个元素，分别是一个T类型的数据域data，一个指向T类型的指针左孩子，一个指向T类型的指针右孩子。在对二叉树的关键算法的实现过程中，采用了队列的存储结构。对于二叉树中每个结点的data域的赋值，我们事先把这些data储存在一个数组中，通过对数组元素的调用事先对二叉树中每个结点的data域的赋值。2.2 关键算法分析2.2.1二叉树的建立：A 自然语言描述：1 首先判断调用的数组是否为空，如果为空，直接将一个已经初始化好的根节点置为空。2 如果该数组不为空，则把调用的数组的第一个元素的赋给根节点的data域。3 采用递归的思想，分别将根节点的左右孩子作为根节点，递归调用该

3、函数。完成对左右子树的赋值。时间复杂度：O（1）B 代码详细分析：template<class T>void Bitree<T>:create(Binode<T>*&R,T data,int i)/创建二叉树if(datai-1!=0)R=new Binode<T> /创建根结点R->data=datai-1;R->lch=R->rch=NULL;create(R->lch,data,2*i); /创建左子树create(R->rch,data,2*i+1); /创建右子树template <class

4、 T>Bitree<T>:Bitree(T data)create(root,data,1); /create root2.2.2前序遍历二叉树：A. 自然语言描述：1：判断根节点是否为空2：输出它的data域3：遍历左子树4：遍历右子树时间复杂度：O（1）B.代码详细分析：template <class T>void Bitree<T>:preorder(Binode<T>*R) /前序遍历if(R!=NULL)cout<<R->data; /访问结点preorder(R->lch); /遍历左子树preorder

5、(R->rch); /遍历右子树 2.2.3中序遍历二叉树：A.自然语言描述：1：判断根节点是否为空2：遍历左子树3：访问结点4：遍历右子树时间复杂度：O（1）B. 代码详细分析：template <class T>void Bitree<T>:Inorder(Binode<T>*R) /中序遍历if(R!=NULL)Inorder(R->lch); /遍历左子树cout<<R->data; /访问结点Inorder(R->rch); /遍历右子树2.2.4后序遍历二叉树：A.自然语言描述：1：判断根节点是否为空2：遍历左

6、子树3：遍历右子树4：访问结点时间复杂度：O（1）B.代码详细分析：template <class T>void Bitree<T>:Postorder(Binode<T>*R) /后序遍历if(R!=NULL)Postorder(R->lch); /遍历左子树Postorder(R->rch); /遍历右子树cout<<R->data; /访问结点2.2.5层序遍历二叉树：A.自然语言描述：1：初始化空队列2：根结点入队3：队头元素出队4：出队打印5：左孩子入队6：右孩子入队时间复杂度：O（1）B.代码详细分析：templat

7、e<class T>void Bitree<T>:Levelorder(Binode<T>*R) /层序遍历Binode<T>* queue10000;int f=0,r=0; /初始化空队列if(R!=NULL)queue+r=R; /根结点入队while(f!=r)Binode<T>*p=queue+f; /队头元素出队cout<<p->data; /出队打印if(p->lch!=NULL)queue+r=p->lch; /左孩子入队if(p->rch!=NULL)queue+r=p->r

8、ch; /右孩子入队2.2.6求二叉树的深度：时间复杂度：O（1）代码详细分析：template <class T>int Bitree<T>:Depth(Binode<T> *R,int d) /深度if (R=NULL) return d;if (R->lch=NULL) && (R->rch=NULL)return d+1;elseint m = Depth(R->lch,d+1);int n = Depth(R->rch,d+1);return n>m? n:m;2.2.7求指定结点到根的路径时间复杂度：

9、O（n）代码详细分析：template<class T>void Bitree<T>:path(Binode<T>* root,char m) /求路径Binode<T>* stack10000;Binode<T>*s;int tag10000;int top=0;s=root;dowhile(s!=NULL)top+;stacktop=s;tagtop=0;s=s->lch;if(top> 0)if(tagtop=1)if(stacktop->data=m)cout<< "路径: "

10、for(int i=1;i <=top;i+)cout<<stacki->data;break;top-;Elses=stacktop;if(top> 0)s=s->rch;tagtop=1;while(s!=NULL|top!=0);2.2.8销毁二叉树时间复杂度：O（1）详细代码分析：template <class T>void Bitree<T>:Destroy(Binode<T> *R) /销毁二叉树if (R!=NULL)Destroy(R->lch);Destroy(R->rch);delete R

11、;template <class T>Bitree<T>:Bitree()/销毁根结点Destroy(root); 3.程序运行结果实现了二叉树的功能4.总结对二叉树的操作上，前序遍历，中序遍历，后续遍历，层序遍历，求二叉树深度等函数采用了递归算法。为了提高运算性能，可以将它们改为非递归算法来实现，对于比较复杂的算法，递归和非递归的运算时间复杂度差别较大。在实验中我掌握二叉树基本操作的实现方法，并且根据二叉树的抽象数据类型的定义，使用二叉链表实现一个二叉树。源程序：#include<iostream> using namespace std; templat

12、e<class T> struct Binode T data; Binode<T> *lch; Binode<T> *rch; ; template<class T>class Bitree private: void create(Binode<T>*&R,T data,int i); /创建二叉树 void Destroy(Binode<T> *R); public: Binode<T>*root; /根结点 Bitree(T data); /构造函数 Bitree(); void preorde

13、r(Binode<T>*R); /前序遍历 void Inorder(Binode<T>*R); /中序遍历 void Postorder(Binode<T>*R); /后序遍历 void Levelorder(Binode<T>*R); /层序遍历 /*void find(T data);*/ int Depth(Binode<T> *R,int d); /深度 void path(Binode<T>* root,char); Bitree(); /析构函数; template<class T>void Bi

14、tree<T>:create(Binode<T>*&R,T data,int i) /创建二叉树 if(datai-1!=0) R=new Binode<T> /创建根结点 R->data=datai-1; R->lch=R->rch=NULL; create(R->lch,data,2*i); /创建左子树 create(R->rch,data,2*i+1); /创建右子树 template <class T> Bitree<T>:Bitree(T data) create(root,data,

15、1); /create root template <class T> void Bitree<T>:preorder(Binode<T>*R) /前序遍历 if(R!=NULL) cout<<R->data; /访问结点 preorder(R->lch); /遍历左子树 preorder(R->rch); /遍历右子树 template <class T> void Bitree<T>:Inorder(Binode<T>*R) /中序遍历 if(R!=NULL) Inorder(R->

16、lch); /遍历左子树 cout<<R->data; /访问结点 Inorder(R->rch); /遍历右子树 template <class T> void Bitree<T>:Postorder(Binode<T>*R) /后序遍历 if(R!=NULL) Postorder(R->lch); /遍历左子树 Postorder(R->rch); /遍历右子树 cout<<R->data; /访问结点 template<class T> void Bitree<T>:Leve

17、lorder(Binode<T>*R) /层序遍历 Binode<T>* queue10000; int f=0,r=0; /初始化空队列 if(R!=NULL) queue+r=R; /根结点入队 while(f!=r) Binode<T>*p=queue+f; /队头元素出队 cout<<p->data; /出队打印 if(p->lch!=NULL) queue+r=p->lch; /左孩子入队 if(p->rch!=NULL) queue+r=p->rch; /右孩子入队 template <class

18、T> void Bitree<T>:Destroy(Binode<T> *R) /销毁二叉树 if (R!=NULL) Destroy(R->lch); Destroy(R->rch); delete R; template <class T> Bitree<T>:Bitree() /销毁根结点 Destroy(root); template <class T> int Bitree<T>:Depth(Binode<T> *R,int d) /深度 if (R=NULL) return d;

19、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 n>m? n:m; template<class T> void Bitree<T>:path(Binode<T>* root,char m) /求路径 Binode<T>* stack10000; Binode<T>*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+) cout<<stacki->data; break; top-; els s=stacktop; if(top> 0) s=s