In this article, the definition of binary sort tree:
- If the left subtree is not empty, the values of all nodes on the left subtree are less than or equal to the values of its root node
- If the right subtree is not empty, the value of all nodes on the right subtree is greater than that of its root node
- The left and right subtrees are also binary sort trees
The class created in this article and the elements in it:
| Class name | element |
| BST_Demo (main class) | |
| BinarySortTree | BST_Node root |
| BST_Node | int value |
| BST_Node left | |
| BST_Node right |
Creation of binary sort tree:
The creation idea of binary sort tree is as follows:
1. In BST_ Node class defines a method AddNode(BST_Node node) for adding nodes
2. Define a new method TreeAddNode method in BinarySortTree class, nested call AddNode method, and add judgment conditions. Enables the main function to add elements through the BinarySortTree object.
3. In the main function, use the for loop to traverse the array involved in the construction of binary sort tree, and call the TreeAddNode method in each loop, passing the parameters as the traversed array elements
The following is the specific idea and code implementation!
BST_ Node class: definition of public void AddNode(BST_Node node)
The idea of recursion is realized. Define a pointer to the current node (in the following description, the current node refers to target). At this time, there are four situations:
1. The left child node is empty, and the value of the node to be inserted is less than or equal to the value of the current node Set the left child node of the current node as node
2. The right child node is empty, and the value of the node to be inserted is greater than the value of the current node Set the right child node of the current node as node
Note: the above two cases are the conditions for the end of recursion.
3. The left child node is not empty, and the value of the node to be inserted is less than or equal to the value of the current node Recursion to the left child of the current node
4. The right child node is not empty, and the value of the node to be inserted is greater than the value of the current node Recursion to the right child node of the current node
public void AddNode(BST_Node node){
if(this.left==null && node.value<=this.value){
this.left=node;
}else if(this.right==null && node.value>this.value){
this.right=node;
}else if(this.left!=null && node.value<=this.value){
this.left.AddNode(node);
}else{
this.right.AddNode(node);
}
}BinarySortTree class: definition of public void BSTAddNode(BST_Node node)
You need to judge whether the element root representing the root node of the binary sort tree in this class is empty. If it is empty, you can directly assign the passed node parameter to root. Otherwise, the AddNode method is called by root to add elements.
public void BSTAddNode(BST_Node node){
if(root==null){
root=node;
}else{
root.AddNode(node);
}
}BST_ main(String[] args) in demo class: creation of binary sort tree:
import java.util.*;
public static void main(String[] args){
Random r=new Random();
int[] Array=new int[10];
for(int i=0;i<Array.length;i++){
Array[i]=r.nextInt(20);
}
System.out.println("Original array:");
System.out.println(Arrays.toString(Array));
BinarySortTree BST=new BinarySortTree();
for(int i:Array){
BST.BSTAddNode(new BST_Node(i));
}
}Now the binary sort tree is created!
Middle order traversal:
Code implementation:
BST_Node class:
public void InorderTraversal(){
if(this.getLeft()!=null){
this.getLeft().InorderTraversal();
}
System.out.println(this.toString());
if(this.getRight()!=null){
this.getRight().InorderTraversal();
}
}BinarySortTree class:
public void InorderTraversal(){
if(this.root==null){
System.out.println("The current binary sort tree is empty and cannot be traversed!");
}else{
this.root.InorderTraversal();
}
}So far, the middle order traversal is completed!
Delete node:
First show the method of deleting nodes defined in the BinarySortTree class. The specific code will be analyzed later!
public void DeleteNode(int value)
public void DeleteNode(int value){
BST_Node target=SearchNode(value);
if(target==null){
System.out.println("No node to delete found!");
return;
}
BST_Node parent=SearchParent(target.getValue());
if(target.getLeft()==null && target.getRight()==null){
if(parent==null) {
this.root=null;
return;
}
if(parent.getRight()==target){
parent.setRight(null);
return;
}else{
parent.setLeft(null);
return;
}
}else if(target.getLeft()!=null && target.getRight()!=null){ //The deleted node has two subtrees
int RightMinValue=DeleteRightMin(target.getRight());
target.setValue(RightMinValue);
return;
}else{ //The deleted node has only one subtree
if(parent==null){ //Delete node as root node
if(this.root.getLeft()!=null){
this.root=root.getLeft();
return;
}else{
this.root=root.getRight();
return;
}
}
if(target.getLeft()!=null){ //The deleted node is not a root node and only has left child nodes
if(parent.getLeft()==target){
parent.setLeft(target.getLeft());
return;
}else{
parent.setRight(target.getLeft());
return;
}
}else{ //Only the right child node exists when deleting a node
if(parent.getLeft()==target){
parent.setLeft(target.getRight());
return;
}else{
parent.setRight(target.getRight());
return;
}
}
}
}Three cases
- Delete a node with two subtrees
- Delete nodes with only one subtree
- Delete nodes without subtrees
The processing of the above three cases requires obtaining the node to be deleted and the parent node of the node, so two methods are defined
The method is similar to preorder traversal:
- First consider whether the current node (this) is empty
- Then, the left and right child nodes of the current node are discussed separately according to the size relationship between the lookup value and the current node value
- When the value of the search node is less than the value of the current node, search to the left subtree, but you need to determine whether the left subtree is empty.
- When the value of the search node is greater than the value of the current node, search in the right subtree direction. You also need to determine whether the right subtree is empty.
Method 1: public BSY_Node SearchNode(int value)
public BST_Node SearchNode(int value){
if(this.value==value){
return this;
}
if(value<this.value){
if(this.left==null){
return null;
}else{
return this.left.SearchNode(value);
}
}else{
if(this.right==null){
return null;
}else{
return this.right.SearchNode(value);
}
}
}Method 2: public BST_Node SearchParent(int value)
public BST_Node SearchParent(int value) {
if ((this.left != null && this.left.value == value) || (this.right != null && this.right.value == value)) {
return this;
}
if (value < this.value) {
if (this.left == null) {
return null;
} else {
return this.left.SearchParent(value);
}
} else {
if (this.right == null) {
return null;
} else {
return this.right.SearchParent(value);
}
}
}So far, the method of finding the node of the specified value and the parent node of the corresponding value is completed!
1. Delete the node with two subtrees
Because the binary sort tree after deleting nodes needs to have its properties. When a node with two subtrees is deleted, the node can be regarded as the root node and its two subtrees form a binary sort tree. Then deleting the root node can be completed by searching the smallest node in the right subtree of the root node to replace the root node.
Note: at this time, you also need to consider whether it is a root node,
Reason: when the smallest node in the right subtree is used as the root node, it is less than (may be equal to) the remaining nodes in the right subtree and greater than the left and right nodes in the left subtree.
The specific operation of substitution: record the value of the minimum node, delete it, and then assign the recorded value to the root node
Get the element of the smallest node in the right subtree and delete the node:
public int DeleteRightMin(BST_Node RightRoot)
public int DeleteRightMin(BST_Node RightRoot){
BST_Node temp=RightRoot;
if(temp.getLeft()==null){
BST_Node parent=this.root.SearchParent(temp.getValue());
if(temp==RightRoot){
parent.setRight(temp.getRight());
return temp.getValue();
}
parent.setLeft(temp.getRight());
return temp.getValue();
}else{
return this.DeleteRightMin(temp.getLeft());
}
}2. Delete a node with only one subtree
Two situations need to be considered: 1. It is the root node 2. Non root node
Reason: the root node cannot get its parent node
1. When it is a root node (parent==null), judge whether its only subtree is a left subtree or a right subtree, and perform different operations according to different judgments. Take the root node with only left subtree as an example: if the root node has only left subtree, you need to delete the root node and assign the root node to the left subtree of the root node. this.root=this.root.getLeft(); The same is true for right subtrees only.
2. For a non root node (else), judge whether the node to be deleted is the left or right subtree of its parent node. At the same time, determine whether the only subtree of the node to be deleted is the left or right subtree. There are four cases:
| situation | Coping methods |
| parent.getLeft()==target && target.getLeft()!=null | parent.setLeft(target.getLeft()) |
| parent.getLeft()==target && target.getRight()!=null | parent.setLeft(target.getRight()) |
| parent.getRight()==target && target.getLeft()!=null | Parent.setRight(target.getLeft()) |
| parent.getRight()==target && target.getRight()!=null | Parent.setRight(target.getRight()) |
3. Delete nodes without subtree
There are two cases: 1. There is no root node of subtree 2. Leaf node
The two cases can be separated by judging whether the parent is empty if(parent==null)
1. There is no root node of the subtree. Just set this.root==null.
2. For a leaf node, you need to consider whether the leaf node is the left child node or the right child node of its parent node. If it is a left child node, parent.setLeft(null);
So far, all ideas, namely the code implementation, have been sorted out
All codes:
1.BST_Demo.java
package Tree experiment.Binary sort tree;
import java.util.Arrays;
public class BST_Demo {
public static void main(String[] args){
int[] Array={7,3,10,12,5,1,9};
System.out.println("Original array:");
System.out.println(Arrays.toString(Array)); //Print original array
System.out.println("______________________________");
System.out.println("Create a binary sort tree of the array and traverse it in middle order:");
BinarySortTree BST=new BinarySortTree();
for(int i:Array){ //Create a binary sort tree by traversing the array and adding nodes
BST.BSTAddNode(new BST_Node(i));
}
BST.InorderTraversal(); //Middle order traversal binary sort tree
System.out.println();
BST.DeleteNode(3); //Delete node with value 3
BST.InorderTraversal();
}
}
2.BinarySortTree.java
package Tree experiment.Binary sort tree;
public class BinarySortTree {
private BST_Node root;
public BinarySortTree(){
}
public BinarySortTree(BST_Node root){
this.root=root;
}
public BST_Node getRoot(){
return this.root;
}
public void setRoot(BST_Node root){
this.root=root;
}
public void BSTAddNode(BST_Node node){
if(root==null){
root=node;
}else{
root.AddNode(node);
}
}
public void InorderTraversal(){
if(this.root==null){
System.out.println("The current binary sort tree is empty and cannot be traversed!");
}else{
this.root.InorderTraversal();
}
}
//Find the node corresponding to the element value
public BST_Node SearchNode(int value){
if(root==null){
System.out.println("The binary sort tree is empty and cannot be found!");
}
return root.SearchNode(value);
}
public BST_Node SearchParent(int value){
//In both cases, there is no parent node. 1. There is only one root node. 2. Find the parent node of a node, which is the root node
if((this.root.getLeft()==null && this.root.getRight()==null) || this.root.getValue()==value){
return null;
}else{
return this.root.SearchParent(value);
}
}
/**
* @param RightRoot Root node of right subtree
* @return The value of the minimum right child node found
*/
public int DeleteRightMin(BST_Node RightRoot){
BST_Node temp=RightRoot;
if(temp.getLeft()==null){
BST_Node parent=this.root.SearchParent(temp.getValue());
if(temp==RightRoot){
parent.setRight(temp.getRight());
return temp.getValue();
}
parent.setLeft(temp.getRight());
return temp.getValue();
}else{
return this.DeleteRightMin(temp.getLeft());
}
}
public void DeleteNode(int value){
BST_Node target=SearchNode(value);
if(target==null){
System.out.println("No node to delete found!");
return;
}
BST_Node parent=SearchParent(target.getValue());
if(target.getLeft()==null && target.getRight()==null){
if(parent==null) {
this.root=null;
return;
}
if(parent.getRight()==target){
parent.setRight(null);
return;
}else{
parent.setLeft(null);
return;
}
}else if(target.getLeft()!=null && target.getRight()!=null){ //The deleted node has two subtrees
int RightMinValue=DeleteRightMin(target.getRight());
target.setValue(RightMinValue);
return;
}else{ //The deleted node has only one subtree
if(parent==null){ //Delete node as root node
if(this.root.getLeft()!=null){
this.root=root.getLeft();
return;
}else{
this.root=root.getRight();
return;
}
}
if(target.getLeft()!=null){ //The deleted node is not a root node and only has left child nodes
if(parent.getLeft()==target){
parent.setLeft(target.getLeft());
return;
}else{
parent.setRight(target.getLeft());
return;
}
}else{ //Only the right child node exists when deleting a node
if(parent.getLeft()==target){
parent.setLeft(target.getRight());
return;
}else{
parent.setRight(target.getRight());
return;
}
}
}
}
}
3.BST_Node.java
package Tree experiment.Binary sort tree;
public class BST_Node {
private int value;
private BST_Node left;
private BST_Node right;
public BST_Node(int value){
this.value=value;
}
public int getValue(){
return this.value;
}
public void setValue(int value){
this.value=value;
}
public BST_Node getLeft() {
return left;
}
public void setLeft(BST_Node left) {
this.left = left;
}
public BST_Node getRight() {
return right;
}
public void setRight(BST_Node right) {
this.right = right;
}
public String toString(){
return "BST_Node[value="+this.value+"]";
}
public void AddNode(BST_Node node){
if(node==null) {
System.out.println("The current node is empty and cannot be added!");
return;
}else {
if(node.value<=this.value){
if(this.left==null){
this.left=node;
}else{
this.left.AddNode(node);
}
}else{
if(this.right==null){
this.right=node;
}else{
this.right.AddNode(node);
}
}
}
}
public void InorderTraversal(){
if(this.left!=null){
this.left.InorderTraversal();
}
System.out.println(this.toString());
if(this.right!=null){
this.right.InorderTraversal();
}
}
public BST_Node SearchNode(int value){
if(this.value==value){
return this;
}
if(value<this.value){
if(this.left==null){
return null;
}else{
return this.left.SearchNode(value);
}
}else{
if(this.right==null){
return null;
}else{
return this.right.SearchNode(value);
}
}
}
public BST_Node SearchParent(int value) {
if ((this.left != null && this.left.value == value) || (this.right != null && this.right.value == value)) {
return this;
}
if (value < this.value) {
if (this.left == null) {
return null;
} else {
return this.left.SearchParent(value);
}
} else {
if (this.right == null) {
return null;
} else {
return this.right.SearchParent(value);
}
}
}
}