Shulou(Shulou.com)06/01 Report--

In view of the principle and creation of clue binary tree, this article introduces the corresponding analysis and solution in detail, hoping to help more partners who want to solve this problem to find a more simple and feasible method.

1. Why use a clue binary tree?

Let's first take a look at the shortcomings of an ordinary binary tree. The following is a normal binary tree (chained storage):

An ordinary binary tree

At first glance, is there a sense of disobedience? The whole structure has a total of 7 nodes and a total of 14 pointer domains, of which 8 are empty. For a binary tree with n nodes, there will be a total of 1 empty pointer domains, which uses all binary trees.

Is it wasteful to have so many empty 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 so wasted, what a loser!

So we need to find ways to make good use of them and use them to help us make better use of the binary tree data structure.

So how to use it?

It has been emphasized many times before that the essence of traversing a binary tree is to transform the nodes of the nonlinear structure in the binary tree into a linear sequence, and then it is convenient for us to traverse.

For example, the traversal sequence in the above figure is as follows: DBGEACF.

For a linear sequence (linear table), it has the concepts of direct precursor and direct successor (described in [what is a linear table?]). For example, in the mid-order ergodic sequence, the direct precursor of B is D and the direct successor is G.

The reason why we can know the direct predecessor and successor of B is that we write out the middle order traversal sequence of the binary tree according to the middle order traversal algorithm, and then say whose precursor is who and who is the successor according to this sequence.

Direct precursor and direct successor can not be obtained directly from the binary tree, because there is only the direct relationship between the parents and the child nodes in the binary tree, that is, only the address of the child node is stored in the pointer domain of the binary tree.

The demand now is that I want to be able to get the direct predecessor and successor of a node in the middle order traversal mode directly from the binary tree.

At this point, we need to use the clue binary tree.

two。 What is a clue binary tree?

Of course, we certainly need to use the pointer field of the node to save the address of the direct predecessor and immediate successor.

In fact, in the ordinary binary tree (the sequence obtained by traversing in the middle order), some nodes (nodes whose pointer domain is not empty) can be found directly. For example, the left child G of node E is the direct precursor of node E, and the right child C of node An is the direct successor of node A.

However, some nodes (the pointer domain is empty) are not feasible, for example, the direct successor of node G is E and the direct precursor is B, but such a conclusion can not be obtained in the binary tree. What should I do? We notice that both pointer fields of node G are NULL and are not used, so why don't we just use these two pointers to point to its predecessor and successor, respectively?

The direction of node G under traversal in the middle order

It's the best of both worlds, a match made in heaven! But the problem has not been solved!

Because we use the empty pointer domain to point to the precursor or successor, it is contradictory for those nodes whose pointer domain is not empty, such as node E and node B.

Since there is a contradiction, then we will find the root cause of the contradiction and resolve it.

The root cause of the contradiction is that when the pointer domain of the node is empty and not empty, the pointer points to the contradiction. That is, the contradiction between pointing to the child when the pointer is not null and pointing to the predecessor or successor when the pointer is empty.

Then we prescribe the right medicine to the case, distinguish between empty and non-empty pointer domain, and tell the pointer clearly: point to the child when it is not empty, and point to the precursor or successor when it is empty. This requires us to add a flag bit to each of the two pointers.

The node of a cue binary tree

And agree on the following rules:

When left_flag = = 0, the pointer left_child points to the left child

When left_flag = = 1, the pointer left_child points to the direct precursor

When right_flag = 0, the pointer right_child points to the right, child.

When right_flag = = 1, the pointer right_child points to the direct precursor

The nodes of the binary tree should be changed:

/ * structure of the node of the threaded binary tree * / typedef struct Node {char data; / / data field struct Node * left_child; / / left pointer field int left_flag; / / left pointer flag bit struct Node * right_child; / / right pointer field int right_flag; / / right pointer flag bit} TTreeNode

With the mark bit, everything can be sorted out. We call pointers to direct forerunners and successors as clues. The pointer with the flag bit 0 is the pointer to the child, and the pointer with the flag bit 1 is the clue.

A binary linked list tree, the node structure is like the above, we turn all the null pointers into clues, such a binary tree is the binary clue tree.

3. How to create a clue binary tree?

In an ordinary binary tree, we want to get the direct predecessor or successor of a node in a certain traversal order, and we need to traverse each time to get the traversal order before we know. In the cue binary tree, we only need to traverse once (when creating the cue binary tree), then the cue binary tree can "remember" the direct predecessor and successor of each node, and we no longer need to get the predecessor or successor through the traversal order.

According to a certain traversal way, the process of turning an ordinary binary tree into a cue binary tree is called the threading of a binary tree.

Next, we turn the following binary tree into a threaded binary tree by traversing the middle order.

The pointer with the flag bit 1 traverses the sequence in the middle order so that it points to the precursor or successor:

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 the existence of an empty pointer domain in a binary tree with n nodes. The solution is to add a marker bit to the pointer of each node, so as to make use of the empty pointer domain. The Boolean value of 0 or 1 is stored in the flag bit, which is relatively cost-effective compared with the wasted empty pointer field. And it makes the binary tree have a new characteristic-the precursor and successor relationship between the nodes in the binary tree which can be saved in a certain traversal order.

4. The realization of threading

Please note that the cue binary tree is derived from the ordinary binary tree and is obtained in some kind of traversal order. Because the clue can only be set when the predecessor and successor of a node are known, and the relationship between the precursor and the successor can not be directly reflected by 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 and the clue can be set only after the sequence with precursor and successor relationship is obtained by some traversal method.

That is, the essence of threading is to modify the null pointer of the node in the process of traversing the binary tree according to a certain traversal order, so that it points to its direct precursor or successor in that traversal order.

We introduce the principle and code implementation of four traversal methods of binary tree in [traversal principle of binary tree] and [realization of traversal of binary tree] respectively. At that time, we took printing as an example to introduce traversal. But traversing can not only do printing, but also do threading.

So, the general structure of the code is the same, we just need to replace the print code in the traversal code with threaded code and make some other changes.

The following figure is an example of three kinds of threading:

For an unthreaded binary tree, all the markers default to 0. 5%.

Example

4.1. Intermediate sequence threading

After going through the sequence according to the middle order, the following figure can be obtained:

Let's make the following clear again:

We thread it in the process of traversing the binary tree.

The order of traversal in the middle order is: left subtree > root > right subtree.

Threading modifies two things: the empty pointer field and its corresponding flag bits.

How to modify it? Set the empty pointer domain as a direct precursor or successor.

So our question becomes:

Find all empty pointer fields.

Find the node to which the empty pointer domain belongs, the direct precursor and the direct successor in the first order.

Modify the contents of the empty pointer field and its flag bits so that the pointer is called a clue.

Description: we use recursion when traversing the binary tree, so we also use it when threading.

The specific code is as follows:

/ / Global variable prev pointer to the newly accessed node TTreeNode * prev = NULL; / * indexed * / void inorder_threading (TTreeNode * root) {if (root = = NULL) {/ / if the binary tree is empty, short 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);}

4.2. Pre-order threading

After being threaded in the first order, the following figure can be obtained:

The specific code is as follows:

/ / Global variable prev pointer to the newly visited node TTreeNode * prev = NULL; / * pre-threaded * / 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);}}

4.3. Post-sequence lineation

After going through the sequence according to the post-order, the following figure can be obtained:

The specific code is as follows:

/ / Global variable prev pointer to the newly visited node TTreeNode * prev = NULL; / * followed by threading * / 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;}

The cue binary tree makes full use of the empty pointer domain in the binary tree and gives the binary tree a new feature. after a traversal, the binary tree can preserve the precursor and successor relationship between its nodes.

If we need to traverse the binary tree frequently to find the direct precursor or successor of a node, it is very appropriate to use the threaded binary tree.

The answer to the question about the principle of the clue binary tree and how to create it is shared here. I hope the above content can be of some help to you. If you still have a lot of doubts to be solved, you can follow the industry information channel for more related knowledge.

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.