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

This article mainly explains "the storage structure of java tree and the traversal implementation of binary tree". Interested friends may wish to have a look. The method introduced in this paper is simple, fast and practical. Let the editor take you to learn the storage structure of the java tree and the traversal implementation of the binary tree.

Storage structure of trees

The tree defined in the data structure is similar to the following figure:

As we said earlier, computers can only store data sequentially or chained, so structures such as trees cannot be stored directly, so they should be converted to sequential or chained storage. There are three main ways:

Parental representation

This method is based on an array and on the basis that each node of the tree (except the root node) has one and only one parent node. The practice is to add a domain to the location of its parent node when storing each node. For example, the above figure is stored in an array according to the parent representation, and the structure is like this:

In practice, from top to bottom, the sequence traverses a tree and assigns a value to the corresponding domain. This storage method can quickly obtain the location of the parent node of any node, but on the contrary, it needs to traverse to get the child node of a node.

But the above problems can be solved by adding a field, a firstChild field can be added to represent the leftmost child node of a node. for example, for the above tree, the firstChild of An is BMagie B and the firstChild of D. In this way, we can get the first child node of any node, and all the child nodes are continuous, so we can easily get all the child nodes.

This leads us to wonder whether we can get any relationship we want by adding domains. For example, the location of the sibling node can be stored. Yes, this is very flexible, but we should also pay attention to the well-designed, too large data units, will take up a lot of memory space, this is a matter of opinion and wisdom.

Child representation

This way is to create multiple pointer domains that point to the addresses of all its child nodes. That is, any node has the information of all its child nodes. We use array + linked list to achieve this. The structure of the above tree using child notation is as follows:

In this way, for any node, all its child nodes can be found directly. We can also combine it with the above parental representation to give it more power.

Child brother representation

In this way, an ordinary tree can be converted into a binary tree. It uses two pointers to point to its first child node and its first right sibling node, respectively.

The result of the tree at the beginning of the article using the child brother representation is as follows:

Full binary tree and complete binary tree

The concept of binary tree was introduced in the previous article. In fact, there are several special binary trees in binary tree, two of which are introduced here.

Full binary tree

In a binary tree, if all branch nodes have left and right subtrees, and all leaves are on the same layer, such a binary tree is called a full binary tree.

The full binary tree is a perfect binary tree, and each of its subtrees is symmetrical. The following is a full binary tree:

Complete binary tree

A binary tree with n nodes is numbered in sequence. If the node numbered I (1 ≤ I ≤ n) has exactly the same position in the binary tree as the node numbered I in the full binary tree of the same depth, the binary tree is called a complete binary tree.

This sentence may not be easy to understand, to put it simply, a complete binary tree is a full binary tree with fewer leaves, and the leaves are less from right to left. For example, the following picture is a complete binary tree. Comparing it with the full binary tree above, we can find that they are exactly the same from top to bottom, except that the complete binary tree lacks a few leaves at the end. If any node in the middle does not match, it is not a complete binary tree.

Storage of binary tree

Binary trees can also be stored sequentially or chained, which is similar to the child representation of the tree. Define a lchild and rchild pointer to point to the left child and the right child, respectively. Its sequential storage is much simpler than an ordinary tree, so let's take a look at how the sequential storage of binary trees is implemented.

Sequential storage

Taking the above complete binary tree as an example, we can find that the position of each node is the same as that in its online table, so there is no need for a pointer to point to its parent node or child node. we can just store it in the array according to the sequence traversal. The results are as follows:

The above is for a complete binary tree, what if it is not a complete binary tree? For example, the following tree:

Starting from the third row, the location of the data is no longer the same as that stored in the array, for example, the subscript of 5 in the array is 4. At this point, we need to use space to supplement, compare this binary tree with a complete binary tree, and the missing part is supplemented by empty or specific characters in the array. Take this binary tree as an example, its corresponding complete binary tree is as follows, in which the part of the dotted line connection does not actually exist.

Then, in the way of a complete binary tree, the elements that do not actually exist when stored in the array are represented as empty, and the result is as follows:

In this way, the array can correctly correspond to the original binary tree. The feasibility of this approach is that for a general binary tree, the smallest complete binary tree that can be constructed is unique, where the minimum does not add useless leaf nodes at the end of the complete binary tree.

The problem of sequential storage is thus exposed, compared with the complete binary tree, more trees are this general structure, which means that there will be a large number of empty spaces in the array, which is a great waste of memory.

Traversal implementation of binary Tree

The traversal of binary tree can be divided into three kinds: pre-order, middle order and post-order, and another kind is called sequence traversal, which is traversed from top to bottom. After introducing these concepts of traversal, let's take the above general binary tree as an example to demonstrate these traversal.

1. Construct binary tree

We demonstrate with chained storage, and the structure of the node is as follows:

Class TreeNode {Integer data; TreeNode lChild; TreeNode rChild; public TreeNode (Integer data) {this.data = data;} 2. Sequence traversal

The characteristic of sequence traversal is to first get the value of the root node, then get its left child, and then get its right child, such as the tree above, the acquisition order is 1-> 2-> 3, this part is very simple. But the next step is to go back to 2 from 3, get 5 and then go back to 3, so it's not so easy to jump back and forth between 2 and 3. We can do it with the help of the queue.

For demonstration purposes, we use black to represent the current node, blue to represent its left child, and red to represent its right child to build the following model:

Taking the above tree as an example, the principle of implementation with Queue is as follows:

First of all, join the team at the root node, cut off its two children when joining the team, and join the team with both children in the left and right order, and then discard the root node:

Then do the same for node 2:

Next, deal with node 3:

I believe you have found that after getting 2, the next step is to get 3, and 5 is cleverly placed after 3, so that we can traverse the binary tree layer by layer. The Java code is as follows:

Private void levelTraverse (TreeNode tree) {if (tree = = null) return; Queue queue = new LinkedList (); queue.add (tree); TreeNode node; while (! queue.isEmpty ()) {node = queue.poll (); System.out.println ("Node is" + node.data); if (node.lChildNull) {queue.offer (node.lChild) } if (node.rChildchild invalid null) {queue.offer (node.rChild);} 3. Preorder traversal

Preorder traversal can be easily implemented using recursion, and the code is clear at a glance, as follows:

Private void preOrderTraverse (TreeNode tree) {if (tree = = null) {return;} System.out.println ("Node is" + tree.data); preOrderTraverse (tree.lChild); preOrderTraverse (tree.rChild);} 4. Traversing private void inOrderTraverse (TreeNode tree) {if (tree = = null) {return;} inOrderTraverse (tree.lChild); System.out.println ("Node is" + tree.data); inOrderTraverse (tree.rChild);} 5. After traversing private void postOrderTraverse (TreeNode tree) {if (tree = = null) {return;} postOrderTraverse (tree.lChild); postOrderTraverse (tree.rChild); System.out.println ("Node is" + tree.data);} so far, I believe you have a deeper understanding of "the storage structure of java tree and the traversal implementation of binary tree". You might as well do it in practice. Here is the website, more related content can enter the relevant channels to inquire, follow us, continue 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.