Java Implement binary search tree of chain storage （ Recursive method ）

The definition of binary search tree ：

Binary search tree or an empty tree , Or a non empty binary tree with the following characteristics ：

1. If the left subtree is not empty , Then the key values of all nodes in the left subtree are less than the keywords of the root node ;

2. If the right subtree is not empty , Then the key values of all nodes in the right subtree are greater than those of the root node ;

3. Left 、 The right subtree itself is also a binary search tree .

Implementation of binary search tree , Functions include ：

1. Use an array to build a binary search tree

2. Middle order traversal and hierarchical traversal of binary search tree

3. Insert node

4. Find node

      5. Find the maximum and minimum values in a binary tree

6.  Get the direct parent of the node

7. Get the direct precursor and direct successor node of the node

8. Delete node

Tree node TreeNode See the last blog for the definition of ：Java Binary tree for chain storage

import java.lang.Integer;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
/*
* Binary sort tree （ Binary search tree ） The implementation of the
*/
public class BinarySearchTree {
private TreeNode<Integer> root; // The root node
public BinarySearchTree(){
root = null;
}
// Use an array to build a binary search tree
public TreeNode<Integer> buildBST(Integer[] array){
if(array.length == 0){
return null;
}else{
root = null; // Initialization tree is empty tree
for(int i=0; i<array.length; i++){ // Insert each element in turn
root = insertNode(root,array[i]);
}
return root;
}
}
// Insert a data field into the binary search tree data The node of , The newly inserted node must be a leaf node
public TreeNode<Integer> insertNode(TreeNode<Integer> node, Integer data){
if(node == null){ // The original tree is empty , The newly inserted record is the root node
node = new TreeNode<Integer>(data,null,null);
}else{
if(node.getData() == data){ // There are nodes with the same keyword in the tree , Do nothing
}else{
if(node.getData() > data){ // The root node > insert data , Insert into the left subtree
node.setLchild(insertNode(node.getLchild(),data));
}else{ // The root node < insert data , Insert into the right subtree
node.setRchild(insertNode(node.getRchild(),data));
}
}
}
return node;
}
// Middle order traversal of binary search tree , You can get an increasing sequence of numbers
public void inOrder(TreeNode<Integer> node){
if(node != null){
inOrder(node.getLchild());
System.out.print(node.getData()+" ");
inOrder(node.getRchild());
}
}
// Hierarchical traversal of binary search tree
public void levelOrder(TreeNode<Integer> root){
Queue<TreeNode<Integer>> nodeQueue = new LinkedList<TreeNode<Integer>>();
TreeNode<Integer> node = null;
nodeQueue.add(root); // Put the root node in the team
while(!nodeQueue.isEmpty()){ // The queue is not empty
node = nodeQueue.peek();
System.out.print(node.getData()+" ");
nodeQueue.poll(); // Team leader element out of the team
if(node.getLchild() != null){ // Zuozi tree is not empty , Then the left subtree enters the queue
nodeQueue.add(node.getLchild());
}
if(node.getRchild() != null){ // Right subtree is not empty , Then the right subtree enters the queue
nodeQueue.add(node.getRchild());
}
}
}
// The search data field is data The node of , If it does not exist , return null
public TreeNode<Integer> searchNode(TreeNode<Integer> node, Integer data){
while(node != null && node.getData() != data){
if(node.getData() > data){
node = node.getLchild(); // The root node > data , turn left
}else{
node = node.getRchild(); // The root node < data , turn right
}
}
return node;
}
// Find the maximum ： Keep looking for the right child node
public TreeNode<Integer> getMaxData(TreeNode<Integer> node){
if(node.getRchild() == null){
return node;
}else{
return getMaxData(node.getRchild());
}
}
// Find minimum ： Constantly looking for left child nodes
public TreeNode<Integer> getMinData(TreeNode<Integer> node){
if(node.getLchild() == null){
return node;
}else{
return getMinData(node.getLchild());
}
}
// The data field is data The direct parent of the node of parentNode
public TreeNode<Integer> getParentNode(TreeNode<Integer> root, Integer data){
TreeNode<Integer> parentNode = root;
if(parentNode.getData() == data){ // The parent of the root node is returned as null
return null;
}
while(parentNode != null){
// Find the left and right child nodes of the parent node of the current node , If it's equal , The parent node is returned
if((parentNode.getLchild() != null && parentNode.getLchild().getData() == data) ||
(parentNode.getRchild() != null && parentNode.getRchild().getData() == data)){
return parentNode;
}else{
if(parentNode.getData() > data){ // Find the parent node to the left
parentNode = parentNode.getLchild();
}else{
parentNode = parentNode.getRchild(); // Find the parent node to the right
}
}
}
return null;
}
/**
* Get the node node Direct antecedents of
* a. The left subtree of this node is not empty ： Its precursor node is the largest element of its left subtree
* b. The left subtree of this node is empty : Its precursor node is its ancestor node ( recursive ), And the right child of the ancestor node is also its ancestor node
* ( It's all the way to parent look for , The ancestor node after turning left )
*/
public TreeNode<Integer> getPrecessor(TreeNode<Integer> root,TreeNode<Integer> node){
if(node == null){
return null;
}
//a. The left subtree of this node is not empty ： Its precursor node is the largest element of its left subtree
if(node.getLchild() != null){
return getMaxData(node.getLchild());
}else{ //b. The left subtree of this node is empty : Its precursor node is its ancestor node ( recursive )
TreeNode<Integer> parentNode = getParentNode(root, node.getData());
while(parentNode != null && node == parentNode.getLchild()){
node = parentNode;
parentNode = getParentNode(root, parentNode.getData());
}
return parentNode;
}
}
/**
* Get the node node Immediate successor ( The successor node is the minimum value in the node set larger than the key value of the node to be deleted )
* a. The right subtree of this node is not empty , Its successor node is the smallest element of its right subtree
* b. The right subtree of this node is empty , Then its successor node is its ancestor node ( recursive ), And the left child of this ancestor node is also the ancestor node of this node ,
* That is to say, keep looking up for its ancestor node , Until the ancestor node after turning right ：
*/
public TreeNode<Integer> getSuccessor(TreeNode<Integer> root,TreeNode<Integer> node){
if(node == null){
return null;
}
//a. The right subtree of this node is not empty , Its successor node is the smallest element of its right subtree
if(node.getRchild() != null){
return getMinData(node.getRchild());
}else{ //b. The right subtree of this node is empty , Then its successor node is its highest ancestor node ( recursive )
TreeNode<Integer> parentNode = getParentNode(root, node.getData());
while(parentNode != null && node == parentNode.getRchild()){
node = parentNode;
parentNode = getParentNode(root, parentNode.getData());
}
return parentNode;
}
}
/**
* Delete the data field as data The node of
* Deal with it in three ways ：
* a. If the node is deleted z It's a leaf node , Then delete , Does not destroy the properties of binary search trees
* b. If node z There is only one left or right subtree , Then let z The subtree becomes z The subtree of the parent node , Instead of z The location of
* c. If the node z There is left 、 Two subtrees on the right , Then order z Immediate successor （ Or direct precursor ） replace z,
* Then delete the direct successor from the binary search tree （ Or direct precursor ）, This translates into the first or second case
* @param node The root node of the binary search tree
* @param data The data field of the node to be deleted
* @return
*/
public boolean deleteNode(TreeNode<Integer> node, Integer data){
if(node == null){ // The tree is empty.
throw new RuntimeException(" The tree is empty. ！");
}
TreeNode<Integer> delNode= searchNode(node, data); // Search for nodes to be deleted
TreeNode<Integer> parent = null;
if(delNode == null){ // If there is no keyword to delete in the tree
throw new RuntimeException(" There is no keyword to delete in the tree ！");
}else{
parent = getParentNode(node,data); // Get the immediate parent of the deleted node
//a. If the node is deleted z It's a leaf node , Then delete , Does not destroy the properties of binary search trees
if(delNode.getLchild()==null && delNode.getRchild()==null){
if(delNode==parent.getLchild()){ // The deleted node is the left child of its parent node
parent.setLchild(null);
}else{ // The deleted node is the right child of its parent node
parent.setRchild(null);
}
return true;
}
//b1. If node z There's only one left tree , Then let z The subtree becomes z The subtree of the parent node , Instead of z The location of
if(delNode.getLchild()!=null && delNode.getRchild()==null){
if(delNode==parent.getLchild()){ // The deleted node is the left child of its parent node
parent.setLchild(delNode.getLchild());
}else{ // The deleted node is the right child of its parent node
parent.setRchild(delNode.getLchild());
}
delNode.setLchild(null); // Set the left child of the deleted node to null
return true;
}
//b2. If node z There's only one right subtree , Then let z The subtree becomes z The subtree of the parent node , Instead of z The location of
if(delNode.getLchild()==null && delNode.getRchild()!=null){
if(delNode==parent.getLchild()){ // The deleted node is the left child of its parent node
parent.setLchild(delNode.getRchild());
}else{ // The deleted node is the right child of its parent node
parent.setRchild(delNode.getRchild());
}
delNode.setRchild(null); // Set the right child of the deleted node to null
return true;
}
//c. If the node z There is left 、 Two subtrees on the right , Then delete the successor node of the node , And replace the node with the successor node
if(delNode.getLchild()!=null && delNode.getRchild()!=null){
TreeNode<Integer> successorNode = getSuccessor(node,delNode); // Get the successor node of the deleted node
deleteNode(node,successorNode.getData()); // Delete the successor node of this node
delNode.setData(successorNode.getData()); // Replace the node with the successor node
return true;
}
}
return false;
}
public static void main(String args[]){
Scanner input = new Scanner(System.in);
Integer[] array = {8,3,10,1,6,14,4,7,13};
BinarySearchTree bst = new BinarySearchTree();
TreeNode<Integer> root = bst.buildBST(array);
System.out.print(" Level traversal ：");
bst.levelOrder(root);
System.out.print("\n"+" In the sequence traversal ：");
bst.inOrder(root);
System.out.println();
System.out.print(" Get the maximum ：");
System.out.println(bst.getMaxData(root).getData());
System.out.print(" Get the minimum ：");
System.out.println(bst.getMinData(root).getData());
System.out.print(" Insert a node into the binary search tree , Please enter the data field to insert the node ：");
int data = input.nextInt();
System.out.print(" Insert node "+ data +" after , The result of middle order traversal ：");
root = bst.insertNode(root, data);
bst.inOrder(root);
System.out.println("\n"+" Find elements in the binary search tree ,"+" Please enter the node value you want to find ：");
data = input.nextInt();
if(bst.searchNode(root, data) == null){
System.out.println("false");
}else{
System.out.println("true");
}
System.out.println(" Find the direct parent of a node ,"+" Please enter the node value you want to find ：");
data = input.nextInt();
System.out.print(" node "+ data +" The parent of is ：");
if(bst.getParentNode(root, data) == null){
System.out.println("null");
}else{
System.out.println(bst.getParentNode(root, data).getData());
}
System.out.println(" Delete node ,"+" Please enter the node value to be deleted ：");
data = input.nextInt();
if(bst.deleteNode(root, data)){
System.out.print(" Level traversal after deleting nodes ：");
bst.levelOrder(root);
System.out.print("\n"+" Middle order traversal after deleting nodes ：");
bst.inOrder(root);
}
}
}

  Program run results ：

 Level traversal ：8 3 10 1 6 14 4 7 13
In the sequence traversal ：1 3 4 6 7 8 10 13 14
Get the maximum ：14
Get the minimum ：1
Insert a node into the binary search tree , Please enter the data field to insert the node ：15
Insert node 15 after , The result of middle order traversal ：1 3 4 6 7 8 10 13 14 15
Find elements in the binary search tree , Please enter the node value you want to find ：
true
Find the direct parent of a node , Please enter the node value you want to find ：
node 10 The parent of is ：8
Delete node , Please enter the node value to be deleted ：
Level traversal after deleting nodes ：8 3 10 1 6 14 7 13 15
Middle order traversal after deleting nodes ：1 3 6 7 8 10 13 14 15

Reference blog ：

https://www.cnblogs.com/CherishFX/p/4625382.html