【 Series 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
  • Cue binary trees for data Structures: The principle and creation of cue binary trees

1. Why use cue binary trees?

Let’s first look at the disadvantages of a normal binary tree. Here is an ordinary binary tree (chained storage) :

At first glance, will there be a sense of dissonance? The whole structure has a total of 7 nodes, a total of 14 pointer fields, of which 8 are empty. For a binary tree with n nodes, there will be a total of N +1 null pointer fields. This rule uses all binary trees.

Isn’t it wasteful to have so many null pointer fields? The focus of our study of data structures and algorithms is to find ways to improve time efficiency and space utilization. So many pointer fields are wasted, what a loser!

So we need to figure out how to use them, how to use them to help us better use binary trees as data structures.

So how to use it?

As has been emphasized many times before, the essence of traversing a binary tree is to transform the nodes of a nonlinear structure in a binary tree into a linear sequence, so that we can easily traverse it.

For example, the middle-order traversal sequence in the figure above is DBGEACF.

For a linear sequence (a linear list), there are concepts of immediate precursors and immediate successors (in what is a linear list?). ). For example, in a middle-order traversal sequence, the immediate precursor of B is D, and the immediate successor is G.

The reason why we know the immediate precursor and immediate successor of B is because we write down the middle-order traversal sequence of the binary tree according to the middle-order traversal algorithm, and then we say who is the precursor and who is the successor based on that sequence.

Direct precursors and direct successors cannot be completely obtained by binary trees, because there is only a direct relationship between parent and child nodes in binary trees, that is, the node pointer field of binary trees only stores the addresses of their child nodes.

Now what I want is, I want to be able to get directly from the binary tree a direct precursor and a direct successor of a node in middle order traversal mode.

This is where the cue binary tree comes in.

2. What is a binary tree of clues?

Of course, we definitely need to use the pointer field of the node to hold the addresses of the immediate precursor and immediate successor.

In fact, in the ordinary binary tree above (sequence traversed in middle order), some nodes (nodes whose pointer field is not empty) can find their direct precursor or successor. For example, G, the left child of node E, is the direct precursor of node E. The right child of node A, C, is the immediate successor of node A.

However, partial nodes (with null pointer field) are not feasible, such as node G whose immediate successor is E and direct precursor is B, but this cannot be concluded in binary trees. What to do? Note that both fields of Pointers to node G are NULL and are not being used.

It was the best of both worlds, a match made in heaven! But the problem is not solved!

Since we are using a null pointer field to point to a precursor or successor, this is paradoxical for nodes whose pointer field is not null, such as E and B.

Since there is a contradiction, then we find the root cause of the contradiction, solve the contradiction.

The root cause of the contradiction is: when the pointer field of the node is null and not null, the pointer points to the contradiction. That is, the contradiction between a pointer pointing to a child when it is not null and a pointer pointing to a precursor or successor when it is null.

So we are appropriate to the case, the pointer field is empty and not empty to distinguish, clearly tell the pointer: not empty point to the child, empty point to the precursor or successor. This requires us to add a flag bit to each pointer.

And agree the following rules:

  • left_flag == 0When the pointerleft_childPoint to the left, kid.
  • left_flag == 1When the pointerleft_childPointing to a direct precursor
  • right_flag == 0When the pointerright_childPoint to the right, kid.
  • right_flag == 1When the pointerright_childPointing to a direct precursor

The nodes of the binary tree change:

/* The structure of the node of the clue binary tree */
typedef struct Node {
    char data; / / data domain
    struct Node *left_child; // Left pointer field
    int left_flag; // The left pointer flag bit
    struct Node *right_child; // Right pointer field
    int right_flag; // Right pointer flag bit
} TTreeNode;
Copy the code

With the flag bit, everything is clear. We call the Pointers to immediate antecedents and successors clues. A pointer with flag bit 0 is a pointer to the child, and a pointer with flag bit 1 is a clue.

A binary linked list tree with the node structure shown above, where we turn all null Pointers into clues, is called a binary clue tree.

3. How to create a binary tree of clues?

In ordinary binary trees, if we want to obtain the direct precursor or successor of a node in a certain traversal order, we need to obtain the traversal order every time before we know. In the case of a cued binary tree, we only need to traverse once (traversal when creating the cued binary tree), and then the cued binary tree “remembers” the immediate precursor and successor of each node, without ever needing to traverse the order again.

The process by which we turn an ordinary binary tree into a cued binary tree in a certain traversal way is called cueing of binary trees.

Next, we use the middle order traversal method, the following binary tree clue into the clue binary tree

To pass a pointer with flag bit 1 through the sequence in middle order so that it points to a precursor or successor:

Where, node D has no direct precursor and node F has no direct successor, so the pointer is NULL.

So far, we have solved the waste caused by n+1 null pointer field in the binary tree with N nodes. The solution is to add a flag bit to the pointer of each node to make use of the null pointer field. Flag bits store Boolean values of 0 or 1, which is relatively cost-effective compared to wasteful null pointer fields. Moreover, a new property of binary tree is given, that is, binary tree can store the precursor and successor relations between nodes in a certain traversal order.

4. Realization of cueing

Note that the cue binary tree is derived from an ordinary binary tree, and in some traversal order. Because the clue can be set only when the precursor and successor of a node are known, and the precursor and successor relationship cannot be directly reflected through the binary tree, but can only be obtained by traversing the linear sequence of the binary tree. Therefore, the null pointer of the node can be modified to set the clue only after the sequence with the precursor and successor relationship can be obtained through some traversal method.

That is, the essence of cueing is to modify the null pointer of a node in the process of traversing a binary tree according to a certain traversal order to make it point to its direct precursor or direct successor under the traversal order.

We in “binary tree traversal principle” and “binary tree traversal implementation” respectively introduced the binary tree four traversal methods of principle and code implementation. We introduced traversal as an example of printing. But traversal doesn’t just do printing, it can also do cueing.

So, the general structure of the code is the same, we just replace the printed code in the traversal code with the cued code, and make some other changes.

Three kinds of cueing are introduced respectively in the following pictures:

An unclued binary tree with all flag bits default to 0.

4.1. Middle order cueing

The following figure can be obtained after the sequential cueing is carried out according to the middle order:

Let’s first clarify the following:

  • We did this as we walked through the binary tree.

  • The middle order traversal is left subtree >> root >> right subtree.

  • Cueing modifies two things: the null pointer field and its corresponding flag bit.

  • How to modify? Sets the null pointer field to a direct precursor or successor.

So our question becomes:

  1. Find all null pointer fields.
  2. Find the node to which the null pointer field belongs, the direct precursor and direct successor under the preemptive order.
  3. Modifies the contents of the null pointer field and its flag bit so that the pointer is called a clue.

Note: We use recursion in traversing binary trees, so we use it in cueing as well.

The specific code is as follows:

// Global prev pointer to the node just visited
TTreeNode *prev = NULL;

/** ** ** */
void inorder_threading(TTreeNode *root)
{
    if (root == NULL) { // If the binary tree is empty, short operation
        return;
    }
    inorder_threading(root->left_child);
    if (root->left_child == NULL) {
        root->left_flag = 1;
        root->left_child = prev;
    }
    if(prev ! =NULL && prev->right_child == NULL) {
        prev->right_flag = 1;
        prev->right_child = root;
    }
    prev = root;
    inorder_threading(root->right_child);
}
Copy the code

4.2. Sequential cueing

After cueing according to the sequential order, the following figure can be obtained:

The specific code is as follows:

// Global prev pointer to the node just visited
TTreeNode *prev = NULL;

/** ** ** */
void preorder_threading(TTreeNode *root)
{
    if (root == NULL) {
        return;
    }
    if (root->left_child == NULL) {
        root->left_flag = 1;
        root->left_child = prev;
    }
    if(prev ! =NULL && prev->right_child == NULL) {
        prev->right_flag = 1;
        prev->right_child = root;
    }
    prev = root;
    if (root->left_flag == 0) {
        preorder_threading(root->left_child);
    }
    if (root->right_flag == 0) { preorder_threading(root->right_child); }}Copy the code

4.3. Postsequential cueing

The following figure can be obtained after the sequential cueing is carried out according to the subsequent sequence:

The specific code is as follows:

// Global prev pointer to the node just visited
TTreeNode *prev = NULL;

/** ** ** */
void postorder_threading(TTreeNode *root)
{
    if (root == NULL) {
        return;
    }
    postorder_threading(root->left_child);
    postorder_threading(root->right_child);
    if (root->left_child == NULL) {
        root->left_flag = 1;
        root->left_child = prev;
    }
    if(prev ! =NULL && prev->right_child == NULL) {
        prev->right_flag = 1;
        prev->right_child = root;
    }
    prev = root;
}
Copy the code

5. To summarize

The cued binary tree makes full use of the null pointer field in the binary tree, and gives the binary tree a new feature: after cueing through a traversal, the binary tree can store the precursor and successor relations between its nodes.

So, if we need to traverse the binary tree frequently, looking for the immediate precursor or successor of a node, using the clue binary tree is very appropriate.

In addition, because the code involves recursion, it can be difficult to understand at first sight, so we can debug with breakpoints and watch the whole process of cueing in detail to help understand.

So that’s how the clue binary tree works

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.