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

What are the methods of traversing the binary tree in Java, many novices are not very clear about this, in order to help you solve this problem, the following editor will explain for you in detail, people with this need can come to learn, I hope you can get something.

1. Basic introduction

There are a variety of tree structures, but the most commonly used is binary tree. Each node in the binary tree has at most two child nodes, which are the left child node and the right child node. Note: it is not required to have two child nodes, either the left child node or the right child node.

two。 The storage of binary tree is 2.1. Chain storage method

Each node has at least three fields, one of which stores data, and the other two are pointers to the left and right child nodes. This kind of storage method is more commonly used, and most of the binary tree code is implemented through this structure.

2.2. Array storage method

We store the root node in the location of subscript iNode 1, its left child node in the location of subscript 2Secreti, and the right child node in the location of subscript 2*i+1. And so on, the left and right child nodes of B node and C node are stored according to this law, as shown in the following figure.

To sum up, if node X stores the location in the array with the subscript I, then the location with the subscript 2Secreti stores its left child node, and the location with the subscript 2*i+1 stores its right child node. Conversely, the location of iUniver 2 stores its parent node. In general, for ease of calculation, the root node is stored in the location with the subscript 1.

As you can see from the above, for a general tree, using an array to store a tree wastes more storage space. But for full binary trees or full binary trees mentioned below, array storage is the most memory-saving way. Because when the array is stored, there is no need to store additional pointers to the left and right child nodes.

3. Traversal of binary tree

The traversal of the binary tree is to print out all the nodes in the binary tree. There are three classical methods, pre-order traversal, mid-order traversal and post-order traversal, and can also be traversed by layer (personal understanding of layer-by-layer traversal is actually traversed according to the breadth-first traversal method of the graph).

The front, middle and back are distinguished according to the order in which the node is printed: the preorder is to print the node itself first, then to print its left subtree, and finally to print its right subtree; the middle order is to print the node's left subtree first, then print the node itself, and finally print the right subtree, that is, put the node in the middle position output; the latter order is to print the node's left subtree first, then print the node's right subtree, and finally print the node itself. As shown in the following figure

Traversing by layer is similar to the breadth-first traversal of the graph, first printing the nodes of the first layer, then printing the nodes of the second layer in turn, and so on.

3.1. Code implementation

In fact, the pre-order, middle-order and post-order traversal of a binary tree is a recursive process. For example, preorder traversal is actually printing the root node first, then recursively traversing the left subtree, and finally recursively traversing the right subtree. Recursively traversing the left and right subtrees is actually the same as traversing the root node. Let's first write the recursive formula for traversing these three:

Recursive formula for preorder traversal:

PreOrder (r) = print r-> preOrder (r-> left)-> preOrder (r-> right)

The recursive formula of traversal in the middle order:

InOrder (r) = inOrder (r-> left)-> print-r-muri-> inOrder (r-> right)

The recursive formula of post-order traversal:

PostOrder (r) = postOrder (r-> left)-> postOrder (r-> right)-> print r

Then convert the recursive formula to the code as follows:

/ * *

* preorder traversal

, /

Public void preOrder (Node tree) {

If (tree = = null) {

Return

}

System.out.print (tree.data + "")

PreOrder (tree.left)

PreOrder (tree.right)

}

/ * *

* traversal in the middle order

, /

Public void inOrder (Node tree) {

If (tree = = null) {

Return

}

InOrder (tree.left)

System.out.print (tree.data + "")

InOrder (tree.right)

}

/ * *

* traversal in post-order

, /

Public void postOrder (Node tree) {

If (tree = = null) {

Return

}

PostOrder (tree.left)

PostOrder (tree.right)

System.out.print (tree.data + "")

}

★

The key to recursive code is to write recursive formulas. The key to the recursive formula is that problem A can be divided into two problems B and C. Suppose you want to solve problem A, then assume that problems B and C have been solved. So in advance that B and C have been solved, let's see how to use B and C to solve A. Don't simulate the computer one layer at a time, or you'll find that you don't even know where you are.

"

The following is the code for traversing by layer, which requires queuing and dequeuing operations. First put the root node into the queue, then cycle to get the node from the queue (dequeue), and then queue the left and right child nodes of the node. The order of leaving the team is the result of hierarchical traversal.

/ * *

* hierarchical traversal

, /

Public void BFSOrder (Node tree) {

If (tree = = null) {

Return

}

Queue queue = new LinkedList ()

Node temp = null

Queue.offer (tree)

While (! queue.isEmpty ()) {

Temp = queue.poll ()

System.out.print (temp.data + "")

If (temp.left! = null) {

Queue.offer (temp.left)

}

If (temp.right! = null) {

Queue.offer (temp.right)

}

}

}

★

The complete code can be found in the github warehouse https://github.com/DawnGuoDev/algos, which will mainly contain handwritten implementations of common data structures and their basic operations (Java), as well as implementations of classic examples of common algorithm ideas (Java). The repository will be updated until the program pot finds a job, and the knowledge or implementation of data structures and algorithms learned in between will be commit, so hurry up and star.

"3.2. Time complexity

The number of times in the traversal process is the number of times required to visit all nodes, and each node is visited twice at most, so the time complexity of traversal is proportional to the number of nodes n, that is, the time complexity of traversal is O (n).

4. Special binary tree 4.1. Full binary tree

Full binary tree is not only a special binary tree, but also a special case of complete binary tree. As shown in the tree numbered 2 above, the leaf nodes are all at the bottom, with the exception of the leaf node, each node has two left and right child nodes.

4.2. Complete binary tree

Complete binary tree is also a special kind of binary tree. As shown in the tree numbered 3 above, the leaf nodes are in the bottom two layers, the leaf nodes in the last layer are arranged on the left, and all the other layers have the largest number of nodes except the last layer.

The characteristics of the complete binary tree make it possible to store data well using arrays. This is also why the complete binary tree requires the leaf nodes of the last layer to be arranged to the left.

4.2.1. Storage of complete binary tree

Chain storage

It's the way mentioned above.

Array storage

When a full binary tree uses array storage, as shown in the following figure. We found that using arrays to store complete binary trees is a very memory-saving way. This is why the complete binary tree is regarded as a special tree, and it is also the reason why the child nodes of the last layer must be left.

When talking about heap or heap sorting, heap is also a kind of complete binary tree, and the most commonly used storage method is array.

Is it helpful for you to read the above content? If you want to know more about the relevant knowledge or read more related articles, please follow the industry information channel, thank you for your support.

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.