What is a binary tree

In computer science, a binary tree is a data structure in which each node has at most two child nodes, as shown in the figure below:

The definition of a binary tree is that simple, but this seemingly simple data structure is anything but simple to traverse.

How do I traverse a binary tree

The so-called traversal is simply like looking for treasure in a maze. The treasure is hidden in a tree node, but we do not know which node it is, so to find the treasure, we need to search all tree nodes systematically.

So how do you systematically search a binary tree?

Given a single linked list, you know how to traverse it almost without thinking about it. It’s simple: take the first node, process the current node, take the next node from the first node, and repeat the process until the node is empty.

You’ll see that the rules for traversing a list are very simple, and the reason is that the list itself is simple enough, it’s just a line, but a binary tree is not a simple line, it’s a triangle net.

So given a binary tree, how do you traverse it? For example, how do you systematically search all the nodes (1,2,3,4,5,6)?

As some of you may have noticed, we can search layer by layer, traversing each node from left to right until there are no nodes in the current layer, which is a binary tree traversal method. This hierarchical traversal method of a tree takes advantage of the depth of the tree (relative to the root node). Nodes at the same level have the same depth. Can we take advantage of the fact that a tree has left and right subtrees to traverse? The answer is yes.

The left subtree of 1 is 2, the left subtree of 2 is 3, and the right subtree of 2 is 4…

Let’s say we go through the root node 1 first, and then what, you might think, and then we go through the left subtree of 2, which is 2, and then what do we do when we get to 2? Do I want to traverse the right subtree of 2? Obviously we shouldn’t go through the right subtree of 2. Why? The reason for this is simple, because from node 1 to node 2 we traverse the left subtree, there’s no reason for us to change this rule when we get to node 2, and we’re going to continue the same rule, which is to traverse the left subtree first.

We’re at node 3, the left subtree of node 3 is empty, so we don’t have to walk through it, and then what? Obviously we should traverse the right subtree of node 3, but the right subtree of node 3 is also empty, and the tree root of node 3 is completely traversed.

What do I do when I walk through node 3? If you are in the maze, node 3, at this time is already dead end node 3, so you need to do is come along the way back to the original road, backs up a node is the parent node 2, and 3 in the computer algorithm called back, this is a common operation in the process of systematic search, we found after back to 2 2 left subtree is search, So you need to search is 2 right subtree is node 4, because node 4 haven’t been search, when came to node 4 we can continue to use the above rules until all the tree node complete search, why to node 4 before can continue to use the rules, the reason is very simple, Since a subtree with root 4 is itself a tree, the same rules apply.

So to summarize the rule:

Process the current node; Search the left subtree of the current node; After searching the left subtree, search the right subtree of the current node.Copy the code

This traversal of the current node and then the left and right subtrees of the current node is called pre_order. Of course, we can traverse the left subtree first, then process the current node and traverse the right subtree. This traversal order is called in_order. It is also possible to traverse the left subtree first, then the right subtree, and then the current node. This traversal order is called post_order.

Recursive implementation traverses the binary tree

Before we talk about recursively traversing a binary tree, let’s first express the structure of the binary tree with code:

struct tree {
struct tree* left;
struct tree* right;
int value;
};
Copy the code

From the definition we can see that the tree itself is recursively defined, the left subtree of the binary tree is a binary tree (struct tree* left), and the right subtree of the binary tree is also a binary tree (struct tree* right). Given a binary tree t, how do we traverse the binary tree?

struct tree* t; // Given a binary treeCopy the code

Some of you might think that traversing a binary tree is a very complicated process, is that really true?

Let’s look again at the rules for traversing binary trees from the previous section:

Process the current node; Search the left subtree of the current node; After searching the left subtree, search the right subtree of the current node.Copy the code

Suppose we have implemented a tree traversal function defined like this:

void search_tree(struct tree* t);
Copy the code

We can print all the nodes of a tree by calling search_tree:

struct tree* t; // Given a binary tree search_tree(t); // Prints all nodes of the binary treeCopy the code

If there were such a function, we’d be done. You’d be insulted if I asked you how to write the code to print out the left subtree of tree T. It’s pretty simple, just pass the left subtree to search_tree.

seartch_tree(t->left); // Prints the left subtree of tree TCopy the code

What about the right subtree of print tree T? Too easy!

search_tree(t->right); // Prints the right subtree of tree TCopy the code

Isn’t that easy? How about printing the value of the current node? You must be tired of talking to me 🙂

printf("%d ", t->value); // Prints the value of the root nodeCopy the code

At this point we can print the root node, we can print the left subtree of tree T, we can print the right subtree of tree T. Now that we’ve solved all these problems, how do WE implement search_tree()?

If you don’t know, here’s what I’m going to say: It’s pretty simple. Just put the above lines of code together

void search_tree(struct tree* t) { printf("%d ", t->value); // Print the root value seartch_tree(t->left); // Print search_tree(t->right); // Print the right subtree of tree t}Copy the code

Is it easy, is it easy, surprise no surprise, surprise no surprise, we just gave the function definition and with rich imagination to implement this function 🙂

The code above perfectly conforms to the rules defined previously.

Of course we need to handle the special case, if the given tree is empty, then return directly, the final code is:

Void search_tree(struct tree* t) {if (t == NULL) void search_tree(struct tree* t) { printf("%d ", t->value); // Print the root value seartch_tree(t->left); // Print search_tree(t->right); // Print the right subtree of tree t}Copy the code

And for those of you who are confused, this function is just implemented, right? Is that correct? No doubt, this code is absolutely correct, you can build your own tree and try to run this code.

The above code is a recursive traversal of the tree.

I know what these students are thinking, this code does look right, it works right, so what does this code run like?

Recursive call procedure

Suppose you have code like this:

void C() {
}

void A() {
    B();
}

void main() {
    A();
}
Copy the code

A() will call B(), and B() will call C(), so the function call process is shown as follows:

In fact, when each function is called, there is a corresponding segment of memory, which stores the parameters passed in when the function is called and the local variables defined in the function. This segment of memory is called function frame. The function call process has the nature of stack in data structure, that is, advanced and then out. For example, when function C() is finished, the corresponding frame of function is released and returned to function B, and the corresponding frame of function B is released and returned to function A.

With this knowledge we can look at how recursive tree calling functions are performed. For simplicity, let’s give a simple tree:

What happens when the search_tree function is called in this tree, as shown below:

Search_tree () is called on the root node 1, and on the left subtree node of 1 after printing the value of the current node. The second function frame is pushed. After printing the value of the current node (2), call search_tree on the left subtree of 2, so that the third function frame is pushed; After printing the value of the current node, (3) call search_tree in the left subtree of 3, and the fourth function frame is pushed; Since the left subtree of 3 is empty, the fourth function frame exits when the first sentence is executed, so we come to the third function frame. At this point, the left subtree of node 3 is traversed, so we start to call search_tree on the right subtree of node 3. The following process is shown in the figure:

This process will continue until the right subtree of node 1 is also traversed and the recursive call is complete. Note that no code is actually contained in the function frame, which was added to make it easier to observe the recursive call to search_tree. The entire call process is not shown in the figure above, but you can deduce how nodes 5 and 6 are traversed.

As we can see from this process, there is nothing mysterious about a recursive call to a function. It is the same as a normal function call, except that a recursive function is special in that it calls itself instead of other functions.

From the above function call can be an important conclusion, that is a recursive function not always call, otherwise is the Stack Overflow, the famous Stack Overflow, then the recursive function call Stack under what circumstances will no longer be increased, in this case is that when a given tree is empty when the recursive function call Stack will no longer growth, So for recursive functions we must specify under what circumstances the recursive function will return directly, which is often called the exit of the recursive function.

Recursive tree implementation of three traversal methods

So far, we have seen how to traverse the tree, how to implement it in code, and how to call the code. Note where to print statements:

printf("%d ", t->value); // Print the root value seartch_tree(t->left); // Print search_tree(t->right); // Prints the right subtree of tree TCopy the code

Middle-order traversal and post-order traversal can be easily implemented by recursive traversal, as follows:

Void search_in_order(struct tree* t) {void search_in_order(struct tree* t) {if (t == NULL); search_in_order(t->left); Printf ("%d ", t->value); Search_in_order (t->right); // Print the right subtree of tree t}Copy the code

The sequence traversal is:

Void search_post_order(struct tree* t) {void search_post_order(struct tree* t) {if (t == NULL); search_in_order(t->left); // Print the left subtree of tree t search_in_ORDER (t->right); Printf ("%d ", t->value); // Print the value of the root node}Copy the code

Now, some of you might think that tree traversal is too easy, but how do you do it in a non-recursive way?

Make sure you understand the first few sections before you read.

If you still don’t fully understand please read it again carefully.

How do I turn recursion into non-recursion

Although recursive is simple to implement, recursive functions have their own specific problems. For example, recursive calls consume a lot of stack space, i.e. memory, and the process is time consuming, so performance is usually not as good as non-recursive versions.

So how do we implement a non-recursive traversal tree?

To solve this problem, we must clearly understand the recursive function call process.

It can be seen from the call process of recursive function that recursive call is nothing more than the process of function frame in and out of the stack, so we can directly use the stack to simulate this process, but the stack is not the function but the tree node.

Now that we know we’re using a stack to simulate recursive calls, we need to make two things clear:

  1. When is it pushed

  2. Under what circumstances

Let’s take the sequential traversal as an example.

If we look closely at the recursive invocation process, we can see something like this:

  1. Put all left subtree nodes on the stack starting from the root node

  2. Look at the top element of the stack. If the top element has a right subtree, the right subtree is pushed and the right subtree is the new root node. Repeat procedure 1 until the stack is empty

Now we can answer both questions.

When is it pushed?

You start by putting all left subtrees starting from the root onto the stack, and repeat step 1 if there is a right subtree at the top of the stack.

So what happens when you unstack?

When we look at the top of the stack we can actually pop off the top of the stack, which is different from recursive calls. Why? One thing we can be sure of when we look at the top of the stack is that the left subtree of the current node has already been processed, so all we need for the top of the stack is the information about the right subtree, and the top of the stack can pop off once we get the information about the right subtree.

So the above description is expressed in code:

void search(tree* root) { if(root == NULL) return ; stack<tree*>s; While (root){s.ush (root); root=root->left; } while(! // look at the top element of the stack, if the top element has a right subtree then the right subtree is pushed and repeat procedure 1 until the stack is empty tree* top = s.tep (); tree* t = top->right; s.pop(); while(t){ s.push(t); t = t->left; } } return r; }Copy the code

The above code is the basis for implementing three non-recursive traversals of the tree, so be sure to understand.

Now you can implement three non-recursive traversals of the tree.

Realization of binary tree non – recursive traversal

Some of you may have noticed that there was no printf statement in the code in the last section, but what if you were to print nodes in a sequential traversal using the code above? If you really understand the above code then it is very simple, for the sequential traversal, we just need to print the node before it is pushed:

void search_pre_order(tree* root) { if(root == NULL) return ; stack<tree*>s; While (root){printf("%d ", root->value); // s.ush (root) is printed before the node is added to the stack. root=root->left; } while(! // look at the top element of the stack, if the top element has a right subtree then the right subtree is pushed and repeat procedure 1 until the stack is empty tree* top = s.tep (); tree* t = top->right; s.pop(); while(t){ printf("%d ", root->value); // prints s.ush (t) before the node is pushed. t = t->left; } } return r; }Copy the code

What about middle order traversal? In fact, it is very simple, we just need to print when the node pop:

void search_in_order(tree* root) { if(root == NULL) return ; stack<tree*>s; While (root){s.ush (root); root=root->left; } while(! // look at the top element of the stack, if the top element has a right subtree then the right subtree is pushed and repeat procedure 1 until the stack is empty tree* top = s.tep (); printf("%d ", top->value); Tree * t = top->right; s.pop(); while(t){ s.push(t); t = t->left; } } return r; }Copy the code

What about subsequent traversal?

The subsequent traversal is more complicated because the situation is different when the stack is out.

In preorder and middle order traversal, as long as the left subtree is done, the top element is actually off the stack, but in subsequent traversal, it’s different. What is subsequent traversal? We can’t process the current node until we’ve traversed both the left and right subtrees, that’s the subsequent traversal, so how do we know that the left and right subtrees of the current node are all traversed?

Obviously we need some way to record the traversal, but actually we only need to record the previous node of the traversal.

If we know the previous node in the traversal, we can make the following decisions:

  1. If the previous node is the right subtree of the current node, then the right subtree is ready to pop

  2. If the previous node is the left subtree of the current node and the right subtree of the current node is empty, then it is ready to pop

  3. If both the left and right subtrees of the current node are empty, that is, the leaf node, then it is ready to pop

This solves the problem of when to push the stack, and if it does not meet these conditions, it cannot push the stack.

Just make some modifications to the code based on the above analysis:

void search_post_order(tree* root) { if(root == NULL) return ; stack<tree*>s; TreeNode* last=NULL; While (root){s.ush (root); root=root->left; } while(! s.empty()){ tree* top = s.top(); (top - > if left = = NULL && top - > right = = NULL | | / / the current node is a leaf node last = = top - > right | | / / before a node of the current node right subtree top - > right = = NULL && Last ==top->left){printf("%d ", top->value); // Last = top; // record the previous node s.pop(); } else { tree* t = top->right; while(t){ s.push(t); t = t->left; } } } return r; }Copy the code

conclusion

Recursive traversal of a tree is relatively simple and easy to understand, but recursive calls actually hide the relatively complex traversal process, which requires careful understanding to traverse a binary tree in a non-recursive manner.

Write in the last

Welcome to pay attention to my public number [calm as code], massive Java related articles, learning materials will be updated in it, sorting out the data will be placed in it.

If you think it’s written well, click a “like” and add a follow! Point attention, do not get lost, continue to update!!