数据结构实现二叉排序树

这篇具有很好参考价值的文章主要介绍了数据结构实现二叉排序树。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

摘  要

二叉排序树(Binary Search Tree,BST),又叫做二叉查找树,二叉搜索树,是一种对查找和排序都有用的特殊二叉树。因为二叉排序树的中序遍历有序性,即得到的递增的序列,由于有序,因此其查找与二分查找类似,每次都可以缩小查找范围,查询效率较高。同时因为二叉排序树的中序遍历存在有序性,所以首先要查找待插入元素的插入位置,当查找不成功时再将待插入元素作为新的叶子节点成为最后一个查找结点的左孩子或者右孩子。二叉排序树的创建可以从空树开始,按照插入关键字的顺序依次进行插入操作,最后得到一颗二叉排序树。二叉排序树的删除需要先在二叉排序树中找到待删除节点,然后执行删除操作。假设指针p指向待删除节点,指针f指向p的父节点。根据待删除节点所在位置的不同,删除操作的处理方法也不同。

关键词:二叉排序树  中序遍历  左孩子  右孩子  

  • 需求分析

1.1 课设主要研究问题

用顺序或二叉链表作为存储结构:

1) 以回车('\n')为输入结束标志,输入数列 L,生成一棵二叉排序树 T;

2) 对二叉排序树 T 作中序遍历,输出结果;

3) 输入元素x,查找二叉排序树T,若存在含x的结点,则删除该结点,并作中

序遍历(执行操作 2);否则输出信息“无 x”;

4) 以二叉排序树结构设计并实现一个排序算法

概要设计

2.1 课设应用的理论知识

二叉排序树或是一棵空树,或具有以下特征:

  1. 若左子树非空,其左子树上所有结点的值均小于根节点的值。
  2. 若右子树非空,其右子树上所有结点的值均大于根节点的值。
  3. 左右子树也满足二叉排序树的特性。
  4. 左子树结点值<根节点值<右子树结点值,所以如果对二叉排序树进行中序遍历可以得到一个递增的有序序列。

添加:从根节点开始往下寻找为null的位置插入结点。

删除:1、找到删除结点所在位置; 2、找到其中序遍历相邻节点; 3、将相邻结点的值赋给删除结点,删除相邻结点。               

2.2 程序流程图

c语言数据结构实现二叉排序树的基本运算算法,数据结构,算法,c语言

详细设计

  建立二叉排序树采用边查找边插入的方式。查找函数采用递归的方式进行查找。如果查找到相等的则插入其左子树。否则返回当前结点的上一个结点,然后利用插入函数将该元素插入原树。对二叉树进行中序遍历采用递归函数的方式。在根结点不为空的情况下,先访问左子树,再访问根结点,最后访问右子树。删除结点函数,采用边查找边删除的方式。如果没有查找到进行提示如果查找到结点则将其左于树最右边的节点的数据传给它,然后删除其左子树最右边的节点。

程序主要设计了四个功能:首先是创建二叉排序树,完成后出现任务菜单,以数字代码确定,二叉排序树的中序遍历和查找,删除步骤,最后完成,结束。

对二叉树进行中序遍历采用递归函数的方式。在根结点不为空的情况下,先访问 左子树,再访问根结点,最后访问右子树。

删除结点函数,采用边查找边删除的方式。如果没有查找到,则不对树做任何的 修改;如果查找到结点,则分四种情况分别进行讨论:1、该结点左右子树均为空,那么令其右子树子承父业代替被删除节点的位置即可;2、该结点右子树为空,那么令其左子树子承父业代替被删除节点的位置即可;3、该结点左右子树均不为空,就不能采用子承父业的方法了,根据二叉排序树的中序遍历有序性删除该节点,可以利用其直接前驱或者直接后继来代替被删除节点的位置,然后删除其直接前驱或者直接后继即可。

直接前驱:在中序遍历中,节点p的直接前驱就是其左子树中的最右节点。即沿着p的左子树一直访问其右子树,直到没有右子树,这样就找到了最右节点,也就是直接前驱。

    直接后继:在中序遍历中,节点p的直接后继就是其右子树中的最左节点。即沿着p的右子树一直访问其左子树,直到没有左子树,这样就找到了最左节点,也就是直接后继。

在进行算法设计时,将题目分成以下五个模块:

1、中序遍历,符合升序输出

void inorder(node *&root)      

{

  if(root!=NULL)

  {

   inorder(root->left);

   cout<<root->data<<' ';

   inorder(root->right);

  }

 }

2、在查找树中插入元素

void insert(node *&ptr,int item)   

{

  if(ptr==NULL)

  ptr=new node(item);

  else if(item<ptr->data)

  insert(ptr->left,item);

  else insert(ptr->right,item);

 }

3、在查找树中查找元素 

node *find(node *&ptr,int item)   

{

     if(ptr==NULL)

         return NULL;

     if(ptr->data==item)

         return ptr;

     else if(item<ptr->data)

         find(ptr->left,item);

     else find(ptr->right,item);

 }

4、在查找树中查找肯定存在的元素,并返回其引用

node *&findy(node *&ptr,int item)  

 {

        if(ptr->data==item)

            return ptr;

        else if(item<ptr->data)

            findy(ptr->left,item);

        else findy(ptr->right,item);

 }

 node* rl()

{

return left;

}

 node* rr()

{

return right;

}

5、删除指定值为所在结点

void dele(node *&ptr)       

 {

  if(ptr->rl()==NULL&&ptr->rr()==NULL)

   ptr=NULL;

  else if(ptr->rr()==NULL)

   ptr=ptr->rl();

  else

   ptr=ptr->rr();

 }

private:

 int data;

 node *left;               

 node *right;              

};

完整程序代码文章来源地址https://www.toymoban.com/news/detail-774489.html

#include <iostream>
using namespace std;

class node
{
public:
node(int i):data(i),left(NULL),right(NULL){}
 void inorder(node *&root)      //中序遍历,符合升序输出
 {
  if(root!=NULL)
  {
   inorder(root->left);
      cout<<root->data<<' ';
      inorder(root->right);
  }
 }
 void insert(node *&ptr,int item)  //在查找树中插入元素
 {
  if(ptr==NULL)
   ptr=new node(item);
  else if(item<ptr->data)
   insert(ptr->left,item);
  else insert(ptr->right,item);
 }
 node *find(node *&ptr,int item)  //在查找树中查找元素,找到返回所在结点指针,找不到返回空指针。
 {
        if(ptr==NULL)
            return NULL;
        if(ptr->data==item)
            return ptr;
        else if(item<ptr->data)
            find(ptr->left,item);
        else find(ptr->right,item);
 }
 node *&findy(node *&ptr,int item)  //在查找树中查找肯定存在的元素,并返回其引用
 {
        if(ptr->data==item)
            return ptr;
        else if(item<ptr->data)
            findy(ptr->left,item);
        else findy(ptr->right,item);
 }
 node* rl(){return left;}
 node* rr(){return right;}

 void dele(node *&ptr)       //删除值为item所在结点
 {
  if(ptr->rl()==NULL&&ptr->rr()==NULL)
   ptr=NULL;
  else if(ptr->rr()==NULL)
   ptr=ptr->rl();
  else
   ptr=ptr->rr();
 }
private:
 int data;
 node *left;               //左孩子结点
 node *right;              //右孩子结点
};

int main()
{
 int t,i=0,j;
 cout<<"         二叉排序树的实现"<<endl;
 cout<<"1.二叉排序树T的输入:"<<endl;
 cout<<"输入数字个数(结点个数):";
 cin>>t;
 cout<<"输入"<<t<<"个数字,数字之间用空格隔开:";
 cin>>j;
 node *x=new node(j);
 for(;i<t-1;i++)
 {
  cin>>j;
  x->insert(x,j);
 }
 cout<<"中序遍历为:";
 x->inorder(x);               //作中序遍历
 cout<<"\n";
 cout<<"2.二叉排序树T的元素查找和删除:"<<endl;
 cout<<"\n输入操作(当输入0时程序结束):"<<endl;
 cin>>j;
 while(j!=0)
 {
  
   node *t=x->find(x,j);          //定位结点
   if(t!=NULL)
   {
    node *&y=x->findy(x,j);
    x->dele(y);
 cout<<"中序遍历为:";
 x->inorder(x);
   }
   else cout<<"无"<<j;
   cout<<"\n输入操作(当输入0时程序结束):"<<endl;
   cin>>j;
 }
 return 0;
}

到了这里,关于数据结构实现二叉排序树的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 二叉树的基本操作-C语言实现-数据结构作业

    目录  (1)二叉树的创建; (2)二叉树的先序、中序和后序遍历输出; (3)输出二叉树的叶子节点和度为2的节点的数量; (4)输出二叉树的深度; (5)将二叉树所有节点的左右子树互换(左子树变右子树,右子树变左子树); (6)参考书上,二叉树按层次输出(一行输出一层); (7)删除二

    2024年02月04日
    浏览(46)
  • 【数据结构初阶】八、非线性表里的二叉树(二叉树的实现 -- C语言链式结构)

    ========================================================================= 相关代码gitee自取 : C语言学习日记: 加油努力 (gitee.com)  ========================================================================= 接上期 : 【数据结构初阶】七、非线性表里的二叉树(堆的实现 -- C语言顺序结构)-CSDN博客  ==========

    2024年02月08日
    浏览(48)
  • 数据结构入门(C语言版)二叉树的顺序结构及堆的概念及结构实现应用

    普通的二叉树是不适合用数组来存储的,因为可能会存在大量的空间浪费。而完全二叉树更适合使用顺序结构存储。现实中我们通常把堆(一种二叉树)使用 顺序结构的数组来存储 ,需要注意的是 这里的堆和操作系统虚拟进程地址空间中的堆是两回事 ,一个是 数据结构 ,一

    2023年04月19日
    浏览(50)
  • 【数据结构】【算法】二叉树、二叉排序树、树的相关操作

    树结构是以分支关系定义的一种层次结构,应用树结构组织起来的数据,逻辑上都具有明显的层次关系。 操作系统中的文件管理系统、网络系统中的域名管理、数据库系统中的索引管理等都使用了树结构来组织和管理数据。 树 Tree 是由n个节点组成的有限集合。在任意一颗非

    2024年02月04日
    浏览(50)
  • 【数据结构】二叉排序树——平衡二叉树的调整

    参考视频: 懒猫老师-数据结构-(59)平衡二叉树【互动视频】 (1)什么是平衡二叉树 平衡二叉树(Balanced Binary Tree)是一种特殊的二叉查找树,它的目的是保持树的高度尽量平衡,以保证查找、插入、删除等操作的时间复杂度为 O(log n)。 常见的平衡二叉树算法包括 AVL 树、红

    2024年02月04日
    浏览(38)
  • 二叉排序树的创建、插入、查找和删除【数据结构】

    若它的左子树不空,则左子树上所有结点的值均小于它根结点的值。 若它的右子树不空,则右子树上所有结点的值均大于它根结点的值。 它的左、右树又分为⼆叉排序树 二叉排序树也叫二叉查找树、二叉搜索树 题目描述 给出一个数据序列,建立二叉排序树,并实现插入功

    2024年01月24日
    浏览(43)
  • 数据结构----完全二叉树的时间复杂度讲解,堆排序

    目录 一.建堆的时间复杂度 1.向上调整算法建堆 2.向下调整算法建堆 二.堆排序 1.概念 2.代码思路 3.代码实现 我们就以极端情况考虑时间复杂度(满二叉树+遍历所有层) 假设所有节点个数为N,树的高度为h N = 2^0+2^1+2^2......+2^(h-1) 即N = 2^h - 1 h = log(N+1) 时间复杂度我们以交换次数为

    2024年03月14日
    浏览(63)
  • 二叉排序树的插入删除和查找(数据结构实训)(难度系数100)

    二叉排序树的插入删除和查找 pre: 前序遍历 in: 中序遍历 post:后序遍历 insert: 插入,本题中不会出现相同的元素 delete: 删除,删除成功输出TRUE,没有该元素则输出FALSE,删除的方法是如果有左子树,以左子树中最大值作为新的树根,否则,以右子树最小值作为树根。 search:

    2024年01月25日
    浏览(50)
  • 【C语言 数据结构】二叉树的遍历

    所谓先序遍历二叉树,指的是从根结点出发,按照以下步骤访问二叉树的每个结点: 访问当前结点; 进入当前结点的左子树,以同样的步骤遍历左子树中的结点; 遍历完当前结点的左子树后,再进入它的右子树,以同样的步骤遍历右子树中的结点; 先序遍历这棵二叉树的过

    2024年02月04日
    浏览(42)
  • 【数据结构】树、二叉树的概念和二叉树的顺序结构及实现

    之前我们学习了顺序表、链表以及栈和队列这些数据结构,但这些数据结构都是线性的(一对一)。接下来要学习 非线性的数据结构——树(二叉树) ,相比前面的,树的结构更加复杂,话不多说,直接进入正题吧。 树是一种 非线性的数据结构 ,它是 一对多(也有可能是

    2024年02月07日
    浏览(40)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包