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; }