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

This article mainly explains "how to understand the tree in Java". The content in the article is simple and clear, and it is easy to learn and understand. Please follow the editor's train of thought to study and learn "how to understand the tree in Java".

Definition of 1 tree

A tree is actually a collection of many nodes, but the composition of each node is divided according to the tree structure. An ordinary tree structure can be defined by the following figure.

Let's say it again, the structure of the tree is like an upside down tree, and the nodes are made up of layers. A tree is made up of several subtrees, and the subtree is made up of smaller subtrees.

The blood relationship of a tree

For a node in the tree, it is directly related to the node in the upper layer at most and to multiple nodes in the lower layer. The node in the upper layer is called the parent node, and the node in the lower layer is called the child node. All nodes that are located at the bottom of the tree without children are called leaf nodes. Nodes with the same parents are sibling nodes.

The family rank of the tree

The tree is a big family with a very strict hierarchy. The number of subtrees of a node in a tree is called the degree of the node. So the leaf node is the node with degree 0. A node whose degree is not zero is called an internal node. Each node has its own level, which increases from high to low, the root node is the first layer, the root child node is the second layer, and so on. The maximum number of layers of a tree is called the height (or depth) of the tree.

Storage structure of 2 trees

Because the ordinary tree structure is not as regular as the binary tree, it may be a combination of multiple trees, so it is difficult to use the conventional linear structure to store. Therefore, the storage of the tree structure needs to peel off the relationship in the tree family for storage, save the relationship between each node, and the whole tree structure can be restored in turn.

It's like a family tree, recording our relationship with our parents and siblings. As for the tree, according to the different storage relationship, it can be divided into three storage methods: parent representation, child representation and sibling representation.

Parental representation

According to the parents of the tree, it is obvious that the hierarchical relationship of the whole tree is stored by recording the parent nodes of each node. One of the storage structures commonly used here is arrays. The node of the tree is stored in a continuous address and corresponds to the sequence number of its parent node in the array, so that the parent information of all nodes can be saved.

The parent representation directly stores the parent position of the node (corresponding to the subscript of the array), so it is very convenient to find the parent node and ancestor node of a node. But it is impossible to directly obtain the location of the child node of the node.

If you need to find the children and descendants of the specified node, you need to traverse the entire array and make multiple judgments.

Child representation

The shortcomings of the parental representation of the tree are obvious, so the most direct solution is to simply save the child node. Not to mention, the child representation is such a representation. However, compared with the storage of parent nodes, there is a problem to be considered in storing child nodes, that is, there is at most one parent node in a node, but there may be more than one child node. If each child node is stored in an array, this is not a wise choice, and it is not necessary.

So when using the child representation to store the structure of the tree, we often use the structure of array + linked list. Whether this structure is very common or not is similar to the chain address method for solving hash conflicts. In such a chain structure, a pointer is used to indicate each child of the node, and the position of each child is connected in turn by a linked list, so it is very convenient to find the descendants of each node.

It's just that the problem remains, and you also need to traverse all the linked lists if you want to find parents looking for a node. However, now that both parents and children have expressed it, a simple and rough merger can complement each other and advance and retreat together.

The so-called parent-child representation can directly combine the parental representation with the child representation. In this way, it can satisfy the search of both parents and children.

Child brother representation

Having a parent-child representation is enough to store the data and information in the tree, so why come to a child-brother method? In fact, the child-brother representation is a very interesting and valuable way of expression.

In the child sibling representation, we agree to store only the first child node and the next sibling node of each node. Not only that, nodes are stored through linked lists. The words are not very clear, so let's just look at the picture.

There seems to be some strange shape, and each node acts as a node in the linked list, pointing to the first child node and the next sibling node through two pointers. In case you don't understand, let me give you an example. Take node B, whose first child node is E and its next brother is C at the same level as it. So the two pointers of node B point to E and C, respectively.

The child-brother representation looks like a chicken rib, but if we adjust the picture on the right, we can see what's wrong with it.

Can you see that the child-brother representation actually converts an ordinary tree into a binary tree. So why is the binary tree so important? because everything is always in it. Seeing this, it also reveals the transformation relationship between the tree and the binary tree, and many properties and operations on the binary tree can also be used in the ordinary tree structure.

Traversal of 3 trees

Students who have studied binary tree must be familiar with pre-order traversal, mid-order traversal, post-order traversal, mid-order traversal, no matter iterative or non-iterative writing, they are all things that can no longer be based. For ordinary trees, because the number of sub-trees of each node is not certain, it is difficult to specify the order of pre -, middle and post-order.

Therefore, generally speaking, there are two ways to traverse the tree, which can be divided into first root traversal and post root traversal according to the order in which the root node is traversed.

The first root traversal of the tree is to visit the root node of the tree first, and then traverse the subtrees of the root node in turn. So recursive. When an ordinary tree is converted into a corresponding binary tree (child brother representation), it is actually equivalent to preorder traversal.

There is no need to say much about the traversal of the back root of the tree, contrary to the traversal of the first root, visit each subtree of the root node first, and then visit the root node. The traversal of the back root of the tree is equivalent to the traversal of the middle order of the transformed binary tree. If you don't believe me, try it.

4 the conversion of trees, forests and binary trees

When I wrote about this, I suddenly found that I forgot to introduce what the forest is. In fact, the concept of forest is very simple, that is, many trees. Yeah, that's it.

Trees, forests, and binary trees are all similar structures in nature, so they can be converted to each other. Any forest or tree can be represented as a binary tree, and any binary tree can also correspond to a forest or a tree.

The transformation of a tree into a binary tree, which we have introduced earlier, is through the child brother representation of the tree. When represented by the child brother method, each tree can be represented by a unique binary tree. However, the converted binary tree has a very remarkable feature. Watch carefully.

Obviously, this is not a balanced binary tree. Moreover, the root node does not have a right subtree, I am sure. This is because the root node has no sibling node, it only has a child node, so after conversion to a binary tree, there must be no right subtree.

But such defects can be remedied in the forest. Since there are many trees in the forest, other trees can be used as right subtrees. The specific implementation step is to convert each tree in the forest into a binary tree, and then take the root node of the first tree as the root of the converted binary tree. The left subtree of the first tree is the left subtree of the root node of the converted binary tree, and the second tree is the right subtree of the converted binary tree. The third tree is the right subtree of the root node of the converted binary tree. and so on.

Let's give an example. There is a forest of three trees.

Transform the above three trees into binary trees in the following form.

Then taking the green binary tree as the right subtree of the blue binary tree root node and the yellow binary tree as the right subtree of the green binary tree root node, the result of forest conversion into binary tree can be obtained.

According to the above rules, a binary tree can also be converted into trees and forests.

Thank you for your reading, the above is the content of "how to understand the tree in Java", after the study of this article, I believe you have a deeper understanding of how to understand the tree in Java, and the specific use needs to be verified in practice. Here is, the editor will push for you more related knowledge points of the article, welcome to follow!

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.