Shulou(Shulou.com)06/01 Report--

This article will explain in detail how to achieve a binary search tree in Java. The editor thinks it is very practical, so I share it for you as a reference. I hope you can get something after reading this article.

1. Concept

a. Is a binary tree (each node has at most two child nodes)

b. For the node values of the nodes in this tree

All node values in the left subtree

< 根节点 < 右子树的所有节点值 二分搜索树中一般不考虑值相等的情况(元素不重复)JDK中的搜索树就不存在相同的值(TreeMap-key)

The biggest feature: it is also a way to judge whether it is a search tree or not.

By traversing the tree in the middle order, we can get an ascending order set 0 1 2 3 4 5 6 7 8 9.

What is the time complexity of binary search on an ordered interval? Logn continues to logN the collection / 2 / 2 = = 1.

LogN = "think of" tree

two。 Key operation

When 58 is deleted, the left and right subtrees of this node are not empty.

Hibbard Deletion 1962

Delete a node that exists in both left and right subtrees in BST

Find the precursor or successor node with 58 as the root node as the deleted new node

Precursor: the last node in a BST rooted at 58 that is less than 58-> 53

Subsequent: the first node greater than 58 in the BST with 58 as the root-> 59

When we use the successor node, we connect removeMin (root.right) first, and then connect root.left

TreeNode successor = findMin (root.right); successor.right = removeMin (root.right); successor.left = root.left;3. The complete code import java.util.NoSuchElementException; / * based on the integer * ordinary binary search tree * / public class BST {private class TreeNode {private int val; private TreeNode left; private TreeNode right; public TreeNode (int val) {this.val = val;}} private int size; private TreeNode root / * insert a new node val * @ param val * / public void add (int val) {root = add (root,val);} private TreeNode add (TreeNode root, int val) {if (root = = null) {/ / create a new node TreeNode newNode = new TreeNode (val); size++ Return newNode;} / / insert if into the left subtree (val

< root.val){ root.left = add(root.left,val); } //右子树插入 if(val >

Root.val) {root.right = add (root.right,val);} return root;} / * determine whether the current BST rooted in root contains val * @ param val * @ return * / public boolean contains (int val) {return contains (root,val) } private boolean contains (TreeNode root, int val) {if (root = = null) {return false;} if (val = = root.val) {/ / found return true;} else if (val)

< root.val){ //递归左子树查找 return contains(root.left,val); }else{ //递归右子树查找 return contains(root.right,val); } } /** * 找到最小值 * @return */ public int findMin(){ //判空 if(root == null){ //抛出一个空指针异常 throw new NoSuchElementException("root is empty! cannot find min"); } TreeNode minNode = findMin(root); return minNode.val; } private TreeNode findMin(TreeNode root) { //当此节点左子树为空，说明此节点是最小值 if(root.left == null){ return root; } //递归访问左子树 return findMin(root.left); } /** * 找到最大值 * @return */ public int findMax(){ //判空 if(root == null){ throw new NoSuchElementException("root is empty! cannot find max"); } TreeNode maxNode = findMax(root); return maxNode.val; } private TreeNode findMax(TreeNode root) { //当此节点右子树为空，说明此节点是最大值 if(root.right == null){ return root; } //递归访问右子树 return findMax(root.right); } /** * 在当前BST中删除最小值节点，返回删除的最小值 * @return */ public int removeMin(){ int min =findMin(); root = removeMin(root); return min; } private TreeNode removeMin(TreeNode root) { if(root.left == null){ TreeNode right = root.right; //找到最小值，删除节点 root = root.left = null; size--; return right; } root.left = removeMin(root.left); return root; } /** * 在当前BST中删除最大值节点，返回删除的最大值 * @return */ public int removeMax(){ int max = findMax(); root = removeMax(root); return max; } //在当前以root为根的BST中删除最小值所在的节点，返回删除后的树根 private TreeNode removeMax(TreeNode root) { if(root.right == null){ TreeNode right = root.right; //找到最大值，删除节点 root = root.right = null; size--; return right; } root.right = findMax(root.right); return root; } /** * 在当前以root为根节点的BST中删除值为val的节点 * 返回删除后的新的根节点 * @return */ public void removeValue(int value){ root = removeValue(root,value); } private TreeNode removeValue(TreeNode root, int value) { if(root == null){ throw new NoSuchElementException("root is empty! cannot find remove"); }else if(value < root.val){ root.left = removeValue(root.left,value); return root; }else if(value >

Root.val) {root.right = removeValue (root.right,value); return root;} else {/ / at this point value = = root.value if (root.left = = null) {/ / delete the minimum number TreeNode right = root.right; root = root.right = null; size-- Return right;} if (root.right = = null) {/ / maximum number of deletions TreeNode left = root.left; root = root.left = null; size--; return left } / / find the precursor or successor node of the current deleted node as the deleted new node / / when we use the successor node, connect removeMin (root.right) first, then connect root.left TreeNode successor = findMin (root.right); successor.right = removeMin (root.right); successor.left = root.left; return successor } @ Override public String toString () {StringBuilder sb = new StringBuilder (); generateBSTString (root,0,sb); return sb.toString ();} / / Visual printing shows the depth of the tree private void generateBSTString (TreeNode root, int height, StringBuilder sb) {if (root = = null) {sb.append (generateHeightString (height)). Append ("NULL\ n") Return;} sb.append (generateHeightString (height)) .append (root.val) .append ("\ n"); generateBSTString (root.left,height+1,sb); generateBSTString (root.right,height+1,sb);} private String generateHeightString (int height) {StringBuilder sb = new StringBuilder (); for (int I = 0; I < height) ITunes +) {sb.append ("- -");} return sb.toString ();}} this is the end of the article on "how to achieve a binary search tree in Java". I hope the above content can be helpful to you so that you can learn more knowledge. if you think the article is good, please share it for more people to see.

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.