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

数据结构 实 验 报 告 1.实验目的和内容：掌握二叉树基本操作的实现方法2.程序分析2.1存储结构 链式存储2程序流程 2.3关键算法分析算法一：Create(BiNode* &R,T data,int i,int n)【1】算法功能：创建二叉树【2】算法基本思想：利用顺序存储结构为输入，采用先建立根结点，再建立左右孩子的方法来递归建立二叉链表的二叉树【3】算法空间时间复杂度分析：O(n)【4】代码逻辑： 如果位置小于数组的长度则 创建根结点 将数组的值赋给刚才创建的结点的数据域 创建左子树，如果当前结点位置为i,则左孩子位置为2i 创建右子树，如果当前结点位置为i,则右孩子位置为2i+1 否则R为空 算法二：CopyTree(BiNode*sR,BiNode* &dR)）【1】算法功能：复制构造函数【2】算法基本思想：按照先创建根结点，再递归创建左右子树的方法来实现。【3】算法空间时间复杂度分析：O（n)【4】代码逻辑: 如果源二叉树根结点不为空 则 创建根结点 调用函数自身，创建左子树 调用函数自身，创建右子树 将该函数放在复制构造函数中调用，就可以实现复制构造函数算法三：PreOrder(BiNode*R)【1】算法功能：二叉树的前序遍历【2】算法基本思想：这个代码用的是优化算法，提前让当前结点出栈。【3】算法空间时间复杂度分析：O（n）【4】代码逻辑（伪代码） 如果当前结点为非空，则 访问当前结点 当前结点入栈 将当前结点的左孩子作为当前结点 如果为空 则栈顶结点出栈 则将该结点的右孩子作为当前结点 反复执行这两个过程，直到结点为空并且栈空算法四：InOrder(BiNode*R)【1】算法功能：二叉树的中序遍历【2】算法基本思想：递归【3】算法空间时间复杂度分析：未知【4】代码逻辑： 如果R为非空： 则调用函数自身遍历左孩子 访问该结点 再调用自身访问该结点的右孩子算法五：LevelOrder(BiNode*R)【1】算法功能：二叉树的层序遍历【2】算法基本思想：【3】算法空间时间复杂度分析：O（n）【4】代码逻辑（伪代码）： 若根结点非空，入队 如果队列不空 对头元素出队 访问该元素 若该结点的左孩子为非空，则左孩子入队； 若该结点的右孩子为非空，则右孩子入队； 算法六：Count(BiNode*R)【1】算法功能：计算结点的个数【2】算法基本思想：递归【3】算法空间时间复杂度分析：未知【4】代码逻辑： 如果R不为空的话 调用函数自身计算左孩子的结点数 调用函数自身计算右孩子的结点数 template int BiTree:Count(BiNode*R) if(R=NULL)return 0; else int m=Count(R-lchild); int n=Count(R-rchild); return m+n+1; 算法七：Release(BiNode*R)【1】算法功能：释放动态内存【2】算法基本思想：左右子树全部释放完毕后再释放该结点【3】算法空间时间复杂度分析：未知【4】代码逻辑： 调用函数自身，释放左子树 调用函数自身，释放右子树 释放根结点 释放二叉树 template void BiTree:Release(BiNode*R) if(R!=NULL) Release(R-lchild); Release(R-rchild); delete R; template BiTree:BiTree() Release(root); int main() int a10=1,2,3,4,5,6,7,8,9,10; BiTree BTree(a,10); BiTreeTree(BTree); BTree.PreOrder(BTree.root); coutendl; Tree.PreOrder(Tree.root); coutendl; BTree.InOrder(BTree.root); coutendl; Tree.InOrder(Tree.root); coutendl; BTree.PostOrder(BTree.root); coutendl; Tree.PostOrder(Tree.root); coutendl; BTree.LevelOrder(BTree.root); coutendl; Tree.LevelOrder(Tree.root); coutendl; int m=BTree.Count(BTree.root);coutmendl; 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:新得体会：在创建二叉树的过程中，在没有思路的时候可以巧妙的利用递归算法。但是我的代码仍然应该改进，应该进一步简化，减少算法的时间复杂度和空间复杂度。#includeusing namespace std;templateclass BiNodepublic:T data;BiNode*lchild;BiNode*rchild; ; templateclass BiTree public: BiNode*root;BiTree(T data,int n);BiTree(BiTree& r);void PreOrder(BiNode*R);void InOrder(BiNode*R);void PostOrder(BiNode*R);void LevelOrder(BiNode*R);int Count(BiNode*R);BiTree();private:void Create(BiNode* &R,T data,int i,int n);void CopyTree(BiNode*sR,BiNode* &dR);void Release(BiNode*R); ; template void BiTree: Create(BiNode* &R,T data,int i,int n) if(i=n&datai-1) R=new BiNode; R-data=datai-1; Create(R-lchild,data,2*i,n); Create(R-rchild,data,2*i+1,n); else R=NULL; template BiTree:BiTree(T data,int n) Create(root,data,1,n); template void BiTree:CopyTree(BiNode*sR,BiNode* &dR) if(sR=NULL) dR=NULL; else dR=new BiNode; dR-data=sR-data; CopyTree(sR-lchild,dR-lchild); CopyTree(sR-rchild,dR-rchild); template BiTree:BiTree(BiTree& p) CopyTree(p.root,this-root);/this? template void BiTree:PreOrder(BiNode*R) BiNode*S100; int top=-1; while(top!=-1)|(R!=NULL) if(R!=NULL) coutdatalchild; elseR=Stop-;R=R-rchild; template void BiTree:InOrder(BiNode*R) if(R!=NULL) InOrder(R-lchild); coutdatarchild); template void BiTree: PostOrder(BiNode*R) if(R!=NULL) PostOrder(R-lchild); PostOrder(R-rchild); coutdata ; template void BiTree:LevelOrder(BiNode*R) BiNode*queue100; int f=0,r=0; if(R!=NULL) queue+r=R; while(f!=r) BiNode*p=queue+f; coutdatalchild!=NULL) queue+r=p-lchild; if(p-rchild!=NULL) queue+r=p-rchild; template int BiTree:Count(BiNode*R) if(R=NULL)return 0; else int m=Count(R-lchild); int n=Count(R-rchild); return m+n+1; template void BiTree:Release(BiNode*R) if(R!=NULL) Release(R-lchild); Release(R-rchild); delete R; template BiTree:BiTree() Release(root); int main() int a5=1,2,3,4,5; BiTree BTree(a,5); BiTreeTree(BTree); BTree.PreOrder(BTree.root); coutendl;