Android Skill Tree - Basic Knowledge of The Tree

Preface:

Now Android interview, for the data structure of the question is more and more, also often see others send interview questions are asked what red black tree, binary tree search, so although we will not immediately all kinds of difficult interview questions, but at least the basic knowledge of the tree or will, so as to further learn.

Post an introduction picture you saw recently:

Android Skill Book Series:

Android Basics

Android Skill Tree – Animation summary

Android Skill Tree – View summary

Android Skill Tree – Activity summary

Android Skill Tree – View event system summary

Android Skill Tree – Summary of Android storage paths and I/O operations

Android Skill Tree – Multi-process related summary

Android skill Tree – Drawable summary

Basic knowledge of data structures

Android Skill Tree – Array, linked list, hash table basic summary

Android Skill Tree — Basic Knowledge of The Tree

Basic knowledge of algorithms

Android Skill Tree – Sorting algorithm basics summary

This paper mainly talks about the basic knowledge of trees.

A Tree is a finite set of n(n>=0) nodes. N =0 is called an empty tree. In any non-empty tree :(1) there is only one specific node called Root; (2) When n>1, the other nodes can be divided into M (m>O) finite sets T1, T2…… Tm, where each set is itself a tree and is called a SubTree of the root.

Basic knowledge of

node

I drew a summary diagram based on the basics above (so I don’t need to write a text introduction, lol) :

Tree structure characteristics

Again, use my own drawing to illustrate:

Storage structure

In Android skill tree – array, linked list, hash table basic summary, we introduce linear storage, chain storage, our tree can fully use the combination of the two.

We use the above methods to represent the storage structure of the following tree:

Parent notation:

Within each node, there is an indicator indicating the position of its parent node in the array.

Since there are eleven nodes, our index is 0-10, and then the index position stores (data + parent’s index value), and the result is as follows:

The parent pointer in index makes it easy to know what the parent is, but if I want to know what E’s children are, I don’t know what E’s children are.

Of course, we can add a pointer in disguise:

If we are more concerned about the relationship between siblings, we can add a right sibling field to reflect the sibling relationship:

Child linked list notation:

Arrange the child nodes of each node and use a single linked list as the storage structure. Then n nodes have n child linked lists. If it is a leaf node, the single linked list is empty. The n head Pointers then form a linear table, stored sequentially in a one-dimensional array.

To represent the tree above us in child notation, the structure is as follows:

So we have two types of node structure: 1.

Child linked list of child nodes:

But it’s easy to look up the child of a node, or look up the sibling of a node, but it’s kind of hard to look up the parent of a node. So we can combine that with the parent representation that we talked about above.

Parent child representation:

Combine the above two methods.

Child brother notation:

Any tree, its first child is unique if it exists, and its right brother is unique if it exists. So set two Pointers to the first child of the node and the right sibling of the node

So it is similar to the above, except we have two different Pointers (from the method name, < child >< brother > method, one child, one brother, two Pointers).

We implement the above tree in this way:

Forest:

Continue to draw a picture to illustrate, save typing, hey hey:

classification

Trees are also classified according to different conditions, so let’s see.

So what’s the difference between an ordered tree and an unordered number?

If the subtrees of the nodes in the tree are regarded as orderly from left to right and cannot be interchanged, it is an ordered tree, otherwise it is an unordered tree

For example, we simply represent a family relationship:

For example, if A’s child has B and C, then B and C switch places and it doesn’t matter, then it’s an unordered tree.

But if we had a family tree that sorted by age (first son, second son), then B and C wouldn’t be able to switch places, and that would be an ordered tree.

But we usually say the tree is usually refers to the ordered tree, and the ordered tree has a lot of classification, more is binary tree.

Binary tree:

Basic form:

Properties of binary tree:

In fact, this is similar to the math formula we have to memorize in math class before, you can draw a binary tree, and then try to compare the above formula, is correct.

Traversing the binary tree:

Binary tree traversal means that all nodes in the binary tree are visited in a certain order starting from the root node, so that each node is visited sequentially and only once.

Sequential traversal:

Just looking at this graph, actually, I wouldn’t understand the rules, but we just need to understand the rules.

Pseudocode: traversal (node object t) {if( t == null){
            return; } // The first step is to implement some business operation, such as we print the node string.print(t) // In the second step, the recursive method continues to call the method to iterate over the left child (t). In the third step, the recursive method continues to call the method to iterate over the right child (t. Right child)}Copy the code

We see that because print precedes the other methods, it is called front-order traversal. So now we pass in the root to this method, and then we print and recurse, and we see that it’s the order on the diagram.

Middle-order traversal:

Pseudocode: traversal (node object t) {if( t == null){
            return; } // The first step is to recursively call the method to iterate over the left child (t). Step 2, implement some business operation, such as we print the node string.print(t) // In the third step, the recursive method continues to call the method to iterate over the right child (t). Right child)}Copy the code

We found that as long as we put our print statement in the middle, it was middle-order traversal.

Post-order traversal:

Pseudocode: traversal (node object t) {if( t == null){
            return; } // The first step is to recursively call the method to iterate over the left child (t). Left child) // In the second step, the recursive approach continues by calling the method to traverse the right child (t. // Step 3, implement some business operation, such as we print the node string.print(t)       
}
Copy the code

We found that as long as we put our print statement at the end, it’s post-order traversal.

Binary tree classification:

Inclined tree:

Complete and full binary trees:

A binary tree with a depth of K and 2^(k+1) – 1 nodes is called a full binary tree, which is characterized by the maximum number of nodes at each level.

In a binary tree, if all the layers except the last layer are full, and the last layer is either full or lacks consecutive nodes on the right side, the binary tree is a complete binary tree.

Balanced binary tree:

This piece of knowledge is very much, later fill up.

Sort binary tree:

This piece of knowledge is very much, later fill up.

Clue binary tree:

The binary linked list with n nodes contains n+1(2n-(n-1)= N +1) null pointer fields. The null pointer field in a binary linked list is used to store Pointers to the preceding and subsequent nodes of a node in some traversal order (such additional Pointers are called “clues”).

Here must explain a knowledge point: what is precursor and successor.

This explanation is so simplistic that many people get it wrong. For example:

Suppose we now have this a binary tree:

Android Skill Tree – Array, linked list, hash table basic summary

A bidirectional list, for example, has a precursor and a successor. That we simply see this tree is invisible, we need to put the tree in the manner of a traversal, put it in the form of a such a list on the table, and then you can know what is the precursor and the subsequent a node, such as in the figure above we use sequence traversal, we get is: HDIBJEAFCG, I at this moment before the D, the subsequent is B.

We have two Pointers to its two children in a binary tree storage structure.

But maybe there’s only one child, or maybe there’s no child, and then the empty pointer store is wasted, and we can store the pointer to the precursor or the successor of this node in this pointer.

The problem is that we don’t know whether the pointer is a precursor or a left child at this point, so we need a parameter to specify which pointer is at this point.

When ltag is 0, lChild is the pointer to the left child of the node; when ltag is 1, lChild is the precursor of the node.
When rtag is 0, rChild is the pointer to the right child of the node; when rtag is 1, rChild is the successor of the node.

Storage structure:

Binary tree sequential storage structure:

We fill the binary tree with a full binary tree, and then fill in a one-dimensional array accordingly.

Binary linked list:

A binary tree has at most two children per node, so it is designed with a data field and two pointer fields.

Trigeminal linked list:

Improved on the binary linked list, add parent node guidance, can better realize the access between nodes

Conclusion:

This article is not finished, the content is too much, and then continue to fill up. Welcome to point out my mistakes. thank you

Reference:

Big Talk Data Structure

Wikipedia