This series of articles is recommended reading

  • Use diagrams and code to make you understand the sequential structure of linear tables
  • After reading this article, I finally understand the linked list
  • 【 Data structure of the stack 】 With detailed pictures and texts to understand the “stack” (Principle)
  • The queue of data structures Learning queues, read this one is enough!
  • 【 Data structure linked list 】 detailed graphics teach you tricks to play linked list
  • [Data structure of binary tree] to understand the concept and principle of binary tree

The foreword 0.

The previous [concept and principle of binary tree] mainly introduces the concepts and principles of the tree, the main content of this paper is the creation of binary tree and traversal code implementation, including recursive traversal and stack traversal.

1. The implementation idea of binary tree

1.0. Sequential storage – Array implementation

We’ve seen full and complete binary trees, and we’ve numbered them in unbroken order from 0 to n, and arrays have that same number, array subscripts, and once we combine the two, an array can store a binary tree.

So how do non-full and incomplete binary trees use array storage?

We can construct a full/complete binary tree by adding some imaginary nodes to the binary tree. When stored in an array, the imaginary node corresponds to an array element that does not store data (# denotes imaginary nonexistence). The diagram below:

The downside of this storage is that there may be a lot of unused space in the array, resulting in waste.

1.1. Linked storage – Linked list implementation

When we draw trees, we always use nodes and arrows, nodes represent data elements, arrows represent relationships between nodes, very clear. If you’re familiar with linked lists, you’ll notice that this is a classic chain structure. The chained structure perfectly solves the space waste that can occur in sequential structures, and there are no array space constraints.

Now let’s analyze the structure of the nodes.

The node of the tree consists of a data element and several branches pointing to its children. The nodes of a binary tree are relatively simple, including:

  • The data element
  • Left subtree branch (left child of node)
  • Right subtree branch (right child of node)

How do you do that? The nodes of a singly linked list are represented by a pointer to their successors. Similarly, we can use Pointers to indicate the relationship between a node and its left and right children.

At this point, the nodes of the binary tree are clear:

  • A variable that stores datadata
  • A pointer to its left child —left_child
  • A pointer to its right childright_child

Use C language structure to achieve the nodes of binary tree (for convenience, our data are all character types) :

/* The structure of the nodes of the binary tree */
typedef struct Node {
    char data; / / data domain
    struct Node *left_child; // Left child pointer
    struct Node *right_child; // Right child pointer
} TreeNode;
Copy the code

2. Creation of binary trees

The definition of a binary tree is recursive, so if you want to create a binary tree, you can do it recursively. How do you recursively create? In reality, a tree grows roots first, then branches, then leaves. When we create trees in code, we follow this principle by creating the root first, then the left subtree, and then the right subtree. The whole process is similar to a sequential traversal.

A dynamic diagram of the binary tree creation process in my previous article will not be covered here.

Here’s an example of creating a tree like the one below:

Note: When we see a binary tree like the one on the left, we should immediately imagine the corresponding one on the right. What is the node?

We’ve already drawn a similar graph, which was NULL, and what it does is it indicates that a node doesn’t have children, and we made it up. When actually creating binary trees in C, you need to use # or some other symbol instead of NULL.

The preceding traversal order is: ABDEGCF, if the # node is added, it is: ABD##EG### #C#F##. We create binary trees in this order.

The code is as follows:

/** * create a binary tree * root: a pointer to a pointer to the root */
void create_binary_tree(TreeNode **root)
{
    char elem;
    scanf("%c", &elem);
    if (elem == The '#') {
        *root = NULL;
    } else {
        *root = create_tree_node(elem); // Create a binary nodecreate_binary_tree(&((*root)->left_child)); create_binary_tree(&((*root)->right_child)); }}Copy the code

Note that create_binary_tree takes a pointer to a pointer to the root. The reason for using a pointer to a pointer was explained in the initialization section.

3. Binary tree traversal

In the article [the concept and principle of binary tree] has introduced the principle of traversal, the following use of C language to achieve it.

3.0. Traverse the substance

The definition of binary tree is recursive, that is, the definition of binary tree is used in the definition of binary tree. So whether you’re creating a binary tree or traversing a binary tree, there are only three things you need to do: access the root, find the left subtree, and find the right subtree. The so-called order, order, order traversal, is nothing more than the order of these three things.

3.1. Recursive implementation

If we use recursive code, it is very easy to iterate, and the code is very simple.

[Sequential traversal]

/** * root: pointer to the root */
void preorder_traversal(TreeNode *root)
{
    if (root == NULL) { // If the binary tree is empty, short operation
        return;
    }
    printf("%c ", root->data); // Access the root
    preorder_traversal(root->left_child); // Recursively traverse the left subtree
    preorder_traversal(root->right_child); // Recursively traverse the right subtree
}
Copy the code

【 Middle order traversal 】

/** * root: pointer to the root */
void inorder_traversal(TreeNode *root)
{
    if (root == NULL) { // If the binary tree is empty, short operation
        return;
    }
    inorder_traversal(root->left_child); // Recursively traverse the left subtree
    printf("%c ", root->data); // Access the root
    inorder_traversal(root->right_child); // Recursively traverse the right subtree
}
Copy the code

[Sequential traversal]

/** * root: pointer to the root */
void postorder_traversal(TreeNode *root)
{
    if (root == NULL) { // If the binary tree is empty, short operation
        return;
    }
    postorder_traversal(root->left_child); // Recursively traverse the left subtree
    postorder_traversal(root->right_child); // Recursively traverse the right subtree
    printf("%c ", root->data); // Access the root
}
Copy the code

In fact, most of the things you do recursively, you can do with stacks. The stack implementation of traversal is described below.

3.2. The stack

We took advantage of the lifO nature of the stack,

The code of stack implementation is more complex, limited by space, here only introduces the sequential traversal and the sequential traversal, please go to the code warehouse for details.

[Sequential traversal]

The nodes of our tree should all be pushed (regardless of the order), so what are the conditions for pushing? This is when the node can be treated as the root of a tree (subtree). That is, the curr pointer must point to the root of a tree (subtree).

We have seen in the concept and Principle of binary tree that when traversing a subtree, it is necessary to return to its parent node. How is this backtracking implemented? We can make use of the advanced last out and last in first out characteristics of the stack, which can perfectly preserve the parent-child relationship of nodes in the stack in the tree, and the top element of the stack is the parent node of the current subtree.

/** * traverses */ using a stack implementation
void preorder_traversal_by_stack(TreeNode *root)
{
    // Create and initialize the stack
    Stack stack;
    init_stack(&stack);
    
    TreeNode *curr = root; // The auxiliary pointer is curr

    while(curr ! =NULL| |! stack_is_empty(&stack)) {
        while(curr ! =NULL) {
            printf("%c", curr->data); // Prints the root
            push(&stack, curr); // the root is pushed
            curr = curr->left_child; // Enter the left subtree
        }
        if(! stack_is_empty(&stack)) {
            pop(&stack, &curr); // go back to the last root
            curr = curr->right_child; // Enter the right subtree}}}Copy the code

[Sequential traversal]

Post-order traversal is more troublesome than pre-order and middle-order traversal, unlike pre-order and middle-order traversal. Since the roots of both foreorder and seed order precede the right subtree, we can print the root and enter the right subtree at the same time when we exit the stack.

The root of the last iteration is behind the right subtree, so we’re going to have to iterate through the left subtree, go back to the root, go into the right subtree, iterate through the right subtree, go back to the root to print it.

The key is also the order of the left subtree, the right subtree, and the root.

Therefore, when the curr pointer traverses the left subtree, we cannot directly remove the root node from the stack. Instead, we first read from the top of the stack to the root node, then return to the root node, and then enter the right subtree for traversal. When the right subtree traverses, the root node is removed from the stack to print the root node.

In this way, there are two actions back to the root, with different subsequent actions. The first time you go back to the root by reading the top of the stack, and then into the right subtree; The second time we go back to the root, we print the root.

So this seems to solve the order problem of post-order traversal, but it actually raises a new problem, which is, how do we know that the right subtree is traversed?

We have to go back to the root twice, and for people who write code, we know what to do after we go back to the root twice, we know if the right subtree has been traversed. But for the curr pointer, it doesn’t know, it goes back to the root twice, it doesn’t know if the right subtree has been traversed.

At this point, for the curr pointer, it is as if it has two paths to take and it has no choice. If one of them had its footprints, it could easily have taken the untrodden path.

So now we also need a “footprint” pointer — prev. The prev pointer keeps track of the nodes that curr has visited.

When the curr pointer returns to the root for the second time, oh! There are my footprints! The prev pointer is in the right subtree. The curr pointer simply prints the root.

/** * use the stack implementation of the sequential traversal */
void postorder_traversal_by_stack(TreeNode *root)
{
    Stack stack;
    init_stack(&stack);

    TreeNode *curr = root; // The secondary pointer curr records the current access node
    TreeNode *prev = NULL; // The footprint pointer prev records the last accessed node

    while(curr ! =NULL| |! stack_is_empty(&stack)) {
        if(curr ! =NULL) {
            push(&stack, curr); // the root is pushed
            curr = curr->left_child; // Enter the left subtree
        } else {
            get_top(&stack, &curr); // Read the top element, not out of the stack
            // The right subtree is not empty and the right subtree is not traversed
            if(curr->right_child ! =NULL&& curr->right_child ! = prev) { curr = curr->right_child;// Enter the right subtree
                push(&stack, curr); // the root is pushed
                curr = curr->left_child; // Enter the left subtree
            } else { // The right subtree has been traversed or the right subtree is empty, it is ready to print the root
                pop(&stack, &curr); // The root is out of the stack
                printf("%c", curr->data); // Prints the root
                prev = curr; / / record
                curr = NULL; // Empty to enter the next loop}}}}Copy the code

The function related to the stack in the above code is not shown here, please refer to the code repository (at the end of this article) for details.

4. To summarize

The recursive code, while concise, is a bit difficult for beginners to understand because of the lack of touch. The stack code is relatively easy to understand, but the code is more complex, especially post-traversal code.

But once you understand the definition, concept, and principle of binary trees, the code is no longer a problem, and it only comes down to six words: nothing else, nothing else.

Above is the realization of binary tree creation and traversal.

Complete code please visit lot | Gitee acquisition.

Please correct me if there are any mistakes.

If you think it’s good, you can like it and follow it. More data structures and algorithms will follow.