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

1、数据结构实 验 报 告1.实验目的和内容:掌握二叉树基本操作的实现方法2.程序分析2.1存储结构链式存储2.程序流程开始T2.3关键算法分析算法一：Create(BiNode<T>* &R,T data,int i,int n)11【3】【41算法功能：创建二叉树算法基本思想：利用顺序存储结构为输入，采用先建立根结点，再建立 左右孩子的方法来递归建立二叉链表的二叉树算法空间时间复杂度分析：0( n)代码逻辑：如果位置小于数组的长度则创建根结点将数组的值赋给刚才创建的结点的数据域创建左子树，如果当前结点位置为i,则左孩子位置为2i创建右子树，如果当前结点位置为i,则右孩子位置

2、为2i+1否则R为空算法二：CopyTree(BiNodevT>*sR,BiNodevT>* &dR)【1】31算法功能：复制构造函数算法基本思想：按照先创建根结点，再递归创建左右子树的方法来实 现。算法空间时间复杂度分析：O (n)41代码逻辑：如果源二叉树根结点不为空则创建根结点调用函数自身，创建左子树调用函数自身，创建右子树将该函数放在复制构造函数中调用，就可以实现复制构造函数算法三：PreOrder(BiNodevT>*R)【3】【4】算法功能：二叉树的前序遍历算法基本思想：这个代码用的是优化算法，提前让当前结点出栈。算法空间时间复杂度分析：O (n)代码逻辑

3、(伪代码)如果当前结点为非空，则访问当前结点当前结点入栈将当前结点的左孩子作为当前结点如果为空则栈顶结点出栈则将该结点的右孩子作为当前结点反复执行这两个过程，直到结点为空并且栈空算法四：In Order(BiNode<T>*R)【2】【3】算法功能：二叉树的中序遍历算法基本思想：递归算法空间时间复杂度分析：未知【4】代码逻辑:【3】【4】如果R为非空：则调用函数自身遍历左孩子访问该结点算法五：LevelOrder(BiNode<T>*R) 【1】再调用自身访问该结点的右孩子算法功能：二叉树的层序遍历【2】算法基本思想：算法空间时间复杂度分析：O (n)代码逻辑(伪代码)

4、： 若根结点非空，入队如果队列不空对头元素出队访问该元素 若该结点的左孩子为非空，则左孩子入队; 若该结点的右孩子为非空，则右孩子入队;算法六：Count(BiNodevT>*R)算法功能：计算结点的个数【2】【3】算法基本思想：递归算法空间时间复杂度分析：未知【4】代码逻辑:1131如果R不为空的话调用函数自身计算左孩子的结点数 调用函数自身计算右孩子的结点数temp latevciass T>int BiTree<T>:Cou nt(BiNodevT>*R) if(R=NULL)return 0;elseint m=Cou nt(R->lchild);

5、int n=Cou nt(R->rchild); return m+n+1;算法七：算法功能：释放动态内存Release(BiNode<T>*R)【2】算法基本思想：左右子树全部释放完毕后再释放该结点 算法空间时间复杂度分析：未知【4】代码逻辑:调用函数自身，释放左子树调用函数自身，释放右子树 释放根结点释放二叉树temp latevciass T>void BiTree<T>:Release(BiNode<T>*R) if(R!=NULL)Release(R->lchild); Release(R->rchild); delete

6、R;temp latevciass T>BiTreevT>:BiTree() Release(root);int mai n()int a10=1,2,3,4,5,6,7,8,9,10;BiTreevi nt> BTree(a,10);BiTreevi nt>Tree(BTree);BTree .P reOrder(BTree.root); coutvve ndl;Tree. PreOrder(Tree.root); coutvve ndl;BTree.I nOrder(BTree.root); coutvve ndl;Tree.lnO rder(Tree.root);

7、 coutvve ndl;BTree. PostOrder(BTree.root); coutvve ndl;Tree. Po stOrder(Tree.root); coutvve ndl;BTree丄evelOrder(BTree.root); coutvve ndl;Tree丄evelOrder(Tree.root); coutvve ndl;int m=BTree.Co un t(BTree.root); coutvvmvve ndl;return 0;3. 测试数据：int a10=1,2,3,4,5;1 2 4 5 31 2 4 5 34 2 5 1 34 5 2 3 11 2 3

8、 4 554. 总结：4.1:这次实验大多用了递归的算法，比较好理解。4.2 :新得体会：在创建二叉树的过程中，在没有思路的时候可以巧妙的利用递归算法。但是我的代码仍然应该改进，应该进一步简化，减少算法的时间复杂度和空间 复杂度。#in cludeviostream> using n ames pace std; tempi atevclass T>class BiNodep ublic:T data;BiNodevT>*lchild;BiNodevT>*rchild;tempi atevciass T>class BiTreep ublic:BiNodevT&g

9、t;*root;BiTree(T data,i nt n);BiTreejBiTreevT >& r);void P reOrdeMBiNodevTVR); void In OrdeMBiNodevThR); void P ostOrdeMBiNodevThR); void LevelOrdeMBiNodevThR); int Cou nMBiNodevTVR);-BiTreeO;p rivate:void CreateQNodevT* & R,T data,i nt i,i nt n); void Cop yTreeQNodevThsR'BiNodevT* &a

10、mp;dR); void ReleaseQNodevThR);tempi atevciass T>void BiTreevT>: Create(BiNodevT>* &R,T data,i nt i,i nt n) if(iv=n&&datai-1)R=new BiNodevT>R->data=datai-1;Create(R->lchild,data,2*i, n);Create(R->rchild,data,2*i+1, n);else R=NULL;tempi atevclass T>BiTreevT>:BiT

11、ree(T data,i nt n) Create(root,data,1, n); tempi atevciass T>void BiTreevT>:Co pyTree(BiNodevT>*sR,BiNodevT>* & dR) if(sR=NULL)dR=NULL;elsedR=new BiNodevT>dR->data=sR->data;Co pyTree(sR->lchild,dR->lchild);Co pyTree(sR->rchild,dR->rchild); temp latevciass T>Bi

12、TreevT>:BiTree(BiTreevT >& p)Cop yTree( p.root,this->root);/this? tempi atevclass T>void BiTreevT>: PreOrder(BiNodevT>*R) BiNodevT>*S100;int top=-1;while(to p!=-1)|(R!=NULL)if(R!=NULL)coutvvR->datavv"" S+t op =R;R=R->lchild;elseR=Stop-; R=R->rchild;tempi a

13、tevciass T>void BiTreevT>:I nOrder(BiNodevT>*R) if(R!=NULL)In Order(R->lchild); coutvvR->datavv"" In Order(R->rchild); tempi atevciass T>void BiTreevT>: P ostOrder(BiNodevT>*R)if(R!=NULL)P ostOrder(R->lchild);P ostOrder(R->rchild); cout<<R->data<

14、;<"" tempi ate<class T>void BiTree<T>:LevelOrder(BiNode<T>*R) BiNodevT>*queue100;int f=0,r=0;if(R!=NULL)queue+r=R;while(f!=r)BiNode<T>* p=queue+f; cout< vp->datavv""if(p->lchild!=NULL) queue+r=p->lchild;if(p->rchild!=NULL) queue+r=p-&g

15、t; rchild;temp latevclass T>int BiTree<T>:Cou nt(BiNodevT>*R) if(R=NULL)return 0;elseint m=Cou nt(R->lchild); int n=Cou nt(R->rchild); return m+n+1;temp latevclass T>void BiTreevT>:Release(BiNodevT>*R) if(R!=NULL)Release(R->lchild);Release(R->rchild); delete R;temp latevclass T> BiTreevT>:BiTree() Release(root);int mai n()int a5=1,2,3,4,5;BiTreevi nt> BTree(a,5);BiTreevi nt>Tree(BTree);BTree .P reOrder(B