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

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

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

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

4、层序遍历【 2】 算法基本思想：【 3】 算法空间时间复杂度分析： O( n)【 4】 代码逻辑(伪代码)：若根结点非空，入队如果队列不空对头元素出队访问该元素若该结点的左孩子为非空，则左孩子入队；若该结点的右孩子为非空，则右孩子入队；算法六： Count(BiNode<T>*R)【 1】 算法功能：计算结点的个数【 2】 算法基本思想：递归【 3】 算法空间时间复杂度分析：未知【 4】 代码逻辑：如果R不为空的话调用函数自身计算左孩子的结点数调用函数自身计算右孩子的结点数template<class T>int BiTree<T>:Count(BiNode

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

6、;T>*R)if(R!=NULL)Release(R->lchild);Release(R->rchild);delete R;template<class T>BiTree<T>:BiTree()Release(root);int main()int a10=1,2,3,4,5,6,7,8,9,10;BiTree<int> BTree(a,10);BiTree<int>Tree(BTree);BTree.PreOrder(BTree.root); cout<<endl;Tree.PreOrder(Tree.root

7、); cout<<endl;BTree.InOrder(BTree.root); cout<<endl;Tree.InOrder(Tree.root); cout<<endl;BTree.PostOrder(BTree.root); cout<<endl;Tree.PostOrder(Tree.root); cout<<endl;BTree.LevelOrder(BTree.root); cout<<endl;Tree.LevelOrder(Tree.root); cout<<endl;int m=BTree.

8、Count(BTree.root); cout<<m<<endl;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 4 554. 总结：4.1: 这次实验大多用了递归的算法，比较好理解。4.2: 新得体会：在创建二叉树的过程中，在没有思路的时候可以巧妙的利用递归算法。但是我的代码仍然应该改进，应该进一步简化，减少算法的时间复杂度和空间复杂度。#include<iostream>using namespace std;template<class T&

9、gt;class BiNodepublic:T data;BiNode<T>*lchild;BiNode<T>*rchild;template<class T>class BiTreepublic:BiNode<T>*root;BiTree(T data,int n);BiTree(BiTree<T>& r);void PreOrder(BiNode<T>*R);void InOrder(BiNode<T>*R);void PostOrder(BiNode<T>*R);void LevelO

10、rder(BiNode<T>*R);int Count(BiNode<T>*R);BiTree();private:void Create(BiNode<T>* &R,T data,int i,int n);void CopyTree(BiNode<T>*sR,BiNode<T>* &dR);void Release(BiNode<T>*R);template<class T>void BiTree<T>: Create(BiNode<T>* &R,T data,

11、int i,int n)if(i<=n&&datai-1)R=new BiNode<T>R->data=datai-1;Create(R->lchild,data,2*i,n);Create(R->rchild,data,2*i+1,n);else R=NULL;template<class T>BiTree<T>:BiTree(T data,int n)Create(root,data,1,n);template<class T>void BiTree<T>:CopyTree(BiNode&l

12、t;T>*sR,BiNode<T>* &dR) if(sR=NULL)dR=NULL;elsedR=new BiNode<T>dR->data=sR->data;CopyTree(sR->lchild,dR->lchild);CopyTree(sR->rchild,dR->rchild);template<class T>BiTree<T>:BiTree(BiTree<T>& p)CopyTree(p.root,this->root);/this?template<

13、class T>void BiTree<T>:PreOrder(BiNode<T>*R)BiNode<T>*S100;int top=-1;while(top!=-1)|(R!=NULL)if(R!=NULL)cout<<R->data<<"" S+top=R;R=R->lchild;) else ( R=Stop-; R=R->rchild;)template<class T>void BiTree<T>:InOrder(BiNode<T>*R)(if(

14、R!=NULL)(InOrder(R->lchild); cout<<R->data<<"" InOrder(R->rchild);)template<class T>void BiTree<T>: PostOrder(BiNode<T>*R) (if(R!=NULL)(PostOrder(R->lchild); PostOrder(R->rchild); cout<<R->data<<"")template<class T>

15、;void BiTree<T>:LevelOrder(BiNode<T>*R)(BiNode<T>*queue100;int f=0,r=0;if(R!=NULL)queue+r=R;while(f!=r)(BiNode<T>*p=queue+f; cout<<p->data<<" "if(p->lchild!=NULL) queue+r=p->lchild;if(p->rchild!=NULL) queue+r=p->rchild;template<class T&

16、gt;int BiTree<T>:Count(BiNode<T>*R)if(R=NULL)return 0;elseint m=Count(R->lchild);int n=Count(R->rchild);return m+n+1;template<class T>void BiTree<T>:Release(BiNode<T>*R)if(R!=NULL)Release(R->lchild);Release(R->rchild);delete R;template<class T>BiTree<T>:BiTree()Release(root);int main()int a5=1,2,3,4,5;BiTree<int> BTree(a,5);BiTree<int>Tree(BTree);BTree.PreOrder(BTree.root