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

This article mainly introduces Java how to achieve binary tree and traversal, has a certain reference value, interested friends can refer to, I hope you can learn a lot after reading this article, the following let the editor take you to understand it.

What is a binary tree?

It is simply understood that for a node, there is at most one superior node and the data structure of at most two subordinate nodes.

Because many sorting algorithms are based on binary tree, and multi-tree is also extended by binary tree, it is very important to build and traverse binary tree.

Binary tree building

The general situation is to give you a string that requires you to build a tree in the way of previous order, middle order, and post-order. At this point, we need to first understand three concepts:

Preorder traversal

Mid-order traversal

Post-order traversal

Let's take a look at the structure of a binary tree:

0

1 2

3 4 5 6

0 is the root node of the entire binary tree, 1 is the left subtree of 0, and 2 is the right subtree of 0. With this knowledge, we can understand that the preorder traversal is where the root is, and the preorder traversal is the root in front, so it is the traversal of the right subtree of the left subtree; the middle order traversal is the root in the middle, so it is the traversal of the right subtree of the left subtree; post-order traversal is the traversal of the root at the end, so it is the traversal of the right subtree of the left subtree.

There are three ways to traverse, and the corresponding tree building methods are known middle order and pre-order tree, known middle order and post-order tree, known pre-order and post-order tree.

If we just want to build a binary balanced tree, we can simply use some kind of sequence to build the tree. Using pseudo-code to represent these three traversal methods is

1. Build a tree by preorder traversal

New Tree (root node); buildTree (left subtree); buildTree (right subtree)

two。 Build a tree by traversing in the middle order

BuildTree (left subtree); new Tree (root node); buildTree (right subtree)

3. The way of post-order traversal is built.

BuildTree (left subtree); buildTree (right subtree); new Tree (root node); preorder building tree

We now take sequence 1, 2, 3, 4, 5, 6, 7, 8, 9 as an example. if it is a preorder tree, then the structure of the binary tree should be:

The implementation is also relatively simple.

Package com.chaojilaji.book.tree;import com.chaojilaji.auto.autocode.utils.Json;public class Handle {/ * pre-built tree * * @ param input * @ param index * @ return * / public static Tree buildTreePrologue (int [] input, int index) {/ / TODO: on 2022-1-12, the root node is the current index node Tree tree = new Tree () Tree.setValue (input [index]); / / TODO: the two nodes around 2022-1-12 are 2*index-1 and 2*index+1 int [] children = new int [] {2*index+1, 2index + 2}; if (children [0])

< input.length) { tree.setLeftChild(buildTreePrologue(input, children[0])); } if (children[1] < input.length) { tree.setRightChild(buildTreePrologue(input, children[1])); } return tree; } public static void demo() { int[] a = new int[]{1, 2, 3, 4, 5, 6, 7, 8, 9}; Tree tree = buildTreePrologue(a, 0); System.out.println(Json.toJson(tree)); } public static void main(String[] args) { demo(); }} 执行结果如下： { "value": 1, "left_child": { "value": 2, "left_child": { "value": 4, "left_child": { "value": 8, "left_child": null, "right_child": null }, "right_child": { "value": 9, "left_child": null, "right_child": null } }, "right_child": { "value": 5, "left_child": null, "right_child": null } }, "right_child": { "value": 3, "left_child": { "value": 6, "left_child": null, "right_child": null }, "right_child": { "value": 7, "left_child": null, "right_child": null } }}中序建树 以 1，2，3，4，5，6，7序列为例，如果是中序建树的方式，那么二叉树的结构应该为

The code is as follows:

Package com.chaojilaji.book.tree;import com.chaojilaji.auto.autocode.utils.Json;import com.chaojilaji.auto.autocode.utils.MathUtils;import java.util.LinkedList;import java.util.Objects;import java.util.Queue Public class Handle {/ * Central sequence Tree Building * @ param input * @ param height * @ param maxHeight * @ return * / public static Tree buildTree2 (Queue input, int height, int maxHeight) {/ / TODO: on 2022-1-12, the root node is the current index node Tree tree = new Tree () If (height < maxHeight) {tree.setLeftChild (buildTree2 (input, height + 1, maxHeight));} if (! input.isEmpty ()) {tree.setValue (input.poll ());} if (height < maxHeight) {tree.setRightChild (buildTree2 (input, height + 1, maxHeight);} return tree } public static void demo () {int [] a = new int [] {1, 2, 3, 4, 5, 6, 7}; Queue queue = new LinkedList (); for (int I = 0; I < a. Resume +) {queue.add (a [I]);} Integer maxCeng = new Double (Math.ceil (MathUtils.getLogAN (2, a.length + 1)). IntValue () System.out.println (Json.toJson (buildTree2 (queue, 1, maxCeng));} public static void main (String [] args) {demo ();}}

Compared with the pre-order tree, the binary tree is built in an extended way, and the middle-order tree can not control the index very well, so a queue is used to store the whole sequence. At the same time, it is necessary to calculate the current number of nodes to build a binary balanced tree. what is the minimum depth? Then, according to the pseudo code given earlier, the value is assigned and called recursively in the way that the left root is right.

The result of the operation is as follows:

{"value": 4, "left_child": {"value": 2, "left_child": {"value": 1, "left_child": null, "right_child": null}, "right_child": {"value": 3, "left_child": null "right_child": null}}, "right_child": {"value": 6, "left_child": {"value": 5, "left_child": null, "right_child": null}, "right_child": {"value": 7 "left_child": null, "right_child": null}}

With the traversal of the middle order, in fact, the traversal of the post order is very simple. Taking the sequence 1, 2, 3, 4, 4, 5, 6, 7 as an example, the achievement should be

The code is as follows:

Package com.chaojilaji.book.tree;import com.chaojilaji.auto.autocode.utils.Json;import com.chaojilaji.auto.autocode.utils.MathUtils;import java.util.LinkedList;import java.util.Objects;import java.util.Queue Public class Handle {/ * return * / public static Tree buildTree3 (Queue input, int height, int maxHeight) {/ / TODO: the root node on 2022-1-12 is the current index node Tree tree = new Tree (); if (height < maxHeight) {tree.setLeftChild (buildTree3 (input, height + 1, maxHeight)) } if (height < maxHeight) {tree.setRightChild (buildTree3 (input, height + 1, maxHeight));} if (! input.isEmpty ()) {tree.setValue (input.poll ();} return tree;} public static void demo () {int [] a = new int [] {1,2,3,4,5,6,7} Queue queue = new LinkedList (); for (int I = 0; I < a.stories; iDepression +) {queue.add (a [I]);} Integer maxCeng = new Double (Math.ceil (MathUtils.getLogAN (2, a.length + 1)). IntValue () System.out.println (Json.toJson (buildTree3 (queue, 1, maxCeng));} public static void main (String [] args) {demo ();}}

By analyzing the code of the three tree-building methods, you can find that, in essence, the root assignment code is different from the location of calling the left and right subtree building functions, so these three different algorithms have already been used.

The essential difference of the three traversal methods corresponding to the three tree-building methods is that the placement of the print value statement is different from that of calling the left and right subtree print value function. If we follow the same example, we can easily get the code for traversing before, in, and after the binary tree. Well, please try it yourself first.

Traversal of binary tree

According to the experience of building trees, we know that we only need to write one traversal method, then there are the other two traversal methods. The difference is simply to change the position of the print statement.

For preorder traversal, write as follows:

Public static void print1 (Tree tree) {if (Objects.isNull (tree)) return; if (Objects.nonNull (tree.getValue ()) {System.out.print (tree.getValue ());} if (Objects.nonNull (tree.getLeftChild () {print1 (tree.getLeftChild ());} if (Objects.nonNull (tree.getRightChild () {print1 (tree.getRightChild ());}}

So let's do an experiment. First, we construct a balanced binary tree by traversing the preorder according to the sequence 1, 2, 3, 4, 4, 5, 6, 7, and then print out the order of traversal in the preorder. The complete code is as follows:

Package com.chaojilaji.book.tree;import com.chaojilaji.auto.autocode.utils.Json;import com.chaojilaji.auto.autocode.utils.MathUtils;import java.util.LinkedList;import java.util.Objects;import java.util.Queue Public class Handle {/ * pre-built tree * * @ param input * @ param index * @ return * / public static Tree buildTreePrologue (int [] input, int index) {/ / TODO: on 2022-1-12, the root node is the current index node Tree tree = new Tree (); tree.setValue (input [index]) / / TODO: the two nodes around 2022-1-12 are 2*index-1 and 2*index+1 int [] children = new int [] {2*index+1, 2indexes + 2}; if (children [0] < input.length) {tree.setLeftChild (buildTreePrologue (input, children [0])) } if (children [1] < input.length) {tree.setRightChild (buildTreePrologue (input, children [1]));} return tree } / * Central sequence tree building * * @ param input * @ param height * @ param maxHeight * @ return * / public static Tree buildTree2 (Queue input, int height, int maxHeight) {/ / TODO: on 2022-1-12, the root node is the current index node Tree tree = new Tree () If (height < maxHeight) {tree.setLeftChild (buildTree2 (input, height + 1, maxHeight));} if (! input.isEmpty ()) {tree.setValue (input.poll ());} if (height < maxHeight) {tree.setRightChild (buildTree2 (input, height + 1, maxHeight);} return tree } / * @ return * / public static Tree buildTree3 (Queue input, int height, int maxHeight) {/ / TODO: the root node on 2022-1-12 is the current index node Tree tree = new Tree (); if (height < maxHeight) {tree.setLeftChild (input, height + 1, maxHeight)) } if (height < maxHeight) {tree.setRightChild (buildTree3 (input, height + 1, maxHeight));} if (! input.isEmpty ()) {tree.setValue (input.poll ());} return tree;} public static void print1 (Tree tree) {if (Objects.isNull (tree)) return If (Objects.nonNull (tree.getValue () {System.out.print (tree.getValue ());} if (Objects.nonNull (tree.getLeftChild () {print1 (tree.getLeftChild ());} if (Objects.nonNull (tree.getRightChild () {print1 (tree.getRightChild ()) } public static void print2 (Tree tree) {if (Objects.isNull (tree)) return; if (Objects.nonNull (tree.getLeftChild () {print2 (tree.getLeftChild ());} if (Objects.nonNull (tree.getValue () {System.out.print (tree.getValue ()) } if (Objects.nonNull (tree.getRightChild () {print2 (tree.getRightChild ());}} public static void print3 (Tree tree) {if (Objects.isNull (tree)) return; if (Objects.nonNull (tree.getLeftChild () {print3 (tree.getLeftChild ()) } if (Objects.nonNull (tree.getRightChild () {print3 (tree.getRightChild ());} if (Objects.nonNull (tree.getValue () {System.out.print (tree.getValue ());}} public static void demoPrint () {int [] a = new int [] {1,2,3,4,5,6,7} Tree tree = buildTreePrologue (a, 0); print1 (tree); System.out.println (); print2 (tree); System.out.println (); print3 (tree);} public static void main (String [] args) {demoPrint ();}}

The final results are as follows:

Thank you for reading this article carefully. I hope the article "how to achieve binary Tree and traversal of Java" shared by the editor will be helpful to everyone. At the same time, I also hope that you will support and pay attention to the industry information channel. More related knowledge is waiting for you to learn!

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.