文章详情

短信预约-IT技能 免费直播动态提醒

请输入下面的图形验证码

提交验证

短信预约提醒成功

什么是二分搜索树

2024-04-02 19:55

关注

这篇文章主要介绍“什么是二分搜索树”,在日常操作中,相信很多人在什么是二分搜索树问题上存在疑惑,小编查阅了各式资料,整理出简单好用的操作方法,希望对大家解答”什么是二分搜索树”的疑惑有所帮助!接下来,请跟着小编一起来学习吧!

一、树结构

树是一种很特别的数据结构,树这种数据结构叫做 “树” 就是因为它 长得像一棵树  。但是这棵树画成的图长得却是一棵倒着的树,根在上,叶在下。树是图的一种,树和图的区别就在于:树是没有环的,而图是可以有环的。

树状图是一种数据结构,它是由n(n>=1)个有限节点组成一个具有层次关系的集合。把它叫做“树”是因为它看起来像一棵倒挂的树,也就是说它是根朝上,而叶朝下的。

什么是二分搜索树

二、为什么要有树结构

2.1 树结构是一种天然的组织结构

比如说电脑中的文件夹,我们需要找到一个特定的文件,需要到某个文件夹下去找这个文件,计算机的文件存储的结构来源于生活。再比如说图书馆,我们知道图书馆里面有  历史类、数理类、计算机类,我们想要找到关于java的书籍,就需要到计算机类的Java中去找到我们需要的图书

什么是二分搜索树

比如公司里面的层级结构:CEO、HR CTO等等,还有我们比较常见的家谱等等,都是类似于树结构

什么是二分搜索树

将数据使用树结构后,会更加的高效

三、二分搜索树

3.1 特点

什么是二分搜索树

二分搜索树天然的具有递归特性

什么是二分搜索树

二叉树不一定是满的,一个接电脑也是二叉树、空也是二叉树

什么是二分搜索树

四、具体代码实现

在进行相关操作之前, 先定义一个支持泛型的节点类, 用于存储二分搜索树每个节点的信息, 这个类作为二分搜索树的一个内部类,  二分搜索树的类声明以及Node节点类声明如下:

public class BST> {  private class Node{  public E e;  public Node left,right;  public Node(E e){  this.e = e;  left = null;  right = null;  }  }  //节点  private Node root;  // 树容量  private int size;  public BST(){  root = null;  size = 0;  }  public int size(){  return size;  }  public boolean isEmpty(){  return size == 0;  }  }

4.1 添加元素

二分搜索树添加元素的非递归写法,和链表很像,由于二分搜索树本身的递归特性, 所以可以很方便的使用递归实现向二分搜索树中添加元素,

什么是二分搜索树

代码实现:

//向二分搜索树添加新的元素e  public void add(E e){  root = add(root,e);  }  //向以Node为根的二分搜索树中插入元素 E,递归算法  //返回插入新节点后二分搜索树的根  private Node add(Node node,E e){  if(node == null){  size++;  return new Node(e);  }  if(e.compareTo(node.e) < 0)  node.left = add(node.left,e);  else if(e.compareTo(node.e) > 0)  node.right = add(node.right,e);  return node;  }

4.2 查找元素

由于二分搜索树没有下标, 所以针对二分搜索树的查找操作, 我们需要定义一个 contains() 方法, 查看二分搜索树是否包含某个元素,  返回一个布尔型变量

代码实现:

//看二分是搜索树中是否包含元素e  public boolean contains(E e){  return contains(root,e);  }  //看以Node为根的二分搜索树中是否包含元素e,递归算法  private boolean contains(Node node,E e){  if(node == null)  return false;  if(e.compareTo(node.e) == 0)  return true;  else if(e.compareTo(node.e) < 0)  return contains(node.left,e);  else //e.compareTo(node.e) > 0  return contains(node.right,e);  }

4.3 遍历操作

一、 什么是遍历操作

前序遍历 : 对当前节点的遍历在对左右孩子节点的遍历之前, 遍历顺序 : 当前节点->左孩子->右孩子中序遍历 :  对当前节点的遍历在对左右孩子节点的遍历中间, 遍历顺序 : 左孩子->当前节点->右孩子后序遍历 : 对当前节点的遍历在对左右孩子节点的遍历之后,  遍历顺序 : 左孩子->右孩子->当前节点

二、 前序遍历

//二分搜索树前序遍历  public void preOrder(){  preOrder(root);  }  //前序遍历以Node为根的二分搜索树,递归算法  private void preOrder(Node node){  if(node == null)  return;  System.out.println(node.e);  preOrder(node.left);  preOrder(node.right);  }  public void preOrderNR(){  Stack stack = new Stack<>();  stack.push(root);  while(!stack.isEmpty()){  Node cur = stack.pop();  System.out.println(cur.e);  if(cur.right != null)  stack.push(cur.right);  if(cur.left != null)  stack.push(cur.left);  }  }

三、 中序遍历

什么是二分搜索树

//二分搜索树的中序遍历  public void inOrder(){  inOrder(root);  }  //中序遍历以Node为根的二分搜索树,递归算法  private void inOrder(Node node){  if(node ==null)  return;  inOrder(node.left);  System.out.println(node.e);  inOrder(node.right);  }

四、 后序遍历

什么是二分搜索树
//二分搜索树的后序遍历  public void postOrder(){  inOrder(root);  }  public void levelOrder(){  Queue q = new LinkedList();  q.add(root);  while (!q.isEmpty()){  Node cur = q.remove();  System.out.println(cur.e);  if(cur.left != null)  q.add(cur.left);  if(cur.right != null)  q.add(cur.right);  }  }  //后序遍历以Node为根的二分搜索树,递归算法  private void postOrder(Node node){  if(node ==null)  return;  inOrder(node.left);  inOrder(node.right);  System.out.println(node.e);  }

五、 理解前中后

什么是二分搜索树

二分搜索树前序非递归写法

什么是二分搜索树

什么是二分搜索树

到此,关于“什么是二分搜索树”的学习就结束了,希望能够解决大家的疑惑。理论与实践的搭配能更好的帮助大家学习,快去试试吧!若想继续学习更多相关知识,请继续关注编程网网站,小编会继续努力为大家带来更多实用的文章!

阅读原文内容投诉

免责声明:

① 本站未注明“稿件来源”的信息均来自网络整理。其文字、图片和音视频稿件的所属权归原作者所有。本站收集整理出于非商业性的教育和科研之目的,并不意味着本站赞同其观点或证实其内容的真实性。仅作为临时的测试数据,供内部测试之用。本站并未授权任何人以任何方式主动获取本站任何信息。

② 本站未注明“稿件来源”的临时测试数据将在测试完成后最终做删除处理。有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341

软考中级精品资料免费领

  • 历年真题答案解析
  • 备考技巧名师总结
  • 高频考点精准押题
  • 2024年上半年信息系统项目管理师第二批次真题及答案解析(完整版)

    难度     813人已做
    查看
  • 【考后总结】2024年5月26日信息系统项目管理师第2批次考情分析

    难度     354人已做
    查看
  • 【考后总结】2024年5月25日信息系统项目管理师第1批次考情分析

    难度     318人已做
    查看
  • 2024年上半年软考高项第一、二批次真题考点汇总(完整版)

    难度     435人已做
    查看
  • 2024年上半年系统架构设计师考试综合知识真题

    难度     224人已做
    查看

相关文章

发现更多好内容

猜你喜欢

AI推送时光机
位置:首页-资讯-后端开发
咦!没有更多了?去看看其它编程学习网 内容吧
首页课程
资料下载
问答资讯