These two days I am doing binomial tree related algorithm problems and taking some study notes. (Not even a binary tree? I am really not proficient, and I do not have to write binary tree related algorithms or data structures in my daily work. Because of their own food, so more to study hard!

define

In computer science, a Binary tree is a tree with at most two branches per node (i.e., no node with a branching degree greater than 2). Branches are usually referred to as “left subtrees” or “right subtrees”. The branches of a binary tree have left and right order and cannot be reversed at will.

Due to the characteristics of binary tree definition itself, it has a high degree of local repeatability, so when traversing the binary tree depth-first, recursion is usually used to achieve it. The code realized in this way is very simple and beautiful, and easy to understand.

Depth-first traversal

In general, there are three most common sequential traversal in depth-first traversal binary trees: pre-order, middle-order and post-order.

The preceding traversal sequence is as follows: visit the root -> traverse the left subtree -> traverse the right subtree

The middle order is traversed in the following order: traverse the left subtree -> visit the root -> traverse the right subtree

The order of traversal is as follows: traversal the left subtree -> traversal the right subtree -> visit the root node

Notice that the left and right are the entire subtree, not just one node, because we need to traverse the entire tree, so each traverse is done in this order, up to the leaf node.

For example, suppose we have the following binary tree:

The preceding traversal yields the sequence a-B-C-D-E

The middle order traversal yields the sequence b-A-D-C-E

The resulting sequence is B-D-e-C-A

It is not recommended to go to human recursion, at least my brain can not tolerate three layers… :

Level 1 recursion:

First access the root, so output root A, then traverse the left subtree (L1), and then the right subtree (R1);

Level 2 recursion:

For L1, the root node is accessed first, so the root node B is printed, and then the left and right subtrees of B are found to be empty, ending the recursion.

For R1, the root is accessed first, so C is printed, and the left subtree (L2) is traversed, and the right subtree (R2) is traversed.

Third level recursion:

For L2, the root node is accessed first, so the root node D is printed, and then the left and right subtrees of D are found to be empty, ending the recursion.

For R2, the root is accessed first, so the root E is printed, and the left and right subtrees of E are found empty, ending the recursion;

Front, middle and rear sequence characteristics

According to the definition of the first, middle and last order, it is not difficult to find the following characteristics:

• The first node in the preceding sequence must be root, and the last node in the following sequence must be root

• The left and right subtrees of each sort are regularly distributed

• A tree that follows the above two rules for each subtree

These characteristics are the expression of order in the definition.

All kinds of deduction

Here are the most basic algorithms for binary tree traversal:

• Given a binary tree, obtain the sequence of its front/middle/rear order traversal;

• Deduce the posterior order (or deduce the whole binary tree) from the anterior and middle order;

• Derive antecedents (or derive whole binary trees) from postorder and middle order;

For traversal of binary trees, as mentioned above, it is usually done recursively. For recursion, there is a template that can be directly applied:

public void recur(int level, int param) {
	
    // terminator
    if (level > MAX_LEVEL) {
        // process result
     	return;   
    }
    
    // process current logic
    process(level, param);
    
    // drill down
    recur(level+1, newParam);
    
    // restore current status
}
Copy the code

This is a practical tip that Chao talked about in my geek Time algorithm boot camp these two days (this template is especially good for beginners). Following the above three steps (step 4 if there are local variables that need to be released or extra processing) can help you write recursive code in a more organized way.

Here is an example of the derivation of the following order according to the preceding and middle order:

Initialize two sequences:

int[] preSequence = {1.2.3.4.5.6.7.8.9};
int[] inSequence = {2.3.1.6.7.8.5.9.4};
Copy the code

We can already find minimum repetition subproblems, recursion at a time, by using some of the features mentioned above

According to the value of the first node in the preceding order, match the index I where the value of this node is located in the middle order. In this way, we can get the front and back parts of the index I corresponding to the left and right subtrees respectively, then traverse the two left and right subtrees respectively, and output the value of the first node in the current preceding order, that is, the root node.

Following the top-down programming approach, we can start by writing the following initial recursive calls:

List<Integer> result = new ArrayList<>();
preAndInToPost(0.0, preSequence.length, preSequence, inSequence, result);
Copy the code

The first parameter represents the index of the first element of the preceding sequence;

The second argument represents the index of the first element of the ordered sequence;

The third parameter represents the sequence length;

The fourth parameter represents the preceding sequence;

The fifth parameter represents the trailing sequence;

The sixth parameter is used to save the results;

So let’s think about what the termination condition is, which is when we end the recursion, when our root is empty, which is when the length of the sequence is zero.

if (length == 0) {
	return;
}
Copy the code

Then consider the processing logic, which is to find index I:

int i = 0;
while(inSequence[inIndex + i] ! = preSequence[preIndex]) { i++; }Copy the code

Then we start to recurse down:

preAndInToPost(preIndex + 1, inIndex, i, preSequence, inSequence, result);
preAndInToPost(preIndex + i + 1, inIndex + i + 1, length - i - 1, preSequence, inSequence, result);
result.add(preSequence[preIndex]);
Copy the code

Since we are deriving a backward sequence, the order is as follows, adding the root comes last. So how do we figure out the first three parameters? Let’s just go through it the first time and figure it out.

The index of 1, the first node of the preordered sequence, is 2 in the mid-ordered sequence

The middle sequence starting index of the left subtree is the first index of the total sequence, and the length is 2.

The initial index of the preceding sequence of the left subtree is the second index of the total sequence, with a length of 2.

The middle sequence starting index of the right subtree is the third index of the total sequence, and the length is Length-3.

The starting index of the preceding sequence of the right subtree is the third index of the total sequence, and the length is length-3.

The complete code is as follows:

/** * Derive the following order ** from the preceding and middle order@paramPreIndex Indicates the preorder index *@paramInIndex Indicates the sequential index *@paramLength Indicates the length of the sequence *@paramPreSequence preSequence *@paramInSequence Sequence *@paramResult Result sequence */
private void preAndInToPost(int preIndex, int inIndex, int length, int[] preSequence, int[] inSequence, List<Integer> result) {
    if (length == 0) {
        return;
    }

    int i = 0;
    while(inSequence[inIndex + i] ! = preSequence[preIndex]) { i++; } preAndInToPost(preIndex +1, inIndex, i, preSequence, inSequence, result);
    preAndInToPost(preIndex + i + 1, inIndex + i + 1, length - i - 1, preSequence, inSequence, result);
    result.add(preSequence[preIndex]);
}
Copy the code

Refer to the link

• Wikipedia – binary tree