1. Name definition
node: node
root node: root node
front-node/previous node: predecessor node/predecessor
behind-node/back-node: successor node/successor
inOrder-traverse: in-order traversal
pointer space: pointer space
left-pointer space: left pointer space
right-piinter space: right pointer space
List: chained binary tree
Tree: tree-like binary tree
binary tree: binary tree
clue-binary tree: clue binary tree
recursion-theory: recursion theory
tag-assignment theory: tag assignment principle
Two, understanding
When threading a binary tree, you must first understand the principle of its construction. That is: convert the binary tree of the tree structure into a chain structure. For the preorder of a binary tree, the construction principles of inorder and postorder are slightly different, but the underlying logic is the same. Here we use the construction of inorder to analyze.
First of all, for the binary tree above, our logical order of inorder traversal is: 4-2-5-1-3. Therefore, we build a structure similar to a linked list in such an order, which we define as a List, and at the same time define each part of the linked structure List as a “node”, where the structure of a node is as follows:
#define ElemType char // define the data type
typedef struct TreeNode
{
ElemType data; // this parameter is used to save the information
struct TreeNode* lchild; // create one pointer which is used to point to the left-child
struct TreeNode* rchild;
int ltag; // used to record the condition of the left and right node if it is nullptr
int rtag;
}TreeNode;
First of all, we need to clarify the basic logic of in-order binary tree. For a node node, it has a left child and a right child respectively, which are managed by pointers lchild and rchild respectively. For a node, it has corresponding left and right pointer spaces (pointer space), which contain pointers lchild and ltag. Among them, lchild is used to manage the child pointing to the left, and ltag is used to record the situation of being a child. If the child is empty, then ltag=1; vice versa.
If its left child is nullptr, then lchild points to the previous node in the List, and ltag = 1. Otherwise, point to this node with ltag = 0.
If its right child is nullptr, then rchild points to the next node in the List, and rtag = 1. Otherwise, just this node, with rtag = 0.
That is: Except for the ltag and rtag in the node on the edge of the List, the assignment of the tag in the middle node follows this principle. When the node points to the node in the Tree, tag = 0; when the node points to the node in the List, tag = 1.
The threaded chain graph is shown in the figure:
In the chain structure diagram, the black line indicates the link relationship of each node in the Tree, and the red line indicates the link relationship of each node in the List based on the assignment principle. Therefore, the basic steps for threading a binary tree are:
(1) Use the corresponding traversal method to arrange all nodes into a List structure
(2) Connect the connection relationship of each node in the Tree structure
(3) Use the “tag assignment principle” to assign the tag in the pointer space, and only want the front-node and back-node respectively
After understanding its basic construction principle, we started to implement it with code.
3. Code implementation
1.creatTree() function: used to create a binary tree with a Tree structure
1.1 Construction of binary tree
void createTree(TreeNode**T, ElemType* data, int* index)
{
ElemType ch; //used to record the information in the data
ch = data[*index]; // assign
*index + = 1; // move the pointer
if(ch == '#') //define the '#' is empty
{
*T = nullptr;
}
else
{
*T = (TreeNode*)malloc(sizeof(TreeNode));
(*T)->data = ch;
(*T)->ltag = 0; // initate
(*T)->rtag = 0;
createTree( & amp;((*T)->lchild),data,index);
createTree( & amp;((*T)->rchild),data,index);
}
}
int main(void)
{
TreeNode* root; //create the root of the tree
int index = 0; //define one pointer in order to locate the information you want to save
//TreeNode* pre = nullptr; //
char data[] = "ABD##E##CF##G##";
createTree( & amp; root, data, & amp; index);
//pre->rtag = 1;
//pre->rchild = nullptr;
return 0;
}
1.2 Analysis
Use recursion to implement tree construction. There are 3 parameters passed into the function, among which T is accepted by the secondary pointer because the lchild and rchild in a node need to be changed. (T here does not refer to the root of the binary tree. When using recursion, we need to make sure that every three nodes can form a binary tree, and the logic of this algorithm is based on this. Each time a binary tree is processed, and a recursion is performed)
The basic logic here is that every time the function is entered, the data information in a data is read and assigned to the variable storing the data in the node. Make a judgment before this:
If the read is empty (‘#’), the assignment is null pointer nullptr. Otherwise, assign and initialize the tag, and enter recursion to continuously judge and assign the next child node. When the left and right children are empty, they are assigned to nullptr by two recursive functions, and this node is the tail node. Here, an array is passed into the function, and an integer-like pointer is defined in the main function to be used as data.
2.inThreadTree() function: Convert the binary tree of the Tree structure to the binary tree of the List structure
2.1 Conversion of binary tree
void inThreadTree(TreeNode* T, TreeNode** pre_node)
{
//pre_node stands for the previous node in the List construction
//you can also think it as the fton-node
if(T != nullptr)
{
inThreadTree(T->lchild, pre_node);
if(T->lchild == nullptr)
{
T->ltag = 1;
T->lchild = *pre_node;
}
if(*pre_node != nullptr & amp; & amp; (*pre_node)->rchild == nullptr)
{
(*pre_node)->rtag = 1;
(*pre_node)->rchild = T;
}
*pre_node = T;
inThreadTree(T->rchild, pre_node);
}
}
int main(void)
{
TreeNode* T;
int index = 0;
TreeNode* pre = nullptr; // define the front-node
char data[] = "ABD##E##CF##G##";
createTree( &T, data, &index);
//change the tree into the list
inThreadTree(T, & pre);
pre->rtag = 1;
pre->rchild = nullptr;
\t
return 0;
}
2.2 Analysis
Initialization: In the main function, initialize a pre to include the information of the previous node in the Tree structure, mainly to find the previous node when recursive. The initial question is empty.
The function receives two parameters, one is the current node, and the other is the previous node (previous node), which should be distinguished from the predecessor in the List structure. This can be compared to the construction of a linked list. In order to connect the linked list, there must be pointers to the previous node and the next node. When the function is used for the first time, that is, when the function is called in main, the node passed in is the root node. The next step is to enter the if judgment. When T==nullptr, that is, when the root node is empty, the tree is empty, and there is no need to continue. The if here is used to prevent segmentation faults. Then comes the analysis of the main part in the if.
The first is to enter recursion, starting from left to right to traverse the deformation. inThreadTree(T->child, pre_node) performs recursion, passing in the left child of a node and the previous node, until the situation of T == nullptr occurs, that is, the leftmost node is found, and then the recursion begins to return. At this time T, pre_node and pre_node->rchild form a unary binary tree.
if (T->lchild == nullptr)
{
//is the left-child is nullptr, assign the ltag is “1”
T->ltag = 1;
//and then let the left-child point to the previous node
T->lchild = *pre_node;
}
This if judges that when the left child of a node is empty, according to the tag-assignment theory, the left pointer area in the node should point to the previous node, and ltag = 1, so the processing is completed. The left child of the unary binary tree. Then judge the root of this unary binary tree, that is, pre_node. If its right child is also empty, use the tag assignment principle again; if the part is empty, assign pre_node to T and start the next recursion.
inThreadTree(T->rchild, pre_node), process the right child. The principle is the same as above. Let’s analyze the example just now:
1. Start to pass in T = 1 for recursion. Since 1->lchild != nullptr, enter a recursive loop. At the same time, there is *pre_node = T, that is, pre_node is constantly updated to the lchild of the current node, thus realizing the update of a unary binary tree.
2. When recursing to T = 4, 4->lchild == nullptr, the left pointer area of 4 is “tag assignment principle”. Order: 4->ltag = 1; T->lchild = *pre_node That is: the left pointer space points to the previous node, namely: pre_node. Therefore, the current structure is: List: 4->2
3. Enter the second if judgment. When pre_node != nullptr (obviously 2 != nullptr), and (*pre_node)->rchild == nullptr at the same time, since 2->5 != nullptr, the if is not executed.
4. Execute *pre_node = T to update the code, the previous node (previous node) is T = 4, so assign pre_node = 4; here also explains why
A secondary pointer needs to be passed in order to change its value
5. Execute inThreadTree(T->rchild, pre_node). (Now pre_node is updated to 4). Execute the next step of recursion. Pass in the right child, that is, execute inThreadTree(5, 2). Then there is the process of executing the appeal again.
It should be noted that in mian there are:
pre->rtag = 1;
pre->rchild = nullptr;
This is because the pointer space on both sides of the node at the head and tail is not assigned, so it needs to be added here.
3. getFirst(): Find the leftmost node
3.1 Code
TreeNode* getFirst(TreeNode* T)
{
while(T->ltag == 0)
{
T = T->lchild;
}
return T;
}
3.2 Analysis
This should not need to be explained too much, I can understand it myself.
4. getNext(): Mainly used in conjunction with getFirst to traverse the binary tree.
4.1 Code
TreeNode* getNext(TreeNode* node)
{
if(node->rtag == 1)
{
return node->rchild;
}
else
{
return getFirst(node->rchild);
}
}
Fourth, the complete code framework
#include "iostream"
#include "cstdlib"
#include "cstring"
using namespace std;
/*
Clue-Binary Tree (binary tree clue)
1.Define: Order the binary tree in the linear construction at a regular way
We achieve it using inOrder as an example. Let every node has one front-node
and after-node except the head and tail.
2. Regulation: add two new pointers: ltag and rtag.
When "ltag == 0", lchild points to the left-child(means it is not nullptr)
When "ltag == 1", lchild points to the front_node(means it is nullptr)
When "rtag == 0", rchild points to the right-child(means it is not nullptr)
When "rtag == 1", rchild points to the behind_node(means it is nullptr)
*/
typedef struct TreeNode
{
char data;//used to save the data
struct TreeNode* lchild; // child pointers
struct TreeNode* rchild;
int ltag;//used to record the condition of the left and right node
int rtag;
}TreeNode;
//create the binary-tree
//the basic logic is similar to the previous achievement
//but you shuold initate the ltag and rtag
void createTree(TreeNode** T, char* data, int* index)
{
char ch;
ch = data[*index];
*index + = 1;
if (ch == '#')
{
*T = nullptr;
}
else
{
*T = (TreeNode*)malloc(sizeof(TreeNode));
(*T)->data = ch;
(*T)->ltag = 0;
(*T)->rtag = 0;
//we define the "false" means the node is not visited
createTree( & amp;((*T)->lchild), data, index);
createTree( & amp;((*T)->rchild), data, index);
}
}
/*
the inOrder traverse Clue-Binary tree
change the binary-tree into the clue-binary tree
*/
void inThreadTree(TreeNode* T, TreeNode** pre_node)
{
/* Before you write the tree, you should change your mind first or in order words, you
should transform the perspective you see the binary-tree. Every time you manipulate the binary-tree,
You should see the "left-child", "middle-child" and "right-child" as one binary-tree because you
will use recursion to continue manipulating the next node. So, the next step is delivering the
left-child or the right-child to the function.
*/
//
//
//There, "T" is the root of the binary tree
//traverse the tree from the left to middle and then the right.
//because the root node doesn't have previous node, so the pre_node is "nullptr"
//FRONT-NODE
if (T != nullptr)
{
//if T->lchild != nullptr, execute this function, or execute the "if-program"
inThreadTree(T->lchild, pre_node);
/*
There, we use recursion to achieve the creation of the clue-binary tree.
The basic logic is: deliver T->lchild and pre_node to the function's parameters: T and pre_node
until the T->lchild == nullptr. So, you shuold know that the node "T" is no longer the root ot the tree.
"T" is the next child node
"pre_node" is the front-node
*/
if (T->lchild == nullptr)
{
//is the left-child is nullptr, assign the ltag is "1"
T->ltag = 1;
//and then let the left-child point to the previous node
T->lchild = *pre_node;
}
//BEHIND-NODE
//after you finish manipulating the lchild, you should deal with the previous node.
if (*pre_node != nullptr & amp; & amp; (*pre_node)->rchild == nullptr)
{
(*pre_node)->rtag = 1;
(*pre_node)->rchild = T;
}
*pre_node = T;
//after you have finished manipulating the left-child, then you should deal with the
//right-child
inThreadTree(T->rchild, pre_node);
}
}
//traverse the clue-binary tree
//because the binary-tree is linear construction now, you can find the head of the list
TreeNode* getFirst(TreeNode* T)
{
//find the node whose ltag is 1 which means its front-node is nullptr
//So, that means this is the head because we visit the tree from the left to the middle and then the right
while (T->ltag == 0)
{
T = T->lchild;
}
return T;
}
TreeNode* getNext(TreeNode* node)
{
if (node->rtag == 1)
{
return node->rchild;
}
else
{
return getFirst(node->rchild);
}
}
int main(void)
{
TreeNode* T;
int index = 0;
TreeNode* pre = nullptr;
char data[] = "ABD##E##CF##G##";
createTree( &T, data, &index);
inThreadTree(T, & pre);
pre->rtag = 1;
pre->rchild = nullptr;
for (TreeNode* node = getFirst(T); node != nullptr; node = getNext(node))
{
cout << node->data;
}
cout << endl;
return 0;
}