This paper understands three traversal methods of binary tree

It is said that ： either progress or be washed backward , move forward , or you 'll fall behind ; The heart is like a plain horse , Easy to put but hard to collect . This sentence is for programmers , Experience more . This line has become more and more voluminous , Be ready ,. Binary tree , In the interview , It's already a must-have appetizer . In the interview questions related to binary tree , Traversal is a common test topic . This paper will start with the traversal of binary tree , This paper analyzes and explains the traversal of binary tree from the perspective of recursion and non recursion .

Traverse

*

Binary tree traversal refers to starting from the root node , Access all the nodes in the binary tree in some order , Make each node accessible and only once .

*

Traversal of binary tree , Yes 「 The first sequence traversal 」「 In the sequence traversal 」 as well as 「 Subsequent traversal 」 Three . Figure 1

The first order of the above three traversal methods 、 There are three ways of middle order and post order , Is the parent node relative to the child node . If the parent node precedes the child node , So it's a preorder traversal . If the child node precedes the parent node , So it's post order traversal . For child nodes , If you left the node first , Then the parent node , Then the right node , So it's middle order traversal .

Such as 【 Figure 1 】 Binary tree shown . The three traversal results are as follows ：

The first sequence traversal : A->B->D->E->C->F->G

In the sequence traversal : D->B->E->A->F->C->G

Subsequent traversal : D->E->B->F->G->C->A

To make it easier to understand the code , Let's first define the node of the tree ：

struct TreeNode {
TreeNode *left;
TreeNode *right;
int val;
};

The first sequence traversal

*

Definition ： Access the parent node first , And then I go through the left subtree , Finally, traverse the right subtree .

*

recursive

I believe that recursive traversal will be easy for everyone to write , And bugfree. Because the implementation code is very simple . Figure 2 The first sequence traversal

In the picture above 【 Figure 2 】 in , Use recursive traversal , The left subtree and the right subtree are treated as one tree . The code is as follows ：

void PreOrder(TreeNode *root) {
if (!root) {
return;
}

//  Traverse the root node ( Here is only output , Readers can also deal with it according to their actual needs , Such as storage )
std::cout << root->val << std::endl;

//  Traverse left subtree
PreOrder(root->left);

//  Traversal right subtree
PreOrder(root->right);
}

Non recursive

In non recursive operations , We still visit the root node first , And then I go through the left subtree , Then traverse the right subtree . Figure 3 The first sequence traversal

1. Reach the node A, Access to the node A, To traverse the A The left subtree
2. Reach the node B, Access to the node B, To traverse the B The left subtree
3. Reach the node D, Access to the node D, Because of the node D A seedless tree , So nodes D Traverse complete
• node D Traverse complete , It means that nodes B Complete the left subtree traversal of , So go through the nodes B The right subtree
4. Reach the node E, Access to the node E. Because of the node E A seedless tree , So nodes E Traverse complete
• node E Traverse complete , It means that nodes B Right subtree traversal complete , It also indicates that nodes B The traversal of the subtree is complete
• Start traversing nodes A The right subtree
5. Reach the node C, Access to the node C. To traverse the C The left subtree
6. Reach the node F, Access to the node F. Because of the node F A seedless tree , So nodes F Traverse complete
• node F Traverse complete , It means that nodes C Complete the left subtree traversal of , So start traversing the nodes C The right subtree
7. Node to G, Access to the node G. Because of the node G A seedless tree , So nodes G Traverse complete
• node G Traverse complete , It means that nodes C Right subtree traversal complete , Then it indicates that the node C Traverse complete
• node C Traverse complete , It means that nodes A Right subtree traversal complete , This in turn means that nodes A Traverse complete , So in order to A The tree traversal for the root node is complete .

Traversing a binary tree in a non recursive manner , Additional data structure stacks need to be introduced (stack), The basic process is as follows ： 1、 Apply for a stack stack, Then press the head node into stack in .

2、 from stack Pop up the top of the stack node , Print

3、 Turn its right child node （ Not empty words ） Press in first stack in

4、 Turn its left child node （ Not empty words ） Push the stack in .

5、 Repeat the steps 2、3、4, until stack It's empty , The whole process is over .

The code is as follows ：

void PreOrder(TreeNode *root) {
if (!root) {
return;
}

std::stack<TreeNode*> s;
s.push(root); //  step 1

while (!s.empty()) {
auto t = s.top();
s.pop();// Out of the stack

if (t->right) {
s.push(t->right); //  Corresponding steps 3
}

if (t->left) {
s.push(t->left); //  Corresponding steps 4
}
}
}

In the sequence traversal

*

Definition ： First traverse the left subtree , Access the root node , Traversal right subtree

*

recursive Figure 4 In the sequence traversal

In the picture above 【 Figure 4 】 in , Use recursive traversal , The left subtree and the right subtree are treated as one tree . The code is as follows ：

void InOrder(TreeNode *root) {
if (!root) {
return;
}

//  Traverse left subtree
InOrder(root->left);

//  Traverse the root node ( Here is only output , Readers can also deal with it according to their actual needs , Such as storage )
std::cout << root->val << std::endl;

//  Traversal right subtree
InOrder(root->right);
}

The recursive code traversed in the above order , Compared with preorder traversal , Just put the behavior of accessing the root node between traversing the left and right subtrees .

Non recursive

In non recursive operations , We still traverse the left subtree first , Then access the root node , Finally, the way to traverse the right subtree . Figure 5 In the sequence traversal

1. Reach the node A, node A There's a Zuozi tree , Traversal node A The left subtree
2. Reach the node B, node B There's a Zuozi tree , Traversal node B The left subtree
3. Reach the node D, node D A seedless tree , visit D node
• because D A seedless tree , signify B Complete the left subtree traversal of , Then go back to B node
4. visit B node , Traverse B The right subtree of the node
5. Reach the node E, node E A seedless tree , Access to the node E
• E Node traversal is complete , It means to B Traversal of the subtree of the root is complete , go back to A node
6. arrive A node , visit A node , Traverse A The right subtree of the node
7. arrive C node , Traverse C The left subtree of the node
8. arrive F node , because F Node has no subtree , Therefore access F node .
• because F Node has no subtree , signify C Node's left subtree traversal is complete , go back to C node
9. arrive C node , visit C node , Traverse C The right subtree
10. Reach the node G, because G A seedless tree , Because access nodes G
• G Node traversal is complete , signify C Node's right subtree traversal is complete , Which means A Node's right subtree traversal is complete , From means to A The traversal of the binary tree with the node as the root is completed .

In the sequence traversal , Additional auxiliary data structure stacks are also required .

1. Put the root node on the stack 2、 If the root node has a left subtree , Put the root node of the left subtree on the stack 3、 Repeat step 1 and 2. Continue to traverse the left subtree 4、 Pop nodes from the stack , Visit , And then I go through the right subtree ( Repeat step 1 and 2) 5、 If the stack is empty , The traversal is completed

The code is as follows ：

void InOrder(TreeNode *root) {
if (!root) {
return;
}

std::stack<TreeNode*> s;
auto p = root;

while (!s.empty() || p) {
if (p) { //  step 1 and 2
s.push(p);
p = p->left;
} else { //  step 4
auto t = s.top();
std::cout << t->val << std::endl;
p = t->right;
}
}
}

Subsequent traversal

*

Definition ： First traverse the left subtree , Traversing right subtree again , Finally, the root node is accessed

*

recursive Figure 6 After the sequence traversal

void PostOrder(TreeNode *root) {
if (!root) {
return;
}

//  Traverse left subtree
PostOrder(root->left);

//  Traversal right subtree
PostOrder(root->right);

//  Traverse the root node ( Here is only output , Readers can also deal with it according to their actual needs , Such as storage )
std::cout << root->val << std::endl;
}

The above is the recursive writing of subsequent traversal , Compare write preorder traversal 、 Recursive traversal of middle order traversal and subsequent traversal , Most of the code is the same , The only difference is 「 Access the code location of the root node 」 Dissimilarity ：

The first sequence traversal ：「 Access the root node first , And then I go through the left subtree , Finally, traverse the right subtree 」 In the sequence traversal ：「 First traverse the left subtree , Then access the root node , Finally, traverse the right subtree 」 After the sequence traversal ：「 First traverse the left subtree , And then I go through the right subtree , Finally, the root node is accessed 」

Non recursive

In non recursive operations , We still traverse the left subtree first , Then access the root node , Finally, the way to traverse the right subtree . Figure 7 Subsequent traversal

1. Reach the node A, Traverse A The left subtree
2. Reach the node B, Traverse B The left subtree
3. Reach the node D, because D A seedless tree , Then access the node D
• node D A seedless tree , It means that nodes B Complete the left subtree traversal of , Then go through B The right subtree
4. Reach the node E, because E A seedless tree , Then access the node E
• node E A seedless tree , It means that nodes B Right subtree traversal complete , Back to the node B
5. Access to the node B, Back to the node B The root node A
6. Reach the node A, Access to the node A The right subtree
7. Reach the node C, Traversal node C The left subtree
8. Reach the node F, Due to the node F A seedless tree , So access nodes F
• node F The visit is complete , signify C Node's left subtree traversal is complete , So go back to the node C
9. Reach the node C, Traversal node C The right subtree
10. Reach the node G, Due to the node G A seedless tree , Because access nodes G
• node G The visit is complete , signify C Node's right subtree traversal is complete , Back to the node C
• node C Traverse complete , It means that nodes A Right subtree traversal complete , Back to the node A
1. node A Right subtree traversal complete , Access to the node A

Traversing a binary tree in a non recursive manner , Additional data structure stacks need to be introduced (stack), The basic process is as follows ： 1、 Apply for two stacks stack, Then press the head node into the specified position stack in .

2、 from stack Pop up the top of the stack node , Put it on another stack

3、 Turn its left child node （ Not empty words ） Press in first stack in

4、 Turn its right child node （ Not empty words ） Push the stack in .

5、 Repeat the steps 2、3、4, until stack It's empty .

6、 Repeat access to another stack , Until the stack is empty

void PostOrder(TreeNode *root) {
if (!root) {
return;
}

std::stack<TreeNode*> s1;
std::stack<TreeNode*> s2;

s1.push(root);

while (!s1.empty()) {
auto t = s1.top();
s1.pop();
s2.push(t);

if (t->left) {
s1.push(t->left);
}

if (t->right) {
s1.push(t->right);
}
}

while (!s2.empty()) {
auto t = s2.top();
s2.pop();
std::cout << t->val << std::endl;
}
}

Conclusion

For binary trees , The so-called traversal , It refers to accessing each node in turn along a route , And only one visit was made . Traversal of binary tree , It is one of the common face algorithms in the interview , Be sure to understand it , When necessary , Need to recite , Even muscle memory .