Binary sort tree: BST

1. Introduce ：

2. Creation and traversal of binary sort tree 【 Traversal adopts medium order traversal 】：

Add node 【 stay Node Class 】：

Then in the binary sort tree class    

class BinarySortTree  Encapsulation method 

public void add(Node node) {
		if(node == null) {
			return;
		}

		// Determine the value of the incoming node , The value relationship with the root node of the current subtree 
		if(node.value < this.value) {
			// If the left child of the current node is null
			if(this.left == null) {
				this.left = node;
			} else {
				// Recursively add... To the left subtree 
				this.left.add(node);
			}
		} else { // The value of the added node is greater than   The value of the current node 
			if(this.right == null) {
				this.right = node;
			} else {
				// Recursively add... To the right subtree 
				this.right.add(node);
			}
		}
	}

3. Delete node 【 The following two methods are all encapsulated in a binary sort tree 】：

  You need to write two methods first ： 1. Find the target node 2. Find the parent node of the target node

1. Find the target node ：

public Node search(int value) {
   if(value == this.value) // Find the node 
      return this;
    else if(value < this.value) {// If the search value is less than the current node , Search left subtree recursively 
      // If the left child node is empty 
      if(this.left  == null)
         return null;
      else
         return this.left.search(value);
   } else { // If the search value is not less than the current node , Search right subtree recursively 
      if(this.right == null)
         return null;
      else
         return this.right.search(value);
   }
}

2. Find the parent node of the target node ：

public Node searchParent(int value) {
   // If the current node is the parent of the node to be deleted , Just go back to 
   if((this.left != null && this.left.value == value) ||
         (this.right != null && this.right.value == value))
      return this;
    else {
      // If the search value is less than the value of the current node ,  And the left child of the current node is not empty 
      if(value < this.value && this.left != null)
         return this.left.searchParent(value); // Search left subtree recursively 
       else if (value >= this.value && this.right != null)
         return this.right.searchParent(value); // Search right subtree recursively 
       else
         return null; //  No parent found 
   }
}

There are three situations ：

（1） Delete leaf node 【BinarySortTree Class 】：

（2） Delete a node with only one subtree

 

（3） Delete a node with two subtrees

public void delNode(int value) {
		if(root == null)
			return;
		else {
			// Find the target node 
			Node target = root.search(value);
			if(target == null) {
				System.out.println(" Unable to find the target node ");
				return;
			}
			// There is only one node 
			else if (root.right == null && root.left == null) {
				root = null;
				return;
			}
			// Find parent node 
			Node parent = searchParent(value);
			//1. Delete the leaf node 
			if (target.left == null && target.right == null) {
				if (parent.left != null && parent.left.value == target
						.value)
					parent.left = null;
				else if (parent.right != null && parent.right.value ==
						target.value)
					parent.right = null;
			}
			//2. Delete a node with only one subtree 
			//2.1  If target There's a Zuozi tree 

			if(target.left!=null&&target.right == null){
				//target Is the left subtree of the parent node 
				if (parent != null) {   //  !!!  Consider whether the parent node is empty 
					if (parent.left != null && parent.left.value == value)
						parent.left = target.left;
					//target Is the right node of the parent node 
					if (parent.right != null && parent.right.value == value)
						parent.right = target.left;
				}
				else root = target.left;
			}
			//2.2 If target There are right subtrees 
			else if(target.right!=null&&target.left == null){
				//target Is the left node of the parent node 
				if (parent != null) {
					if (parent.left != null && parent.left.value == value)
						parent.left = target.right;
					//target Is the right node of the parent node 
					if (parent.right != null && parent.right.value == value)
						parent.right = target.right;
				}
				else root = target.right;
			}
			// Delete two subtrees 
			// find target The minimum node of the right subtree of 
			else if (target.left != null && target.right != null) {
				int min = delRightTreeMin(target.right);  // Find the smallest left child node of the right subtree and delete , Then return the number 
				target.value = min; // Directly assigned to the target node 
			}
		}
	}

// Find the minimum left child of the right subtree of the target node 
	public int delRightTreeMin(Node node) {
		Node target = node;  //target  Temporary variable 
		// Loop to find the left child node , You'll find the minimum 
		while(target.left != null) {
			target = target.left;
		}
		// At this time  target It points to the smallest node 
		// Delete the minimum node 
		delNode(target.value);
		return target.value;
	}