Java创建二叉搜索树,实现搜索,插入,删除的操作实例-创新互联

Java实现的二叉搜索树,并实现对该树的搜索,插入,删除操作(合并删除,复制删除)

创新互联建站,专注为中小企业提供官网建设、营销型网站制作、成都响应式网站建设公司、展示型成都网站建设、成都网站设计等服务,帮助中小企业通过网站体现价值、有效益。帮助企业快速建站、解决网站建设与网站营销推广问题。

首先我们要有一个编码的思路,大致如下:

1、查找:根据二叉搜索树的数据特点,我们可以根据节点的值得比较来实现查找,查找值大于当前节点时向右走,反之向左走!

2、插入:我们应该知道,插入的全部都是叶子节点,所以我们就需要找到要进行插入的叶子节点的位置,插入的思路与查找的思路一致。

3、删除:

1)合并删除:一般来说会遇到以下几种情况,被删节点有左子树没右子树,此时要让当前节点的父节点指向当前节点的左子树;当被删节点有右子树没有左子树,此时要让当前节点的父节点指向该右子树;当被删节点即有左子树又有右子树时,我们可以找到被删节点的左子树的最右端的节点,然后让这个节点的右或者左“指针”指向被删节点的右子树

2)复制删除:复制删除相对而言是比较简单的删除操作,也是最为常用的删除操作。大致也有以下三种情况:当前节点无左子树有右子树时,让当前右子树的根节点替换被删节点;当前节点无右子树有左子树时,让当前左子树的根节点替换被删除节点;当前被删节点既有左子树又有右子树时,我们就要找到被删节点的替身,可以在被删节点的左子树中找到其最右端的节点,并让这个节点的值赋给被删节点,然后别忘了让此替身节点的父节点指向替身的“指针”为空,(其实在Java中无关紧要了,有垃圾处理机制自动进行处理)。你也可以在当前被删节点的右子树的最左端的节点作为替身节点来实现这一过程。

接下来就上代码吧。

首先是## 二叉搜索树节点类 ##

package SearchBinaryTree;

public class SearchBinaryTreeNode<T> {
  T data;
  public SearchBinaryTreeNode<T> leftChild;
  public SearchBinaryTreeNode<T> rightChild;

  public SearchBinaryTreeNode(){
    this.data=null;
    this.leftChild=this.rightChild=null;
  }

  public SearchBinaryTreeNode(T da){
    this.data=da;
    this.leftChild=this.rightChild=null;
  }

  public SearchBinaryTreeNode(T da,SearchBinaryTreeNode<T> left,SearchBinaryTreeNode<T>right){
    this.data=da;
    this.leftChild=left;
    this.rightChild=right;
  }

  public T getData() {
    return data;
  }
  public void setData(T data) {
    this.data = data;
  }
  public SearchBinaryTreeNode<T> getLeftChild() {
    return leftChild;
  }
  public void setLeftChild(SearchBinaryTreeNode<T> leftChild) {
    this.leftChild = leftChild;
  }
  public SearchBinaryTreeNode<T> getRightChild() {
    return rightChild;
  }
  public void setRightChild(SearchBinaryTreeNode<T> rightChild) {
    this.rightChild = rightChild;
  }

  public boolean isLeaf(){
    if(this.leftChild==null&&this.rightChild==null){
      return true;
    }
    return false;
  }


}

网站题目:Java创建二叉搜索树,实现搜索,插入,删除的操作实例-创新互联
文章路径:https://www.cdcxhl.com/article4/ehhoe.html

成都网站建设公司_创新互联,为您提供外贸网站建设动态网站网站制作网站排名网站收录App设计

广告

声明:本网站发布的内容(图片、视频和文字)以用户投稿、用户转载内容为主,如果涉及侵权请尽快告知,我们将会在第一时间删除。文章观点不代表本网站立场,如需处理请联系客服。电话:028-86922220;邮箱:631063699@qq.com。内容未经允许不得转载,或转载时需注明来源: 创新互联

成都定制网站建设