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;
  }

}

实现二叉搜索树

package SearchBinaryTree;

public class SearchBinaryTree<T> {
  SearchBinaryTreeNode<T> root;

  public boolean isEmpty(){
    if(root==null){
      return true;
    }
    return false;
  }

  public void Visit(SearchBinaryTreeNode<T> root){
    if(root==null){
      System.out.println("this tree is empty!");
    }
    System.out.println(root.getData());
  }

  public SearchBinaryTreeNode<T> getRoot(){
    if(root==null){
      root=new SearchBinaryTreeNode<T>();
    }
    return root;
  }

  public SearchBinaryTree(){
    this.root=null;
  }

  /*
   * 创造一颗二叉树
   */
  public void CreateTree(SearchBinaryTreeNode<T> node, T data) {
    if (root == null) {
      root = new SearchBinaryTreeNode<T>();
    } else {
      if (Math.random() > 0.5) {          //采用随机方式创建二叉树
        if (node.leftChild == null) {
          node.leftChild = new SearchBinaryTreeNode<T>(data);
        } else {
          CreateTree(node.leftChild, data);
        }
      } else {
        if (node.rightChild == null) {
          node.rightChild = new SearchBinaryTreeNode<T>(data);
        } else {
          CreateTree(node.rightChild, data);
        }
      }
    }
  }

  /*
   * 在二查搜索树中进行搜索
   */
  public SearchBinaryTreeNode<T> search(SearchBinaryTreeNode<T> root,T value){
    SearchBinaryTreeNode<T> current=root;
    while((root!=null)&&(current.getData()!=value)){
      //需要注意的是java中泛型无法比较大小,在实际的使用时我们可以使用常见的数据类型来替代这个泛型,这样就不会出错了
      current=(value<current.getData()?search(current.leftChild,value):search(current.rightChild,value));
    }
    return current;
  }

  public SearchBinaryTreeNode<T> insertNode( T value){
    SearchBinaryTreeNode<T> p=root,pre=null;
    while(p!=null){
      pre=p;
      //需要注意的是java中泛型无法比较大小,在实际的使用时我们可以使用常见的数据类型来替代这个泛型,这样就不会出错了
      if(p.getData()<value){
        p=p.rightChild;
      }else{
        p=p.leftChild;
      }
    }
    if(root==null){
      root=new SearchBinaryTreeNode<T>(value);
    }else if(pre.getData()<value){
      pre.rightChild=new SearchBinaryTreeNode<T>(value);
    }else{
      pre.leftChild=new SearchBinaryTreeNode<T>(value);
    }
  }

  /*
   * 合并删除
   */
  public void deleteByMerging(SearchBinaryTreeNode<T> node){
    SearchBinaryTreeNode<T> temp=node;
    if(node!=null){
      //若被删除节点没有右子树,用其左子树的根节点来代替被删除节点
      if(node.rightChild!=null){
        node=node.leftChild;
      }else if(node.leftChild==null){
        //若被删节点没有左子树,用其有字数的最左端的节点代替被删除的节点
        node=node.rightChild;
      }else{
        //如果被删节点左右子树均存在
        temp=node.leftChild;
        while(temp.rightChild!=null){
          temp=temp.rightChild;   //一直查找到左子树的右节点
        }

        //将查找到的节点的右指针赋值为被删除节点的右子树的根
        temp.rightChild=node.rightChild;
        temp=node;
        node=node.leftChild;
      }
      temp=null;
    }
  }

  /*
   * 复制删除
   */
  public void deleteByCoping(SearchBinaryTreeNode<T> node){
    SearchBinaryTreeNode<T> pre=null;
    SearchBinaryTreeNode<T> temp=node;
    //如果被删节点没有右子树,用其左子树的根节点来代替被删除节点
    if(node.rightChild==null){
      node=node.leftChild;
    }else if(node.leftChild==null){
      node=node.rightChild;
    }else{
      //如果被删节点的左右子树都存在
      temp=node.leftChild;
      pre=node;
      while(temp.rightChild!=null){
        pre=temp;
        temp=temp.rightChild;   //遍历查找到左子树的最右端的节点
      }
      node.data=temp.data;      //进行赋值操作
      if(pre==node){
        pre.leftChild=node.leftChild;
      }else{
        pre.rightChild=node.rightChild;
      }
    }
    temp=null;
  }

}

测试类

package SearchBinaryTree;

public class SearchBinaryTreeTest {

  public static void main(String []args){
    SearchBinaryTree<Integer> tree=new SearchBinaryTree<Integer>();
    for(int i=1;i<10;i++){
      tree.CreateTree(new SearchBinaryTreeNode<Integer>(), i);
    }

    //搜索
    tree.search(tree.root, 7);

    //合并删除
    tree.deleteByMerging(new SearchBinaryTreeNode<Integer>(8));

    //复制删除
    tree.deleteByCoping(new SearchBinaryTreeNode<Integer>(6));
  }

}

好了,就是这样!

以上这篇Java创建二叉搜索树,实现搜索,插入,删除的操作实例就是小编分享给大家的全部内容了,希望能给大家一个参考,也希望大家多多支持我们。

您可能感兴趣的文章:

  • 二叉搜索树实例练习
  • Java 实现二叉搜索树的查找、插入、删除、遍历
  • java二叉查找树的实现代码
(0)

相关推荐

  • 二叉搜索树实例练习

    一棵二叉查找树是按二叉树结构来组织的.这样的树可以用链表结构表示,其中每一个结点都是一个对象.结点中除了数据外,还包括域left,right和p,它们分别指向结点的左儿子.右儿子,如果结点不存在,则为NULL. 它或者是一棵空树:或者是具有下列性质的二叉树: 1)若左子树不空,则左子树上所有结点的值均小于它的根结点的值: (2)若右子树不空,则右子树上所有结点的值均大于它的根结点的值: (3)左.右子树也分别为二叉查找树: 显然满足了上面的性质,那么二叉查找树按中序遍历就是按从小到大的顺序遍历,

  • Java 实现二叉搜索树的查找、插入、删除、遍历

    由于最近想要阅读下JDK1.8 中HashMap的具体实现,但是由于HashMap的实现中用到了红黑树,所以我觉得有必要先复习下红黑树的相关知识,所以写下这篇随笔备忘,有不对的地方请指出- 学习红黑树,我觉得有必要从二叉搜索树开始学起,本篇随笔就主要介绍Java实现二叉搜索树的查找.插入.删除.遍历等内容. 二叉搜索树需满足以下四个条件: 若任意节点的左子树不空,则左子树上所有结点的值均小于它的根结点的值: 若任意节点的右子树不空,则右子树上所有结点的值均大于它的根结点的值: 任意节点的左.右子

  • java二叉查找树的实现代码

    本文实例为大家分享了java二叉查找树的具体代码,供大家参考,具体内容如下 package 查找; import edu.princeton.cs.algs4.Queue; import edu.princeton.cs.algs4.StdOut; public class BST<Key extends Comparable<Key>, Value> { private class Node { private Key key; // 键 private Value value;

  • Java创建二叉搜索树,实现搜索,插入,删除的操作实例

    Java实现的二叉搜索树,并实现对该树的搜索,插入,删除操作(合并删除,复制删除) 首先我们要有一个编码的思路,大致如下: 1.查找:根据二叉搜索树的数据特点,我们可以根据节点的值得比较来实现查找,查找值大于当前节点时向右走,反之向左走! 2.插入:我们应该知道,插入的全部都是叶子节点,所以我们就需要找到要进行插入的叶子节点的位置,插入的思路与查找的思路一致. 3.删除: 1)合并删除:一般来说会遇到以下几种情况,被删节点有左子树没右子树,此时要让当前节点的父节点指向当前节点的左子树:当被删节点

  • Java实现二叉搜索树的插入、删除功能

    二叉树的结构 public class TreeNode { int val; TreeNode left; TreeNode right; TreeNode() { } TreeNode(int val) { this.val = val; } } 中序遍历 中序遍历:从根节点开始遍历,遍历顺序是:左子树->当前节点->右子树,在中序遍历中,对每个节点来说: 只有当它的左子树都被遍历过了(或者没有左子树),它才会被遍历到.在遍历右子树之前,一定会先遍历当前节点. 中序遍历得到的第一个节点是没

  • 利用java实现二叉搜索树

    二叉搜索树的定义 它是一颗二叉树 任一节点的左子树上的所有节点的值一定小于该节点的值 任一节点的右子树上的所有节点的值一定大于该节点的值 特点: 二叉搜索树的中序遍历结果是有序的(升序)! 实现一颗二叉搜索树 实现二叉搜索树,将实现插入,删除,查找三个方面 二叉搜索树的节点是不可以进行修改的,如果修改,则可能会导致搜索树的错误 二叉搜索树的定义类 二叉搜索树的节点类 -- class Node 二叉搜索树的属性:要找到一颗二叉搜索树只需要知道这颗树的根节点. public class BST {

  • java基础二叉搜索树图文详解

    目录 概念 直接实践 准备工作:定义一个树节点的类,和二叉搜索树的类. 搜索二叉树的查找功能 搜索二叉树的插入操作 搜索二叉树删除节点的操作-难点 性能分析 总程序-模拟实现二叉搜索树 和java类集的关系 总结 概念 二叉搜索树又称二叉排序树,它或者是一棵空树,或者是具有以下性质的二叉树:1.若它的左子树不为空,则左子树上所有节点的值都小于根结点的值.2.若它的右子树不为空,则右子树上所有节点的值都大于根结点的值.3.它的左右子树也分别为二叉搜索树 直接实践 准备工作:定义一个树节点的类,和二

  • java实现 二叉搜索树功能

    一.概念 二叉搜索树也成二叉排序树,它有这么一个特点,某个节点,若其有两个子节点,则一定满足,左子节点值一定小于该节点值,右子节点值一定大于该节点值,对于非基本类型的比较,可以实现Comparator接口,在本文中为了方便,采用了int类型数据进行操作. 要想实现一颗二叉树,肯定得从它的增加说起,只有把树构建出来了,才能使用其他操作. 二.二叉搜索树构建 谈起二叉树的增加,肯定先得构建一个表示节点的类,该节点的类,有这么几个属性,节点的值,节点的父节点.左节点.右节点这四个属性,代码如下 sta

  • C#创建二叉搜索树的方法

    本文实例讲述了C#创建二叉搜索树的方法.分享给大家供大家参考.具体如下: public static BinaryTreeNode BuildBinarySearchTree(int[] sortedArray) { if (sortedArray.Length == 0) return null; int _mid = sortedArray.Length / 2; BinaryTreeNode _root = new BinaryTreeNode(sortedArray[_mid]); in

  • Java封装数组实现包含、搜索和删除元素操作详解

    本文实例讲述了Java封装数组实现包含.搜索和删除元素操作.分享给大家供大家参考,具体如下: 前言:在上一小节中我们已经会了如何获取和如何修改数组中的元素,在本小节中我们将继续学习如何判断某个元素是否在数组中存在.查询出某个元素在数组中的位置.以及删除数组中元素等方法的编写. 1.查找数组中是否包含元素e,返回true或false //查找数组中是否包含元素e public boolean contains(int e) { for (int i = 0; i < size; i++) { if

  • 在Java中实现二叉搜索树的全过程记录

    目录 二叉搜索树 有序符号表的 API 实现二叉搜索树 二叉搜索树类 查找 插入 最小/大的键 小于等于 key 的最大键/大于等于 key 的最小键 根据排名获得键 根据键获取排名 删除 总结 二叉搜索树 二叉搜索树结合了无序链表插入便捷和有序数组二分查找快速的特点,较为高效地实现了有序符号表.下图显示了二叉搜索树的结构特点(图片来自<算法第四版>): 可以看到每个父节点下都可以连着两个子节点,键写在节点上,其中左边的子节点的键小于父节点的键,右节点的键大于父节点的键.每个父节点及其后代节点

  • C语言实现二叉搜索树的完整总结

    1. 二叉树的构建 我们都知道二叉搜索树的特点是:当前节点的值大于它的左子树的值,小于等于右子树的值.所以我们这里可以通过迭代的方式构建二叉搜索树,当然也可以通过递归的方式构建二叉树. 定义一个结构体,表示节点: typedef struct NODE{ int va; struct NODE *left,*right; }Node; ①通过迭代的方式实现二叉搜索树的构建,值得注意的是,这种方式构建二叉搜索树的时候,需要定义一个变量,表示这个节点插入的位置是父节点的左子节点还是右子节点的位置,同

随机推荐