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

This article introduces Java how to achieve binary search tree insertion, deletion function, the content is very detailed, interested friends can refer to, hope to be helpful to you.

What are the characteristics of Java? what are the characteristics of Java? what is the 1.Java language that represents the static object-oriented programming language? it implements the object-oriented theory and allows programmers to carry out complex programming in an elegant way of thinking. 2.Java has the characteristics of simplicity, object-oriented, distributed, security, platform independence and portability, dynamic and so on. 3. Using Java, you can write desktop applications, Web applications, distributed systems, embedded system applications, and so on.

Order traversal in the structure of binary tree public class TreeNode {int val; TreeNode left; TreeNode right; TreeNode () {} TreeNode (int val) {this.val = val;}}

Mid-order traversal: traversing from the root node, the traversal order is: left subtree-> current node-> right subtree. In mid-order traversal, for each node:

It will be traversed only if its left subtree has been traversed (or there is no left subtree).

Be sure to traverse the current node before traversing the right subtree.

The first node obtained by traversing in the middle order has no left subtree (maybe a leaf node, maybe a right subtree)

Similarly, the last node of the traversal in the middle order has no right subtree.

Code recursive implementation

List list = new ArrayList (); public void inorder_traversal (TreeNode root) {if (root = = null) {return;} if (root.left! = null) {inorder_traversal (root.left);} list.add (root); if (root.right! = null) {inorder_traversal (root.right) Definition of binary search tree

For each node, all nodes of the left subtree are smaller than it, and all nodes of the right subtree are larger than it.

Each node in the binary tree has a different value.

The result of traversal in the middle order is ascending.

These definitions determine its advantages: search efficiency is fast, because when a binary search tree looks for a value, it can be searched by binary search, and the average time complexity is log2 (n). N is the layer tree of the binary tree.

The following figure is a standard binary search tree. The right subtree is larger than the root node, and the left subtree is smaller than the root node.

Find Node

Given a value, use a loop to search in the binary search tree until the node is found

Start from the root node and cycle through the comparison

If the given value is greater than the current node, find the right subtree, and if it is less than that, find the left subtree. If the value is equal, you will find the node.

The code is implemented as follows

Public TreeNode search (TreeNode root, int val) {/ / node is not empty and is not equal to the specific value while (root! = null & & root.val! = val) {if (root.val > val) {root = root.left;} else {root = root.right;}} return root;} add node

Let the node to be added is b, and the binary search tree is added to it as a leaf node, because the increase of leaf nodes is relatively simple.

Similar to the search process, start from the root node and cycle through to find a location suitable for the new node

The b value is larger (smaller) than the current node, and the right (left) subtree of the current node is empty. Insert b into the right (left) subtree of the current node.

If the subtree of the current node is not empty, continue to look down

Use a constantly updated pre node as the parent of b with the search process, and the pre node adds b

The binary tree that may be inserted into the node is an empty tree. Create a new binary tree.

If there is already a value equal to b in the binary search tree, you do not need to add it

Public TreeNode insertInto (TreeNode root, int val) {if (root = = null) {/ / if the tree is empty return new TreeNode (val);} / / A temporary node points to the root node and is used to return the value TreeNode tmp = root; TreeNode pre = root While (root! = null & & root.val! = val) {/ / Save parent node pre = root; if (val > root.val) {root = root.right;} else {root = root.left }} / / add if through parent node (val > pre.val) {pre.right = new TreeNode (val);} else {pre.left = new TreeNode (val);} return tmp;} delete node

The deletion process is complicated. First, the node to be deleted in the binary search tree is a _ a.

An is the leaf node

A has a child node

A has two child nodes to delete the leaf node

The process is similar to the search node. When an is found, it is deleted through its parent node, and the deletion of the leaf node does not affect the properties of the tree.

A node with one child node

To delete an and keep the child node of a, let its parent node connect its child node, because the relationship between the child node of an and the parent node of a = the parent node relationship of an and a does not change the nature of the tree

The definition of binary search tree determines that for each node, if it is larger (less than) its parent node, then its child node is larger (less than) its parent node.

The process is like this picture.

Delete a node with two child nodes

By swapping nodes, we can exchange a with a node with only one child node, and the operation of deleting a becomes the second case above.

We know that the results of the middle order traversal binary search tree are in ascending order. If we want to exchange, we must find the nodes where the middle order traverses on the left and right sides of a (because the value exchange also meets the definition of the binary search tree).

The last (front) node of the middle order traversal is the first (last) node in the right (left) subtree, and they all have only one child node.

The process is similar to the following figure (the value of an is exchanged with the latter node of the traversal in the middle order, and the node is deleted)

Code implementation

Public TreeNode deleteNode (TreeNode root, int key) {TreeNode tmp = root; TreeNode pre = root; / / find the node to delete while (root! = null & & root.val! = key) {pre = root; if (key > root.val) {root = root.right;} else {root = root.left }} / / No matching node value if (root = = null) {return tmp } / / if there is only one child node or no child node, if (root.left = = null | | root.right = = null) {if (root.left = = null) {/ / the root node to be deleted, return its child node if (root = = tmp) {return root.right } / / use the parent node to connect the child node to delete the current node if (pre.left = = root) {pre.left = root.right;} else {pre.right = root.right }} else {if (root = = tmp) {return root.left;} if (pre.left = = root) {pre.left = root.left;} else {pre.right = root.left }} return tmp;} / / the first way / / find the last node of the middle order traversal, that is, the first node of the right subtree for middle order traversal, and the leftmost node of the right subtree pre = root; TreeNode rootRight = root.right Exchange the values of while (rootRight.left! = null) {pre = rootRight; rootRight = rootRight.left;} / / node int tmpVal = rootRight.val; rootRight.val = root.val; root.val = tmpVal / / the first node in order traversal certainly has no left subtree, but there may be a right subtree. Connect the right subtree to the parent node (equivalent to deleting a node with one child node) if (pre.left = = rootRight) {pre.left = rootRight.right;} else {pre.right = rootRight.right } / / the second way / / finds the previous node of the middle order traversal, that is, the last node of the left subtree traversing the middle order, and the rightmost node of the left subtree / / pre = root;// TreeNode rootLeft = root.left;// while (rootLeft.right! = null) {/ / pre = rootLeft;// rootLeft = rootLeft.right / /} / int tmpVal = rootLeft.val;// rootLeft.val = root.val;// root.val = tmpVal / / the last node traversed in the order certainly does not have a right subtree, but there may be a left subtree. Connect the left subtree to the parent node (equivalent to deleting a node with one child node) / / if (pre.left = = rootLeft) {/ / pre.left = rootLeft.left;//} else {/ / pre.right = rootLeft.left / /} return tmp;} about Java how to achieve binary search tree insert, delete function to share here, I hope the above content can be of some help to you, can learn more knowledge. If you think the article is good, you can 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.