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

This article mainly shows you the "java collection of TreeMap source code example analysis", the content is easy to understand, well-organized, hope to help you solve your doubts, the following let Xiaobian lead you to study and learn "java collection of TreeMap source code example analysis" this article.

Traversal of binary tree

We know that the traversal of binary search tree includes pre-order traversal, mid-order traversal and post-order traversal.

(1) preorder traversal, first traversing me, then traversing my left child node, and finally traversing my right child node

(2) traversal in the middle order, first traversing my left child node, then traversing me, and finally traversing my right child node

(3) traversal in post-order, first traversing my left child node, then traversing my right child node, and finally traversing me

The front, middle and back here are based on the order of "I". I am traversing in front of me, traversing in middle, and traversing in post.

Let's look at how the classic mid-order traversal is implemented:

Public class TreeMapTest {public static void main (String [] args) {/ / build a 10-element tree TreeNode node = new TreeNode (1, null) .insert (2) .insert (6) .insert (3) .insert (5) .insert (9) .insert (7) .insert (8) .insert (4) .insert (10) / / traversal in the middle order, printing results in the order of 1 to 10 node.root (). InOrderTraverse ();}} / * tree node, assuming that there is no duplicate element * @ param * / class TreeNode {T value; TreeNode parent; TreeNode left, right; public TreeNode (T value, TreeNode parent) {this.value = value; this.parent = parent } / * get root node * / TreeNode root () {TreeNode cur = this; while (cur.parent! = null) {cur = cur.parent;} return cur;} / * Central order traversal * / void inOrderTraverse () {if (this.left! = null) this.left.inOrderTraverse () System.out.println (this.value); if (this.right! = null) this.right.inOrderTraverse (); classical binary tree insertion method * / TreeNode insert (T value) {/ / find the root element TreeNode cur = root () first; TreeNode p; int dir / / find the location where the element should be inserted do {p = cur; if ((dir=value.compareTo (p.value)) < 0) {cur = cur.left;} else {cur = cur.right;}} while (cur! = null) / / put the element in the location found if (dir < 0) {p.left = new TreeNode (value, p); return p.left;} else {p.right = new TreeNode (value, p); return p.rightt;}} traversal of TreeMap

From the traversal of the binary tree above, we can clearly see that it is implemented recursively, but recursion takes up extra space, and the variables applied in the method will not be destroyed until the whole thread stack is freed. So it's very dangerous when there are a lot of elements.

(in the above example, no additional space is requested, and if a variable is declared, it can be understood that the variable will not be destroyed until the method is complete)

So, is there any way not to recurse?

Let's take a look at the implementation in java:

@ Overridepublic void forEach (BiConsumer

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.