哈尔滨理工大学

软件与微电子学院

实 验 报 告

（2017-2018第一学期）

课程名称：

班 级：

学 号：

姓 名：

实验名称 姓 名 曹妍 数据结构实验四 学 号 1614010102 专 业 班 级 软件工程 软件16-1班 一、实验目的：

1. 熟练掌握顺序查找方法；

2. 熟练掌握二分查找方法即BinSearch()；

二、实验内容：

1. 用顺序查找法对表进行查找； 2.用二分查找法对查找表进行查找 3.建立二叉排序树并对该树进行查找

三、实验设备及软件环境：

软件需求：

Code Blocks 硬件需求：

微型计算机

四、实验过程及结果： #include using namespace std;

template struct BinTreeNode {

ElemType data;

BinTreeNode *leftChild; BinTreeNode *rightChild; BinTreeNode() {

leftChild=rightChild=NULL; }

BinTreeNode(ElemType &item, BinTreeNode *lChild, BinTreeNode *rChild) {

data=item;

leftChild=lChild; rightChild=rChild; } };

template class BinarySortTree {

protected:

BinTreeNode *root;

void DestroyHelp(BinTreeNode *&r); ///销毁以r为根二叉排序树 void PreOrderHelp(const BinTreeNode *r)const;///先序 void InOrderHelp(const BinTreeNode*r)const;///中序 void PostOrderHelp(const BinTreeNode*r)const;///后序 int HeightHelp(const BinTreeNode *r) const;///高

int NodeCountHelp(const BinTreeNode*r)const;///结点 int leafCountHelp(const BinTreeNode*r)const;///叶子

BinTreeNode*SearchHelp(const KeyType &key,BinTreeNode *&f)const;///查找关键字为key的数据元素

void DeleteHelp(BinTreeNode *&p);///删除p指向的结点 public:

BinarySortTree();

BinTreeNode *GetRoot()const; ///返回二叉树的根 bool Empty() const;

bool GetElem(const BinTreeNode*cur, ElemType &e)const;///用E返回节点数据元素值

void InOrder()const;///先 void PreOrder()const;///中 void PostOrder()const;///后

int NodeCount()const;///结点个数 int Height()const;///高度

BinTreeNode *Search(const KeyType &key) const;///查找关键字为key的数据元素

bool Insert(const ElemType &e); ///插入数据元素e

bool Delete(const KeyType &key); ///删除关键字为e的数据元素 };

template

BinarySortTree::BinarySortTree() {

root=NULL; }

template

void BinarySortTree::DestroyHelp(BinTreeNode *&r)///销毁 {

if(r!=NULL) {

DestoryHelp(r->leftChild); DestoryHelp(r->rightChild);

delete r; r=NULL; } }

template

void BinarySortTree::DeleteHelp(BinTreeNode *&p)///删除 {

BinTreeNode *tmpPtr,*tmpF;

if(p->leftChild==NULL && p->rightChild==NULL) {

delete p; p=NULL; }

else if(p->leftChild==NULL) {

tmpPtr=p;

p=p->rightChild; delete tmpPtr; } else {

tmpF=p;

tmpPtr=p->leftChild;

while(tmpPtr->rightChild!=NULL) {

tmpF=tmpPtr;

tmpPtr=tmpPtr->rightChild; }

p->data=tmpPtr->data;

if(tmpF->rightChild==tmpPtr) {

DeleteHelp(tmpF->rightChild); } else {

DeleteHelp(tmpF->leftChild); } } }

template

void BinarySortTree::PreOrderHelp(const BinTreeNode*r)const///先序 {

if(r!=NULL)