2023年6月22日发(作者：)

数据结构B实验报告

一、 题目要求

1、实验目的

1．熟悉二叉排序树的定义。

2．理解二叉排序树的建立、插入和删除操作的算法。

2、实验题目

本实验要求实现以下功能：

1．对从键盘输入的顺序任意的若干个正整数建立一颗二叉排序树，以－1作为结束。

2．中序遍历该二叉树，输出遍历结果，查看是否有序。

3．从键盘输入一个整数，在二叉排序树中查找，找到该整数就删除之，没找到则输出没找到。输出删除结点后的中序遍历序列。

[测试数据]：

输入序列：67 13 11 88 45 9 60 20 -1

输出中序遍历序列应为：9 11 13 20 45 60 67 88

输入要删除的整数：45

江苏大学计算机学院

输出删除后的中序遍历序列应为：9 11 13 20 60 67 88

2019年 11 月 20 日

二、设计思路

结构体定义

template

class BinarySortTree

{

protected:

}

//数据成员

BinTreeNode*root;

BinarySortTree();

~BinarySortTree() {}

bool IsEmpty()const;

BinTreeNode*GetRoot()const;//求二叉树的根

BinTreeNode*Find(const ElemType&key, BinTreeNode*&f)const;//查找void Delete(BinTreeNode*&p);//删除关键字为key的数据元素

void CreateTree(BinTreeNode*&r);//创建树

void CreateTree();

void InOrder(void(*Visit)(const ElemType &)) const;

void InOrder(BinTreeNode*r, void(*Visit)(const ElemType&))const;

public:

关键字为key的数据元素

三、源代码

#include "pch.h"

#include

using namespace std;

enum Status { SUCCESS, OVER_FLOW, RANGE_ERROR, NOT_PRESENT, ENTRY_FOUND, UNDER_FLOW };//成功，越界，范围错误,未找到

const int MaxSize = 50;

template

struct Node

{

};

template

Node::Node()

{

}

template

Node::Node(ElemType e, Node*link)

{

next = NULL;

ElemType data;

Node*next;

Node();//普通构造函数

Node(ElemType e, Node*link = NULL);//带形参的构造函数

}

data = e;

next = link;

template

struct BinTreeNode

{

};

template

BinTreeNode::BinTreeNode()

{

}

template

BinTreeNode::BinTreeNode(const ElemType &d, BinTreeNode *lChild,

BinTreeNode *rChild)

{

}

//二叉排序树的类模板

template

class BinarySortTree

{

protected:

//数据成员

BinTreeNode*root;

BinarySortTree();

~BinarySortTree() {}

bool IsEmpty()const;

BinTreeNode*GetRoot()const;//求二叉树的根

BinTreeNode*Find(const ElemType&key, BinTreeNode*&f)const;//查找bool Insert(const ElemType &e);//插入数据元素e

void Delete(BinTreeNode*&p);//删除关键字为key的数据元素

void CreateTree(BinTreeNode*&r);//创建树

void CreateTree();

data = d; // 数据元素值

// 左孩子 leftChild = lChild;

leftChild = rightChild = NULL;

ElemType data;

BinTreeNode*leftChild;

BinTreeNode*rightChild;

BinTreeNode();

BinTreeNode(const ElemType &d, BinTreeNode *lChild = NULL,

BinTreeNode *rChild = NULL);

rightChild = rChild; // 右孩子

public:

关键字为key的数据元素

};

void InOrder(void(*Visit)(const ElemType &)) const;

void InOrder(BinTreeNode*r, void(*Visit)(const ElemType&))const;

template

BinarySortTree::BinarySortTree()

{

}

template

bool BinarySortTree::IsEmpty()const

{

}

template

BinTreeNode *BinarySortTree::GetRoot()const

{

}

template

BinTreeNode *BinarySortTree::Find(const ElemType&key,

BinTreeNode*&f)const

{

}

template

bool BinarySortTree::Insert(const ElemType &e)

{

BinTreeNode*f;

if (Find(e, f) == NULL)

BinTreeNode*p = GetRoot();

f = NULL;

while (p != NULL && p->data != key)

{

}

return p;

if (key < p->data)

{

}

else

{

}

f = p;

p = p->rightChild;

f = p;

p = p->leftChild;

return root;

return (root == NULL) ? 1 : 0;

root = NULL;

}

{

}

else return false;

BinTreeNode*p;

p = new BinTreeNode(e);

if (IsEmpty())

root = p;

f->leftChild = p;

f->rightChild = p;

else if (e < f->data)

else

return true;

template

void BinarySortTree::Delete(BinTreeNode *&p)

{

}

BinTreeNode *tmpPtr, *tmpF;

if (p->leftChild == NULL && p->rightChild == NULL) //p为叶子结点

{

}

else if (p->leftChild == NULL) //p的左子树为空，右孩子代替自己

{

}

else if (p->rightChild == NULL) //p的右子树为空，左孩子代替自己

{

}

else { //p左右子树都在，采用前述方案一

}

tmpF = p; tmpPtr = p->leftChild;

while (tmpPtr->rightChild != NULL)//寻找p的左子树中关键字最大的结点

{

}

p->data = tmpPtr->data;//将tmpPtr结点的数据值赋值给待删结点

//删除tmpPtr结点

if (tmpF->rightChild == tmpPtr)

Delete(tmpF->rightChild);

//待删结点p左子树中只有一个结点，tmpF==p，tmpPtr==tmpF->leftChild

Delete(tmpF->leftChild);

else

tmpF = tmpPtr; tmpPtr = tmpPtr->rightChild;

tmpPtr = p; p = p->leftChild; delete tmpPtr;

tmpPtr = p; p = p->rightChild; delete tmpPtr;

delete p; p = NULL;

template

void BinarySortTree::CreateTree()

{

}

template

void BinarySortTree::InOrder(BinTreeNode*r, void(*Visit)(const

ElemType&))const

{

}

template

void BinarySortTree::InOrder(void(*Visit)(const ElemType &)) const

{

}

template

void Display(const ElemType &e)

{

}

int main()

{

BinarySortTreetree;

Tree();

r(Display);

cout << endl;

int key;

cout << e << " ";

InOrder(root, Visit);

if (r != NULL)

{

}

InOrder(r->leftChild, Visit);

(*Visit)(r->data);

InOrder(r->rightChild, Visit);

cout << "请输入若干个整数，以-1结束（67 13 11 88 45 9 60 20 -1)" << endl;

int num;

int i = 1;

while (i <= 11)

{

}

cin >> num;

if (num == -1)

break;

Insert(num);

i++;

}

BinTreeNode*f;

cout << "请输入要查找的数据：n";

cin >> key;

if ((key, f) != NULL)

cout << "查找成功！n";

else cout << "查找失败！n";

int DelData;

cout << "请输入数据：";

cin >> DelData;

BinTreeNode*DelNode;

DelNode = new BinTreeNode(DelData);

(DelNode);

cout << "删除成功！";

r(Display);

system("pause");

四、运行结果

二叉排序树：

13119

4520676088