Data structure – tree: threading and preorder construction traversal of binary tree

1. Name definition

do something: perform a task

renew: value update

preOrder: Preorder traversal

change-type: deformation operation, which converts the binary tree Tree type to List type

root: root node, that is: the first binary tree node (node) in main

Two, understanding

This time I learned the preorder binary tree and its traversal. There are many similarities between this and the in-order traversal, so I won’t go into details about the same places. For details, see Data Structure-Trees: Threading of Binary Trees and In-Order Construction Traversal

First of all, we still need to build the data structure of the tree and build a binary tree

#include"iostream"
#include"cstdlib"
#include"cstring"

#define ElemType char

using namespace std;

typedef struct TreeNode
{
    ElemType data;
    struct TreeNode* lchild;
    struct TreeNode* rchild;

    int ltag;
    int rtag;
}TreeNode;


void createTree(TreeNode** T, ElemType* 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);
}
}


int main(void)
{
TreeNode* T;
int index = 0;
TreeNode* pre = nullptr;
char data[] = "ABD##E##CF##G##";
createTree( &T, data, &index);
\t
return 0;
}

For preorder traversal, its basic logic is similar to that of inorder traversal, but there are some differences. The key lies in the transformation function preThreadTree().

For the above binary tree, perform preorder traversal (root-left-right), and the obtained List is: A-B-D-E-C.

Now perform the change-type operation on it.

3. Code implementation

1.1 preThreadTree(TreeNode* T, TreeNode** pre_node): It is used to convert the binary tree of Tree type to the binary tree of List type.

void preThreadTree(TreeNode* T, TreeNode** pre_node)
{
    if(T != nullptr)
    {
        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;
if (T->ltag == 0) // have left-child
{
//if T->lchild != nullptr, execute this function, or execute the "if-program"
preThreadTree(T->lchild, pre_node);
}
//*pre_node = T;

\t\t
//after you have finished manipulating the left-child, then you should deal with the
//right-child
preThreadTree(T->rchild, pre_node);
        
    }
}

int main(void)
{
TreeNode* T;
int index = 0;
TreeNode* pre = nullptr;
char data[] = "ABD##E##CF##G##";
createTree( &T, data, &index);
preThreadTree(T, & pre);
pre->rtag = 1;
pre->rchild = nullptr;
\t
return 0;
}

1.2 Analysis

The relationship between preorder traversal and inorder traversal is the same as the relationship between the three recursive traversals. It’s just that the position between “doing things” and “updating” is different. The construction logic of inorder traversal is:

inThreadTree(T->lchild, pre_node);

//do something

inThreadTree(T->rchild, pre_node);

The logic of preorder traversal is:

//do something

inThreadTree(T->lchild, pre_node);

inThreadTree(T->rchild, pre_node);

But what needs to be noted here is that because do something is before renew, it may cause a node to be empty, resulting in a segment error, so it needs to be judged when renew.

Analyzed by the binary tree model mentioned above. The input in the main function is root. Enter to execute if judgment

Since A != nullptr and A->lchild == B != nullptr, does not execute

Since pre_node is initialized to nullptr in main, the second if is not executed

Update pre_node to T, start recursion, and don’t forget to judge:

1. When the left pointer space of T is 0, it means that it points to the next node. Go to preThreadTree(T->lchild, pre_node) until you find the leftmost node. The logic here is the same as inOrder

2. After the if judgment, execute preThreadTree(T->rchild, pre_node)

Fourth, the complete framework code

#include"iostream"
#include"cstdlib"
#include"cstring"

/*
This is against to the inOrder binary-tree which is
called "previous clue-binary tree(preorder clue binary tree)". The basic logic is the same as the inOrder

The basic logic of it is that, if the node which is pointed has no left-child and right-child
then, this pointer point to the the previous node and behind node. Or, point to the
corresponding child.
*/

using namespace std;

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 preThreadTree(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)
{
//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;
if (T->ltag == 0) // have left-child
{
//if T->lchild != nullptr, execute this function, or execute the "if-program"
preThreadTree(T->lchild, pre_node);
}
//*pre_node = T;

\t\t
//after you have finished manipulating the left-child, then you should deal with the
//right-child
preThreadTree(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* getNext(TreeNode* node)
{
if (node->rtag == 1||node->ltag == 1)
{
return node->rchild;
}
else
{
return node->lchild;
}
\t
}


int main(void)
{
TreeNode* T;
int index = 0;
TreeNode* pre = nullptr;
char data[] = "ABD##E##CF##G##";
createTree( &T, data, &index);
preThreadTree(T, & pre);
pre->rtag = 1;
pre->rchild = nullptr;
for (TreeNode* node = T; node != nullptr; node = getNext(node))
{
cout << node->data;
}
cout << endl;
return 0;
}