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

Java实现的二叉搜索树，并实现对该树的搜索，插入，删除操作（合并删除，复制删除）

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

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

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

3、删除：

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

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

接下来就上代码吧。

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

package SearchBinaryTree;

public class SearchBinaryTreeNode {
  T data;
  public SearchBinaryTreeNode leftChild;
  public SearchBinaryTreeNode 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 left,SearchBinaryTreeNoderight){
    this.data=da;
    this.leftChild=left;
    this.rightChild=right;
  }

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

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


}