Java implements binary search tree and implements search, insert, and delete operations on the tree (merge and delete, copy and delete)
First of all, we need to have a coding idea, roughly as follows:
1. Search: According to the data characteristics of the binary search tree, we can realize search based on the value comparison of nodes. When the search value is greater than the current node, go to the right, and vice versa!
2. Insert: We should know that all the inserted are leaf nodes, so we need to find the location of the leaf node to be inserted, and the insertion idea is consistent with the search idea.
3. Delete:
1) Merge and delete: Generally speaking, the following situations will be encountered. The deleted node has a left subtree but no right subtree. At this time, the parent node of the current node should point to the left subtree of the current node; when the deleted node has a right subtree but no left subtree, the parent node of the current node should point to the right subtree; when the deleted node has a left subtree and a right subtree, we can find the rightmost node of the left subtree of the deleted node, and then let the right or left "pointer" of this node point to the right subtree of the deleted node
2) Copy and deletion: Copy and deletion are relatively simple deletion operations and are also the most commonly used deletion operations. There are roughly three situations: when the current node has no left subtree and has a right subtree, let the root node of the current right subtree replace the deleted node; when the current node has no right subtree and has a left subtree, let the root node of the current left subtree and replace the deleted node; when the currently deleted node has both a left subtree and a right subtree, we need to find the subtree of the deleted node, and find the rightmost node in the left subtree and assign the value of this node to the deleted node, and then don't forget to let the "pointer" of the parent node pointing to the subtree is empty (in fact, it doesn't matter in Java, and there is a garbage disposal mechanism to automatically process it). You can also implement this process as a stand-alone node on the leftmost node of the right subtree of the currently deleted node.
Next, let’s add the code.
First of all, ## Binary 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){ 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; }}Implementing a binary 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 a binary tree*/ public void CreateTree(SearchBinaryTreeNode<T> node, T data) { if (root == null) { root = new SearchBinaryTreeNode<T>(); } else { if (Math.random() > 0.5) { //Create a binary tree in a random way 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); } } } } } /* * Search in the second search search tree*/ public SearchBinaryTreeNode<T> search(SearchBinaryTreeNode<T> root,T value){ SearchBinaryTreeNode<T> current=root; while((root!=null)&&(current.getData()!=value)){ //It should be noted that generics in java cannot compare sizes. In actual use, we can use common data types to replace this generic, so there will be no errors. 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; //It should be noted that generics in java cannot compare sizes. In actual use, we can use common data types to replace this generic, so that there will be no errors 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 and delete*/ public void deleteByMerging(SearchBinaryTreeNode<T> node){ SearchBinaryTreeNode<T> temp=node; if(node!=null){ //If the deleted node does not have a right subtree, use the root node of its left subtree to replace the deleted node if(node.rightChild!=null){ node=node.leftChild; }else if(node.leftChild==null){ //If the deleted node does not have a left subtree, use the leftmost node with the word count instead of the deleted node node=node.rightChild; }else{ //If the left and right subtrees of the deleted nodes have temp=node.leftChild; while(temp.rightChild!=null){ temp=temp.rightChild; //Followly find the right node of the left subtree} // Assign the right pointer of 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 and delete */ public void deleteByCoping(SearchBinaryTreeNode<T> node){ SearchBinaryTreeNode<T> pre=null; SearchBinaryTreeNode<T> temp=node; //If the deleted node does not have a right subtree, use the root node of its left subtree to replace the deleted node if(node.rightChild==null){ node=node.leftChild; }else if(node.leftChild==null){ node=node.rightChild; }else{ //If the left and right subtrees of the deleted nodes have temp=node.leftChild; pre=node; while(temp.rightChild!=null){ pre=temp; temp=temp.rightChild; //Travel to find the rightmost node of the left subtree} node.data=temp.data; //Perform the assignment operation if(pre==node){ pre.leftChild=node.leftChild; }else{ pre.rightChild=node.rightChild; } } temp=null; }}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 and delete tree.deleteByMerging(new SearchBinaryTreeNode<Integer>(8)); //Copy and delete tree.deleteByCoping(new SearchBinaryTreeNode<Integer>(6)); }}OK, that's it!
The above article Java creates a binary search tree and implements search, insertion, and deletion operation examples are all the content I share with you. I hope you can give you a reference and I hope you can support Wulin.com more.