数据结构/数据结构与算法实验四二叉排序树与快速排序（查找与排序算法的实现）

2023-02-22 191

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 数据结构/数据结构与算法实验四二叉排序树与快速排序（查找与排序算法的实现）

1.实验题目

1.已知二叉树T的结点形式为(lchild、data、count、rchild)，其中count为查找次数计数。在树中查找值为X的结点，若找到则该结点的count加1，函数返回值为TRUE；否则，作为一个新结点插入树中，插入后仍为二叉排序树，且函数返回值为FALSE。写出其非递归算法（迭代算法）。（教材P310，习题八的“四、应用题”的第10题。）

2.验证快速排序的递归算法。

3.利用快速排序的思想编写算法，对关键字取值为整数的一个数据元素序列进行整理，使所有关键字为负值的数据元素排在关键字为非负值的数据元素之前。

2.实验要求

查找实验要求实现以下功能：

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

2.先给出二叉排序树的先序、中序和后序遍历结果，然后从键盘输入一个整数，在二叉排序树中删除该整数，并给出是否删除成功的结果，若删除成功，则再给出删除后的二叉排序树的先序、中序和后序遍历结果。

3.先给出二叉排序树的先序、中序和后序遍历结果，然后从键盘输入一个整数，调用实现“二、实验题目”的功能。根据函数调用结果，显示查找成功的该结点的count值，或者是给出插入新的结点后的二叉排序树的先序、中序和后序遍历结果。

排序实验要求：

1.对从键盘输入的任意个整数，通过递归快速排序使之成为有序的序列，输出每一趟排序的结果。

2.对从键盘输入的任意个整数，按照“1.实验题目”的第1小题的要求输出结果。

3.算法思路

1.建立二叉排序树

在主程序中运用while语句输入一行数据，以-1为终止。输入时，调用二叉排序树的插入函数。插入函数的逻辑如下：先查找该数，若找到则插入失败。若未找到则插入。插入时，若该树为空树，则创建根结点。若该树不为空树，则在相应位置创建含有所需数据的结点。

2.遍历二叉排序树

先序、中序、后序遍历二叉树。先序遍历二叉排序树时，先访问当前结点，再先序遍历左子树，最后先序遍历右子树。中序遍历二叉排序树时，先中序遍历左子树，再访问根结点，最后中序遍历右子树。后序遍历二叉排序树时，先后序遍历左子树，再后序遍历右子树，最后访问根结点。

3.删除节点

先查找要删除的点p。若查找成功，则调用删除算法，删除成功。若查找失败，则删除也失败。删除时，从根结点开始重新查找该结点。若p的数据比当前访问的结点的数据小，则在左子树上删除p点。若p的数据比当前访问的结点的数据大，则在右子树上删除p点。若找到了p结点，则判断其有没有左子树或右子树。若其没有左子树也没有右子树，则是个叶结点，直接删除。若只有右子树但没有左子树，则将点p替换成右子树上第一个结点。若其只有左子树但没有右子树，则将p替换成左子树上第一个结点。若其不仅有右子树而且有左子树，则找到其右子树上最左的结点s，将s替换p，并删掉s结点。

4.查找并记录访问次数

在设计类时，结点除了数据域、指针域，还有一个count域记录结点被访问的次数。利用迭代法，通过循环的终止条件控制是否找到p点。若没找到p点，则调用插入结点的算法。若找到p点，则count增加1。

5.利用快速排序的思想将负数排在正数前

在快速排序的算法中，我们将数组第一个元素作为基准，将数组划分成比基准小、比基准大两个部分。在这个算法中，我们以0而非数组第一个元素作为基准元素，便可以将比0小的数排在比0大的数之前。我们仍然用e=elem[low]这一语句记录数组第一个元素，但这个元素不是基准，而是在i和j指针“撞”在一起的位置上将这个元素放回。无论第一个元素正负，结果上都会是前面是负数，后面是非负数。

4.输出演示

数据的输入

先序遍历

中序遍历

后序遍历

删除数据（删除失败）

删除数据（删除成功）

删除成功后的遍历序列

查找成功

查找失败，插入成功

5.源代码

题目1

binarySortTree.h

#pragma once
#include"binTreeNode.h"
#include<Windows.h>
#include<iostream>
using namespace std;
template <class elemtype>
class binarySortTree
{
private:
  binTreeNode<elemtype>* root;
public:
  bool isEmpty() {//判空
    return root == NULL;
  }
  binTreeNode<elemtype>* find(const elemtype& key, binTreeNode<elemtype>*& f) const{
    //从f结点开始向下查找值为key的结点
    binTreeNode<elemtype>* p=root;
    f = NULL;//初始化
    while (p != NULL && p->data != key) {//往下搜索
      if (key < p->data) {
        f = p;
        p = p->lchild;
      }
      else {
        f = p;
        p = p->rchild;
      }
    }
    return p;//若数值不存在，则指向NULL结点被返回
  }
  void preOrder(binTreeNode<elemtype>* r) const {//先序遍历
    if (r != NULL) {
      cout << r->getData()<<" ";
      preOrder(r->lchild);
      preOrder(r->rchild);
    }
  }
  void inOrder(binTreeNode<elemtype>* r) const {//中序遍历
    if (r != NULL) {
      inOrder(r->lchild);
      cout << r->getData()<<" ";
      inOrder(r->rchild);
    }
  }
  void postOrder(binTreeNode<elemtype>* r) const {//后序遍历
    if (r != NULL) {
      postOrder(r->lchild);
      postOrder(r->rchild);
      cout << r->getData()<<" ";
    }
  }
  bool append(const elemtype& e) {
    //为平衡二叉树添加一个新的结点
    binTreeNode<elemtype>* f=NULL;//指向被查找结点双亲
    if (find(e, f) == NULL) {//查找失败，插入成功
      binTreeNode<elemtype>* p;
      p = new binTreeNode<elemtype>(e);
      if (isEmpty())//若树是空树
        root = p;
      else if (e < f->data)//若不是空树，则插入到相应位置上
        f->lchild = p;
      else
        f->rchild = p;
      return true;
    }
    else
      return false;//查找成功，不能插入数值重复的结点，插入失败
  }
  void Delete(const elemtype& k, binTreeNode<elemtype>*& p) {
    //在p为根的二叉排序树上删除关键字为k的结点
    binTreeNode<elemtype>* s, * temp;
    if (p != NULL)
      if (k < p->data)//还没找到p
        Delete(k, p->lchild);//递归地在p的左子树上删除关键字为k的结点
      else if (k > p->data)
        Delete(k, p->rchild);//递归地在p的左子树上删除关键字为k的结点
      else if (p->lchild != NULL && p->rchild != NULL){//找到p,但是p的左右子树都不空 
        //s = Min(p->rchild);
        temp = p->rchild;
        while (temp->lchild != NULL) {
          temp = temp->lchild;
        }//找到p的右子树上最小的数s，替换掉p，然后删掉s
        s = temp;
        p->data = s->data;//将p替换成s
        Delete(s->data, p->rchild);//递归地删掉s
      }
      else {//相等找到,但是左或右为空
        temp = p;
        if (p->lchild == NULL)       p = p->rchild;//左子树空，则将p替换为右子树上第一个结点
        else if (p->rchild == NULL)  p = p->lchild;//右子树空，则将p替换为左子树上第一个结点
        delete temp;
      }
  }
  bool t2(int val){//第二题：先查找，查找成功则删除成功，查找失败则删除失败
    binTreeNode<elemtype>* f = NULL;
    binTreeNode<elemtype>* p = find(val, f);
    if (p == NULL) {
      //查找失败，删除失败
      cout << "删除失败!";
      return false;
    }
    else {
      //查找成功，删除成功
      //deleteNode(p);
      Delete(val, root);
      cout << "\n删除成功！";
      return true;
    }
  }
  bool t3(int key) {//第三题：先查找，查找成功则计数，查找失败则插入
    binTreeNode<elemtype>* p=root,*f = root;
    f = NULL;//f为要找的结点的双亲结点
    while (p != NULL && p->data != key) {//利用迭代法查找
      if (key < p->data) {
        f = p;
        p = p->lchild;
      }
      else {
        f = p;
        p = p->rchild;
      }
    }
    if (p != NULL) {//查找成功
      p->count++;//访问到了p结点，则p的被访问次数需要计数
      cout << "查找成功！";
      return true;
    }
    else {//查找到最后查找失败时，若数据比双亲结点的数小，则说明双亲结点左子树为空
      //若数据比双亲结点的数大，则说明双亲结点右子树为空
      cout << "查找失败！正在插入该结点";
      if(root==NULL)
        root= new binTreeNode<elemtype>(key);//若为空树，则需要创建一个根结点
      else {//在相应位置上创建新的结点，并且查找失败
        if (key > f->data)
          f->rchild = new binTreeNode<elemtype>(key);
        else
          f->lchild = new binTreeNode<elemtype>(key);
      }
      return false;
    }
  }
  binTreeNode<elemtype>* getRoot() {
    return this->root;
  }
  binarySortTree() {
    root = NULL;//默认的无参构造函数
  }
};

binTreeNode.h

#pragma once
#include<Windows.h>
template<class elemtype>
struct binTreeNode
{
  elemtype data;
  int count;//结点被访问次数
  binTreeNode<elemtype>* lchild;
  binTreeNode<elemtype>* rchild;
  binTreeNode(elemtype mdata = 0) {//构造函数，接受无参数构造
    count = 0;
    data = mdata;
    lchild = NULL;
    rchild = NULL;
  }
  int getcount() {
    return count;
  }
  elemtype getData() {
    return data;
  }
};

main.cpp

#include<iostream>
#include"binarySortTree.h"
using namespace std;
int main() {
  int num;//利用num变量输入数字
  int fun;//选择功能
  int val;//删除或插入数据时输入
  binarySortTree<int> bintree;
  cout << "请输入数据，以-1为终止";
  cin >> num;
  while (num != -1) {//输入数据，以-1为终止
    bintree.append(num);
    cin >> num;
  }
  binTreeNode<int>* p=NULL;//工作指针
  binTreeNode<int>* root=bintree.getRoot(),*mroot = bintree.getRoot();//根结点
  do{
    cout << "\n请选择你想要使用的功能：\n";
    cout << "1.先序遍历\n2.中序遍历\n3.后序遍历\n4.删除数据\n5.查找数据\n6.退出";
    cin >> fun;
    switch (fun) {
    case 1:
      cout << "先序遍历序列为:";
      bintree.preOrder(root);
      break;
    case 2:
      cout << "\n中序遍历序列为:";
      bintree.inOrder(root);
      break;
    case 3:
      cout << "\n后序遍历序列为:";
      bintree.postOrder(root);
      break;
    case 4:
      cout << "\n请输入你想删除的数字:";
      cin >> val;
      bintree.t2(val);
      break;
    case 5:
      cout << "\n请输入你要插入或查找的数字:";
      cin >> val;
      if (bintree.t3(val)) {//调用题3中用迭代实现的函数
        mroot = root;
        p=bintree.find(val,mroot);//find函数中的参数是取引用调用，所以根结点地址需要在调用函数前重置
        cout <<"这个节点已被访问次数"<< p->getcount();//函数只要返回查找成功或失败而不自带输出访问次数的功能
      }
      else {
        cout << "自动显示遍历结果！";
        cout << "\n先序遍历序列为:";
        bintree.preOrder(root);
        cout << "\n中序遍历序列为:";
        bintree.inOrder(root);
        cout << "\n后序遍历序列为:";
        bintree.postOrder(root);
      }
      break;
    default:break;
    }
  } while (fun != 6);//输入6以退出
  cout << "\n运行完成！";

第二题

main.cpp

#include<iostream>
#include<stdio.h>
using namespace std;
int times = 0;//全局变量，记录是第几次排序
int n = 0;//全局变量，记录数组长度
template<class elemtype>
void quicksort(elemtype elem[], int low, int high) {
  elemtype e = elem[low];
  int i = low, j = high;
  while (i < j) {
    while (i < j && elem[j] >= e)j--;
    if (i < j) elem[i++] = elem[j];
    while (i < j && elem[i] <= e) i++;
    if (i < j) elem[j--] = elem[i];
  }
  elem[i] = e;
  times++;
  printf("第%d次排列的结果为:", times);
  for (int t = 0; t < n; t++)
    cout << elem[t] << " ";
  cout << endl;//在递归进入下一层排序前先输出本次排序结果
  if (low < i - 1) quicksort(elem, low, i - 1);
  if (i + 1 < high)quicksort(elem, i + 1, high);
}
template<class elemtype>
void findNegative(elemtype elem[], int n) {
  elemtype e = elem[0];
  int i = 0, j =n-1;
  while (i < j) {
    while (i < j && elem[j] >= 0)j--;
    if (i < j) elem[i++] = elem[j];
    while (i < j && elem[i] <0) i++;
    if (i < j) elem[j--] = elem[i];
  }//寻找负数的思想与快速排序类似
  //快速排序中将数字与第一个数比
  //这里将数字与0比
  //最后无论第一个数的大小都要将第一个数放到对应位置。
  elem[i] = e;
  //算法已经结束，没有递归的后续过程
}
int main() {
  cout << "请输入数组中数的个数：\n";
  cin >> n;
  int *arr=new int[n];
  cout << "请输入数据:";
  for (int i = 0; i < n; i++)
    cin >> arr[i];
  int func,low,high;
  cout << "请选择功能:";
  cout << "1.快速排序";
  cout << "2.将负数整理在非负数前";
  cin >> func;
  switch (func) {
    case 1:
      low = 0;
      high = n - 1;
      quicksort(arr, low, high);
      break;
    case 2:
      findNegative(arr, n);
      break;
  }
  for (int i = 0; i < n; i++)
    cout << arr[i]<<" ";
}

数据结构/数据结构与算法实验四二叉排序树与快速排序（查找与排序算法的实现）

1.实验题目

2.实验要求

查找实验要求实现以下功能：

排序实验要求：

3.算法思路

1.建立二叉排序树

2.遍历二叉排序树

3.删除节点

4.查找并记录访问次数

5.利用快速排序的思想将负数排在正数前

4.输出演示

5.源代码

题目1

binarySortTree.h

binTreeNode.h

main.cpp

第二题

main.cpp

热门文章

最新文章

相关课程

相关电子书

探索云世界

热门

云计算

大数据

云原生

人工智能

数据库

开发与运维

活动广场

任务中心

训练营

直播

乘风者计划

下载

镜像站

技术资料

数据结构/数据结构与算法实验四 二叉排序树与快速排序（查找与排序算法的实现）

1.实验题目

2.实验要求

查找实验要求实现以下功能：

排序实验要求：

3.算法思路

1.建立二叉排序树

2.遍历二叉排序树

3.删除节点

4.查找并记录访问次数

5.利用快速排序的思想将负数排在正数前

4.输出演示

5.源代码

题目1

binarySortTree.h

binTreeNode.h

main.cpp

第二题

main.cpp

热门文章

最新文章

相关课程

相关电子书

数据结构/数据结构与算法实验四二叉排序树与快速排序（查找与排序算法的实现）