Three trees (1)
The tree structure is a beautiful structure.
It is an important structure in computer science, especially in the data structure. We will help you remember all this.
For the organization of the data, the tree structure is in a very special and important location. In general, the linear table is simple, and the data that can be organized through a linear relationship or its composite can be organized, and the figure structure is a more general structure, which can be used as modeling, and can be regarded as the most data structure. General forms, linear tables and tree structures can be regarded as their restricted form; but nonlinear structures, as the tree structure is the most concise, and the linear form is compared with the map, especially for large amounts of data, especially It is an irreplaceable role in the order of sorting and retrieval.
This time we talk about the binary tree and trees. Of course, only some questions are discussed.
1, the weekly tour of the binary tree
Traverse the access tree structure, the west of the binary tree is a typical. Of course, it is very simple, recursive access is presented in pre-sequence, order and sequence, and other hierarchical access (equivalent to width). However, I will remember that a classmate will go to Huawei to participate in the interview. People let him use C to write the two-fork trees, he did not write. So I have to ask college students to pay attention to basic skills.
Let's take an example, as shown below:
Its recursive travel results can be given as follows:
1) Prerequency: A, B, D, C, E, G, F, H, I
2) Order: B, D, A, G, E, C, H, F, I
3) Stress: D, B, G, E, H, I, F, C, A
We no longer give the implementation details of the algorithm, you can refer to books. However, we look at an interesting question, these three results, one knows two, can you launch the third type? Essential is, any know the results of two recursive circumstances, can you rebuild a binary tree?
Let us first assume that the result of the pre-sequence and the order, namely:
Preface: A, B, D, C, E, G, F, H, I
=> Two-forked tree?
Sedential: B, D, A, G, E, C, H, F, I
I remember that when I saw this topic, I was a bit awkward; however, if the detailed analysis algorithm features, it is not difficult to analyze.
Features of the preface weekly travel algorithm you know that A must be the root of the whole tree, but only the results of the preamble, the following is the boundary line of the left and right subtrand. But you look at the results of the order:
B, D, / A, / G, E, C, H, F, I
It is easy to see that B and D is the node, G, E, C, H, F, i, etc., B and D are the nodes of the left subtroduction, and the nodes of the right child. First look at the left subtree part, the result of the preamble, as above, B is its root. For D, but by the result of the preamble, you can't determine whether it is B. The left child or the right child, then look at the result of the order, can you know that the left child of B is empty, D is its right child. Then use this to determine the right child of A. You can rebuild the binary tree. If this algorithm is written, it is obviously still written to recurrent algorithms. Moreover, the result of the results of the sequential interoperability will be reconstructed, and the process is similar.
However, if only the result of the preamble and the sequence, this problem is slightly more complicated. Can you still? If you can't, how can I remedy? If you are interested, you can analyze your own, I will give an answer next time.
The travel of the binary tree is the most basic algorithm. With the algorithm related to it, there is a query (and insertion, delete, etc. related to the query), the height of the tree, the number of points (or the number of leaf nodes, branch nodes), etc. Here, I mention these, everyone may wish to use the implementation of the high-level language write algorithm, see the lessons of my classmates, the basic work is solid.
2, establish the biggest pile
Piles are interesting data structures, logically speaking, it is a complete binary tree. We give its two basic features, remember, understand, it is very helpful to you.
First, the full binary tree that is stacked in sequential storage structure; Second, this tree is partially ordered.
Features Everyone understands that the feature is said, such as the largest heap, it is completely ordered as the sorted binary tree, for each subtree (of course, including the tree itself) root, its value is always left The right child is the largest, and the left and right children are not necessarily an orderly.
So the algorithm for establishing the largest pile is quite natural. As shown below:
In the case where R left, the right sub-tree is not empty, recursive as follows:
1) If R> = H1, and R> = H2, the operation has been completed.
2) Otherwise, a larger exchange of R and H1, H2.
In this way, you can establish a maximum heap as long as you access the nodes required in the stack in a certain order. Just As shown below:
The use of a pile, of course, there are many, everyone is most easy to think, is the stack sort.
The lassification of the binary tree, we have nothing to say. Huffman tree coding is a typical greedy algorithm. If the principle of greed strategy is clear, the basic content of this algorithm will not have any problems.
We will continue to discuss the topic of the tree structure next time.
