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

This article mainly introduces the example analysis of the data insertion algorithm in the java binary tree, which is very detailed and has a certain reference value. Interested friends must read it!

Example:

Question 701 of leetcode

Binary tree insert data

Title:

Given the root node of the binary search tree (BST) and the value to insert into the tree, insert the value into the binary search tree. Returns the root node of the binary search tree after insertion. The input data ensures that the new value is different from any node value in the original binary search tree.

There are three ways to traverse a binary tree

Preorder traversal: the left and right order of the root

Mid-order traversal: the order of the left root and the right

Post-order traversal: the order of the left and right roots

What is the principle / idea of inserting data into binary tree?

The number on the left side of the binary tree is smaller than that on the right side, so we compare the size of the data to be inserted with the value of the root node. If the inserted data is larger than the root node, then the root node is transferred to the node on the right. Repeat the above operation at this time to complete the insertion.

Let's read the TreeNode code snippet:

Class TreeNode {int val; TreeNode left; TreeNode right; TreeNode () {} TreeNode (int val) {this.val = val;} TreeNode (int val, TreeNode left, TreeNode right) {this.val = val; this.left = left; this.right = right;}}

Obviously, binary trees are linked through left,right, which is very similar to ListNode's next, except that binary trees are two-way links, while linked lists are one-way. So we need to get the parent node and use the parent node's left or right to link the number of inserts.

So how do we get the node that can insert the data correctly?

1. We can get the last node that is not empty by moving the node in a loop.

/ / define a parent binary tree to record the node TreeNode parent = root,cur=root; while (curvilinear null) {/ / if p is empty, compare it with val to move the node parent = cur / / record the last node for the final link cur = cur.valval) {/ / if the parent's val is greater than the input val, insert it on the left parent.left = new TreeNode (val);} else {/ / otherwise insert on the right parent.right = new TreeNode (val) } the whole code if (root = = null) {return new TreeNode (val);} / / defines a node used by the parent binary tree to record the previous operation TreeNode parent = root,cur=root; while) {/ / if p is empty, compare it with val to move the node parent = cur / / record the last node for the final link cur = cur.valval) {/ / if the parent's val is greater than the input val, insert parent.left = new TreeNode (val) on the left;} else {/ / otherwise insert parent.right = new TreeNode (val) on the right;} return root

Of course, because the movement of the node repeats the same operation all the time, we can use a simpler recursive implementation.

Public TreeNode insertIntoBST (TreeNode root, int val) {if (root = = null) {return new TreeNode (val);} if (root.valval) {parent.left = new TreeNode (val);} else {parent.right = new TreeNode (val);} break }} return root Solution 3: loop traversal, / * * @ param root * @ param val * @ return * * solution idea: let's first find the parent node that can be inserted through a loop * then we compare the value with the value of the parent node, and if the value is less than the parent node, we insert it on the left side of the parent node * / public TreeNode insertBST3 (TreeNode root,int val) {if (root = = null) {return new TreeNode (val) } / / define a parent binary tree to record the node of the previous operation TreeNode parent = root,p=root; while (paired binary null) {/ / if p is empty, compare it with val to move the node parent = p / / record the last node for the final link p = p.valval) {/ / if the parent's val is greater than the input val, insert it on the left parent.left = new TreeNode (val);} else {/ / otherwise insert on the right parent.right = new TreeNode (val);} return root }} above are all the contents of the article "sample Analysis of data insertion algorithms in java binary Tree". Thank you for reading! Hope to share the content to help you, more related knowledge, welcome to follow the industry information channel!

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.