Shulou(Shulou.com)05/31 Report--

This article mainly explains "how to realize the binary tree structure of C language clues". The explanation content in this article is simple and clear, easy to learn and understand. Please follow the ideas of Xiaobian to study and learn "how to realize the binary tree structure of C language clues" together.

Meaning of clue binary tree

For a binary tree with n nodes, each node has pointer fields pointing to left and right children. There will be n+ 1 empty pointer fields, which do not store anything and waste memory resources.

For some occasions where binary tree traversal operations need to be performed frequently, the non-recursive traversal process of binary tree is relatively complex. Although recursive traversal is simple and clear, it will have additional overhead, and the time and space for operation are relatively wasted.

We can consider using these empty addresses to store addresses pointing to the predecessor and successor nodes of a node in some traversal order. From the addresses of these predecessor and successor nodes, you can know where to go next from the current position.

Definition of threaded binary tree

Pointer to predecessor and successor is called clue, binary linked list with clue is called clue linked list, and corresponding binary tree is called clue binary tree.

The process of traversing a binary tree in a certain order to make it a threaded binary tree is called threading.

Implementation of Thread Binary Tree Structure Thread Storage Structure of Binary Tree

In order to distinguish whether a node of a binary tree points to its child node or to its predecessor or successor node, we can add two flags to each node, Ltag, Rtag.

of which:

When Ltag is 0, it means that the node points to its left child, and when Ltag is 1, it means that the node points to its predecessor.

When Rtag is 0, it means that the node points to its right child, and when Rtag is 1, it means that the node points to its successor.

Therefore, the clue binary tree structure definition code is as follows:

typedef char BTDataType;typedef enum{Link,Thread}PointerTag;//Link is 0, Thread is 1. typedef struct BinaryTreeNode{ struct BinaryTreeNode* left; struct BinaryTreeNode* right; PointerTag LTag ; PointerTag RTag; BTDataType data;}BTNode; middle order threading of binary tree

The process of threading is the process of modifying the null pointer during traversal

The above binary tree order traversal can be obtained:

D B E A F C

The predecessor of D is empty, and the successor is B.

B is preceded by D and followed by E.

E is preceded by B and followed by A.

F is preceded by A and followed by C.

C's predecessor is F, and its successor is empty.

After cueing:

The recursive function code for in-order traversal threading is as follows:

//medium-order threaded BTNode* pre = NULL;/* global variable, always pointing to the node just visited */void InThreading(BTNode* p){ if (p == NULL) return; InThreading(p->left);//recursive left subtree threading if (! p->left)//left child is empty, left pointer points to predecessor { p->LTag = Thread; p->left = pre; } if (pre!= NULL && ! pre->right)//right child is null, right pointer points to successor pointer. //here is pre!= NULL is because the first node (node D) traversed in threaded order has no predecessor node, and pre is still NULL. { pre->RTag = Thread; pre->right = p; } pre = p;//keep pre pointing to p's precursor InThreading(p->right);}

Analysis:

if (! p->left) indicates that if the left pointer field of a node is empty, because its predecessor node has just been visited and assigned to pre, pre can be assigned to l -> left, and p-> LTag = Thread can be modified to complete the threading of predecessor nodes.

Pre is the predecessor of p, then p is the successor of pre. When pre -> right is empty, you can assign p to pre -> right and modify pre -> RTag = Thread.

void MidOrder(BTNode*p){ while (p != NULL) { while (p->LTag == Link)// { p = p->left; } printf("%c ",p->data); while (p->RTag == Thread && p->right != p) { p = p->right; printf("%c ", p->data); } p = p->right; } return;}

Analysis:

while (T->ltag == Link) starts from the root node, if the left tag is Link let it loop until you find the node marked Thread, that is, the first node to traverse, and then find the successor node according to the trailing pointer.

This is repeated until the entire binary number is traversed.

Thank you for reading, the above is "C language clue binary tree structure how to achieve" the content, after the study of this article, I believe we have a deeper understanding of how to achieve this problem in C language clue binary tree structure, the specific use of the situation also needs to be verified by practice. Here is, Xiaobian will push more articles related to knowledge points for everyone, welcome to pay attention!

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.