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

This article introduces the relevant knowledge of "how to achieve binary search tree in Java". In the operation of actual cases, many people will encounter such a dilemma, so let the editor lead you to learn how to deal with these situations. I hope you can read it carefully and be able to achieve something!

The definition of binary search tree

It's a binary tree.

The value of all nodes on the left subtree of any node must be less than the value of that node.

The value of all nodes on the right subtree of any node must be greater than the value of that node.

Features: the middle order traversal results of the binary search tree are ordered (ascending order)!

Implement a binary search tree

To realize the binary search tree, insert, delete and find will be realized.

The nodes of the binary search tree cannot be modified. If modified, it may lead to errors in the search tree.

Definition classes of binary search trees

The Node Class of binary search Tree-class Node

Attributes of a binary search tree: to find a binary search tree, you only need to know the root node of the tree.

Search for the root node} binary search tree of public class BST {static class Node {private int key; private Node left; private Node right; public Node (int key) {this.key = key;}} private Node root;//BST

The idea of finding a binary search tree:

① if the value you are looking for is equal to the value of the current node, then you will find the

② if the value you are looking for is less than the value of the current node, then go to the left subtree of the current node

③ if the value you are looking for is greater than the value of the current node, then go to the right subtree of the current node

In the end, if it is empty and not found, it means that the key does not exist.

/ * find whether there is a node * * idea: according to the characteristics of the binary sort tree: * ① if the value you are looking for is less than the value of the current node, then go to the left subtree of the current node * ② if the value you are looking for is greater than the value of the current node, then Go to the right subtree of the current node * * @ param key with the found key * @ return boolean whether there is * / public boolean find (int key) {Node cur = root While (cur! = null) {if (key)

< root.key) { cur = cur.left; } else if (key >

Root.key) {cur = cur.right;} else {return true;}} return false;} binary search tree insertion

The idea of inserting binary search tree:

The idea is the same as the search, except that what we are going to do this time is to insert, so we also need a parent node to record the parents of the current node, namely:

① cannot be inserted if the value to be inserted is equal to the value of the current node (no duplicate key)

② if the value to be inserted is less than the value of the current node, then go to the left subtree of the current node

③ if the value to be inserted is greater than the value of the current node, then go to the right subtree of the current node

Finally, if it is empty, it means that there is no duplicate key. Just insert it into the back of the parent node, which is the appropriate position. To insert it to the left or right, you need to compare the key of the node to be inserted with the key of parent.

/ * insert a node into the binary tree * * the idea is as follows: * * @ param key the node to be inserted * / public void insert (int key) {if (root = = null) {/ / if the tree is empty, insert root = new Node (key) directly; return;} Node cur = root; Node parent = null / / parent is the parent node of cur while (true) {if (cur = = null) {/ / when a suitable location is found during traversal, the pointer is inserted (no duplicate node) if (parent.key)

< key) { parent.right = new Node(key); } else { parent.left = new Node(key); } return; } if (key < cur.key) { parent = cur; cur = cur.left; } else if (key >

Cur.key) {parent = cur; cur = cur.right;} else {throw new RuntimeException ("insert failed, key already exists");} deletion of binary search tree

Delete idea of binary search tree: (see notes for detailed ideas)

First, you need to find out if the key node exists, delete it if it does, and delete the error if it doesn't exist.

"for, if it exists, there are three cases:"

The node to be deleted by ①, no left child

Ⅰ: the node to be deleted is the root node: root = delete.right

Ⅱ: the node to be deleted is the left child of its parent node: parent.left = delete.right

Ⅲ: the node to be deleted is the right child of its parent node: parent.right = delete.right

The node to be deleted by ②, no right child

Ⅰ: the node to be deleted is the root node: root = delete.left

Ⅱ: the node to be deleted is the left child of its parent node: parent.left = delete.left

Ⅲ: the node to be deleted is the right child of its parent node: parent.right = delete.left

The node to be deleted by ③ includes both left and right children:

At this point, we need to find the first node in the whole binary tree that is larger than the node to be deleted, then replace their values, and finally, delete the found node.

Ⅰ: the parent node of the node found is the node to be deleted: delete.key = find.key; findParent.right = find.right

Ⅱ: the parent node of the node found is not the node to be deleted: delete.key = find.key; findParent.left = find.right

The idea of deleting a node in the tree * * is as follows: * * @ param key the node to be deleted * / public void remove (int key) {if (root = = null) {throw new RuntimeException ("empty tree, deletion error!") ;} Node cur = root; Node parent = null; / / find out whether the location of the key node while (cur! = null) {if (key)

< cur.key) { parent = cur; cur = cur.left; } else if (key >

Cur.key) {parent = cur; cur = cur.right;} else {break;}} if (cur = = null) {throw new RuntimeException ("key not found, input key is illegal") } / / cur is the node to be deleted / / parent is the parent of the node to be deleted / case 1: if the node to be deleted has no left child * where * the node to be deleted has the right child * the node to be deleted by ② has no right child * the node to be deleted has no right child * The two cases can be combined * / if (cur.left = = null) {if (cur = = root) {/ / ① if the root node root = cur.right } else if (cur = = parent.left) {/ / ② if you want to delete the left child of its parent node parent.left = cur.right;} else {/ / ③ if the node you want to delete is the right child of its parent node parent.right = cur.right }} / * * case 2: if the node to be deleted has no right child * * where: there must be a left child in the node to be deleted * / else if (cur.right = = null) {/ / ① if you want to delete the root node if (cur) = = root) {root = cur.left } else if (cur = = parent.left) {/ / ② if you want to delete the left child of its parent node parent.left = cur.left;} else {/ / ③ if the node you want to delete is the right child of its parent node parent.right = cur.left }} / * case 3: if the node to be deleted has both left and right children * * because it is a sorted binary tree, to find the first node of the whole binary tree that is larger than that node, you only need to take a step to the right. Then go all the way to the far left and you can find it * so: * ① first take a step to the right * ② keeps going left * ③ finds the first node larger than the node to be deleted and sets the value of the node Replace to the node to be deleted * the node found by ④ deletion * ⑤ has been deleted * * / else {Node nextParent = cur / / define the parent node. Initialization is the node to be deleted Node next = cur.right; / / define next as the node to which you are currently going. The ultimate goal is to find the first node that is larger than the node to be deleted, while (next.left! = null) {nextParent = next; next = next.left. } cur.key = next.key; / / after finding, the replacement if of the completed value (nextParent = = cur) {/ / the parent node is the node to be deleted, so the node found is the right child of the parent node (because next has only taken one step at this time) nextParent.right = next.right } else {/ / at this time, the parent node is not the node to be deleted, that is, next did go left and came to the end. NextParent.left = next.right;} "how to realize the binary search tree in Java" is introduced here. Thank you for your reading. If you want to know more about the industry, you can follow the website, the editor will output more high-quality practical articles for you!

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.