Java creates binary search trees to search insert and delete operation instances

Java implements a 2-fork search tree, and realizes the search, insert and delete operations on the tree (merge and delete, copy and delete).

First of all, we should have a coding idea, which is roughly as follows:

1. Search: According to the data characteristics of the 2-fork search tree, we can realize the search according to the comparison of nodes' worth. When the search value is greater than the current node, go to the right, or go to the left!

2. Insertion: We should know that all the insertions are leaf nodes, so we need to find the position of the leaf node to be inserted, and the idea of insertion is the same as the idea of search 1.

3. Delete:

1) Merge and delete: 1. Generally speaking, there are several situations in which the deletion point has left subtree but not right subtree. In this case, the parent node of the current node should point to the left subtree of the current node; When the truncated point has a right subtree and no left subtree, the parent node of the current node should point to the right subtree. When an abridged point has both a left and a right subtree, we can find the right-most node of the left subtree of the abridged point, and then let the right or left "pointer" of the node point to the right subtree of the abridged point

2) Copy and delete: Copy and delete is relatively simple deletion operation, but also the most commonly used deletion operation. There are also roughly the following three situations: if the current node has no left subtree and a right subtree, let the root node of the current right subtree replace the truncated point; If the current node has no right subtree and a left subtree, let the root node of the current left subtree replace the deleted node; Currently being truncated points there are both left subtree and right subtree, we will find the point being abridged avatars, can be found in the left subtree of the point being abridged the rightmost end node, and let the node values assigned to be abridged, then don't forget to make this double of the parent node point to double "pointer" is empty, (actually it doesn't matter in the Java, garbage disposal mechanism for automatic processing). You can also do this by acting as a surrogate node at the leftmost end of the right subtree of the current truncated point.

So let's do the code.

The first is ## 2 cross search tree node class ##

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


}

Implement 2 fork search tree

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

  /*
   *  create 1 star 2 tree 
   */
  public void CreateTree(SearchBinaryTreeNode<T> node, T data) {
    if (root == null) {
      root = new SearchBinaryTreeNode<T>();
    } else {
      if (Math.random() > 0.5) {          // Create in a random fashion 2 tree 
        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);
        }
      }
    }
  }

  /*
   *  in 2 Search the search tree 
   */
  public SearchBinaryTreeNode<T> search(SearchBinaryTreeNode<T> root,T value){
    SearchBinaryTreeNode<T> current=root;
    while((root!=null)&&(current.getData()!=value)){
      // One thing to note java The medium generics can't be compared in size, but in practice we can replace the generic type with a common data type, so we don't make mistakes 
      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;
      // One thing to note java The medium generics can't be compared in size, but in practice we can replace the generic type with a common data type, so we don't make mistakes 
      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);
    }
  }

  /*
   *  Merge to delete 
   */
  public void deleteByMerging(SearchBinaryTreeNode<T> node){
    SearchBinaryTreeNode<T> temp=node;
    if(node!=null){
      // If the deleted node has no right subtree , Replace the deleted node with the root node of its left subtree 
      if(node.rightChild!=null){
        node=node.leftChild;
      }else if(node.leftChild==null){
        // If the truncated point does not have a left subtree, replace the deleted node with its leftmost node of the number of words 
        node=node.rightChild;
      }else{
        // If the truncated point exists around the subtree 
        temp=node.leftChild;
        while(temp.rightChild!=null){
          temp=temp.rightChild;   //1 Find the right node of the left subtree 
        }

        // Assigns the right pointer to the found node to the root of the right subtree of the deleted node 
        temp.rightChild=node.rightChild;
        temp=node;
        node=node.leftChild;
      }
      temp=null;
    }
  }

  /*
   *  Copy to delete 
   */
  public void deleteByCoping(SearchBinaryTreeNode<T> node){
    SearchBinaryTreeNode<T> pre=null;
    SearchBinaryTreeNode<T> temp=node;
    // If the truncated point does not have a right subtree, replace the deleted node with the root of its left subtree 
    if(node.rightChild==null){
      node=node.leftChild;
    }else if(node.leftChild==null){
      node=node.rightChild;
    }else{
      // If both the left and right subtrees of the truncated point exist 
      temp=node.leftChild;
      pre=node;
      while(temp.rightChild!=null){
        pre=temp;
        temp=temp.rightChild;   // Traversal finds the rightmost node of the left subtree 
      }
      node.data=temp.data;      // Perform an assignment operation 
      if(pre==node){
        pre.leftChild=node.leftChild;
      }else{
        pre.rightChild=node.rightChild;
      }
    }
    temp=null;
  }

}

The test class

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

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

    // Merge to delete 
    tree.deleteByMerging(new SearchBinaryTreeNode<Integer>(8));

    // Copy to delete 
    tree.deleteByCoping(new SearchBinaryTreeNode<Integer>(6));
  }

}

All right, that's it!