计算机软件技术基础报告

《计算机软件技术基础报告》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、实验四___线性表_____一、实验目的：a)掌握二叉树的逻辑结构；b)掌握二叉树的二叉链表的存储结构；c)掌握二叉树的二叉链表的存储的二叉树的遍历操作的实现二、实验内容及测试结果：a)建立一棵含有n个结点的二叉树，采用二叉链表存储；b)前序（或中序、后序）遍历该二叉树。三、算法或核心技术思考体会：前：根左右中：左根右后：左右根四、附件（源代码）（可选）//定义类中的成员函数，文件名为bitree.cpp#include#include#include"bitree.h"usingnamespacestd;/**前置条件：二叉树不存在*输入：无*功能：构造

2、一棵二叉树*输出：无*后置条件：产生一棵二叉树*/templateBiTree::BiTree(){this->root=Creat();}/**前置条件：二叉树已存在*输入：无*功能：释放二叉链表中各结点的存储空间*输出：无*后置条件：二叉树不存在*/templateBiTree::~BiTree(void){Release(root);}/**前置条件：二叉树已存在*输入：无*功能：获取指向二叉树根结点的指针*输出：指向二叉树根结点的指针*后置条件：二叉树不变*/templateBiNode*BiTree::Getr

3、oot(){returnroot;}/**前置条件：二叉树已存在*输入：无*功能：前序遍历二叉树*输出：二叉树中结点的一个线性排列*后置条件：二叉树不变*/templatevoidBiTree::PreOrder(BiNode*root){if(root==NULL)return;else{cout<data<<"";PreOrder(root->lchild);PreOrder(root->rchild);}}/**前置条件：二叉树已存在*输入：无*功能：中序遍历二叉树*输出：二叉树中结点的一个线性排列*后置条件：二叉树不变*/template

4、lassT>voidBiTree::InOrder(BiNode*root){if(root==NULL)return;//递归调用的结束条件else{InOrder(root->lchild);//中序递归遍历root的左子树cout<data<<"";//访问根结点的数据域InOrder(root->rchild);//中序递归遍历root的右子树}}/**前置条件：二叉树已存在*输入：无*功能：后序遍历二叉树*输出：二叉树中结点的一个线性排列*后置条件：二叉树不变*/templatevoidBiTree::PostOrder(BiNode

5、*root){if(root==NULL)return;//递归调用的结束条件else{PostOrder(root->lchild);//后序递归遍历root的左子树PostOrder(root->rchild);//后序递归遍历root的右子树cout<data<<"";//访问根结点的数据域}}/**前置条件：二叉树已存在*输入：无*功能：层序遍历二叉树*输出：二叉树中结点的一个线性排列*后置条件：二叉树不变*/templatevoidBiTree::LeverOrder(BiNode*root){constintMaxSize=100;

6、intfront=0;intrear=0;//采用顺序队列，并假定不会发生上溢BiNode*Q[MaxSize];BiNode*q;if(root==NULL)return;else{Q[rear++]=root;while(front!=rear){q=Q[front++];cout<data<<"";if(q->lchild!=NULL)Q[rear++]=q->lchild;if(q->rchild!=NULL)Q[rear++]=q->rchild;}}}/**前置条件：空二叉树*输入：数据ch;*功能：初始化一棵二叉树,构造函数调用*输出：无*后置条件：产生一棵

7、二叉树*/templateBiNode*BiTree::Creat(){BiNode*root;Tch;cout<<"请输入创建一棵二叉树的结点数据"<>ch;if(ch=="#")root=NULL;else{root=newBiNode;//生成一个结点root->data=ch;root->lchild=Creat();//递归建立左子树roo