define
Binary Search Tree (Binary Search Tree), also known as Binary sort Tree, Binary Search Tree. Binary lookup trees are developed for fast lookup. However, it can not only quickly find a data, but also quickly insert and delete a data. A binary search tree requires that every node in the tree has a value less than the value of this node in the left subtree, and a value greater than the value of this node in the right subtree.
Both of these are binary search trees.
To find the
To find a node in a binary search tree, we take the root node, and if it equals the data we’re looking for, we return it. If the data you are looking for is smaller than the value of the root node, you do a recursive search in the left subtree. If the data you are looking for is larger than the value of the root node, do a recursive search in the right subtree.
Find the code implementation
public class BinarySearchTree {
private Node root;
public Node find(int data) {
Node temp = root;
while(temp ! =null) {
if (data == temp.data) {
return temp;
} else if(data > temp.data) {
temp = temp.rchild;
} else{ temp = temp.lchild; }}return null; }}public class Node {
int data;
Node lchild;
Node rchild;
public Node(int data) {
this.data = data; }}Copy the codeinsert
The operation of insert is similar to the operation of find. Starting at the root node, compare the data to be inserted in relation to the node. If the data to be inserted is larger than the data of the node, and the right subtree of the node is empty, the data is directly inserted into the location of the right subtree. If the right subtree is not empty, the data continues to traverse the right subtree. If the data to be inserted is smaller than the node’s data and the left subtree of the node is empty, the data is inserted directly into the position of the left subtree. If the left subtree is not empty, the left subtree is traversed.
Insert code implementation
public void insert(int data) {
if (root == null) {
root = new Node(data);
return;
}
Node temp = root;
while (true) {
if (data > temp.data) {
if (temp.rchild == null) {
temp.rchild = new Node(data);
return;
}
temp = temp.rchild;
} else {
if (temp.lchild == null) {
temp.lchild = new Node(data);
return; } temp = temp.lchild; }}}Copy the codedelete
Binary search tree search and insert operation is relatively simple, but the deletion operation is more complex, divided into three cases. In the first case, the node to be deleted is the leaf node. In this case, set the pointer to the node to be deleted to NULL in the parent node. Delete 28 in the figure below. In the second case, the node to be deleted has only one child (left child or right child), and we simply update the pointer in the parent node to point to the byte point of the node to be deleted. 34 in the picture below. In the third case, the node to be deleted has two children. In this case, we need to replace the smallest node in the right subtree of the node to be deleted. 15 in the figure below.
public void delete(int data) {
Node temp = root; // temp points to the node to be deleted
Node ftemp = null; // ftemp points to the parent node of the node to be deleted
while(temp ! =null&& temp.data ! = data) { ftemp = temp;if (data > temp.data) {
temp = temp.rchild;
} else{ temp = temp.lchild; }}if (temp == null) return; // The corresponding node is not found
// If found, temp is the node to delete
// The node to be deleted has two children
if(temp.lchild ! =null&& temp.rchild ! =null) {
Node minTemp = temp.rchild; // Store the smallest node of the right subtree
Node fminTemp = temp; // The parent of minTemp
// Find the smallest node in the right subtree
while(minTemp.lchild ! =null) {
fminTemp = minTemp;
minTemp = minTemp.lchild;
}
temp.data = minTemp.data; // Replace the value of the smallest node with temp
temp = minTemp; // change to delete leaf node
ftemp = fminTemp;
}
// Delete node is leaf node or has only one node
Node child; // Child node of temp
if(temp.lchild ! =null) {
child = temp.lchild;
} else if(temp.rchild ! =null) {
child = temp.rchild;
} else {
child = null;
}
if (ftemp == null) { // Delete the root node
root = child;
} else if (ftemp.lchild == temp) {
ftemp.lchild = child;
} else{ ftemp.rchild = child; }}Copy the codeBinary search tree that supports repeated data
The previous binary search tree operations are aimed at the case where there is no duplicate data. If we need to store duplicate data, when we insert data, if we encounter a node whose value is the same as the value to be inserted, we place the data to be inserted in the right subtree of that node. That is, treat the newly inserted data as if it were greater than the value of the node.
When looking for data, we do not stop looking for nodes with the same value. Instead, we continue searching in the right subtree until we reach a leaf node. In this way, all the nodes that meet the requirements can be found. Before deleting a node, you need to search for each node to be deleted and then delete the node in sequence.
Find Max and min nodes
public Node findMin(a) {
if (root == null) return null;
Node temp = root;
while(temp.lchild ! =null) {
temp = temp.lchild;
}
return temp;
}
public Node findMax(a) {
if (root == null) return null;
Node temp = root;
while(temp.rchild ! =null) {
temp = temp.rchild;
}
return temp;
}
Copy the codeTraversal of binary trees
Pre-order, mid-order, post-order traversal (recursive)
Middle order traversal binary search tree, can output ordered data sequence, time complexity is O(N), very efficient
// preorder traversal
public void preOrder(Node node) {
if(node ! =null) { System.out.println(node.data); preOrder(node.lchild); preOrder(node.rchild); }}// middle order traversal
public void inOrder(Node node) {
if(node ! =null) { inOrder(node.lchild); System.out.println(node.data); inOrder(node.rchild); }}// after the sequence traversal
public void postOrder(Node node) {
if(node ! =null) { postOrder(node.lchild); postOrder(node.rchild); System.out.println(node.data); }}Copy the codePre-order, mid-order, post-order traversal (non-recursive)
Before the order
// preorder traversal
public void preOrderTraversal(Node node) {
if (node == null) return;
Stack<Node> stack = new Stack<>();
stack.push(node);
while(! stack.isEmpty()) { node = stack.pop();if(node.rchild ! =null) {
stack.push(node.rchild);
}
if(node.lchild ! =null) { stack.push(node.lchild); } System.out.println(node.data); }}Copy the codeIn the sequence
// middle order traversal
public void inOrderTraversal(Node node) {
Stack<Node> stack = new Stack<>();
while(node ! =null| |! stack.isEmpty()) {if(node ! =null) {
stack.push(node);
node = node.lchild;
} else{ node = stack.pop(); System.out.println(node.data); node = node.rchild; }}}Copy the codeAfter the order
// after the sequence traversal
public void postOrderTraversal(Node node) {
if (node == null) return;
Stack<Node> stack1 = new Stack<>();
Stack<Node> stack2 = new Stack<>();
stack1.push(node);
while(! stack1.isEmpty()) { node = stack1.pop(); stack2.push(node);if(node.lchild ! =null) {
stack1.push(node.lchild);
}
if(node.rchild ! =null) { stack1.push(node.rchild); }}while (!stack2.isEmpty()) {
System.out.println(stack2.pop().data);
}
}
Copy the codeSequence traversal
// sequence traversal
public void levelOrder(Node node) {
if (node == null) return;
Queue<Node> queue = new LinkedList<>();
queue.offer(node);
while(! queue.isEmpty()) { node = queue.poll(); System.out.println(node.data);if(node.lchild ! =null) {
queue.offer(node.lchild);
}
if(node.rchild ! =null) { queue.offer(node.rchild); }}}Copy the code