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

- Reach the node A, Access to the node A, To traverse the A The left subtree
- Reach the node B, Access to the node B, To traverse the B The left subtree
- 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

- 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

- Reach the node C, Access to the node C. To traverse the C The left subtree
- 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

- 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

std::cout << t->val << std::endl; // Access to the node

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

- Reach the node A, node A There's a Zuozi tree , Traversal node A The left subtree
- Reach the node B, node B There's a Zuozi tree , Traversal node B The left subtree
- 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

- visit B node , Traverse B The right subtree of the node
- 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

- arrive A node , visit A node , Traverse A The right subtree of the node
- arrive C node , Traverse C The left subtree of the node
- 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

- arrive C node , visit C node , Traverse C The right subtree
- 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 .

- 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

- Reach the node A, Traverse A The left subtree
- Reach the node B, Traverse B The left subtree
- 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

- 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

- Access to the node B, Back to the node B The root node A
- Reach the node A, Access to the node A The right subtree
- Reach the node C, Traversal node C The left subtree
- 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

- Reach the node C, Traversal node C The right subtree
- 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

- Reach the node C, Access to the node C

- node C Traverse complete , It means that nodes A Right subtree traversal complete , Back to the node A

- 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 .