当前位置:网站首页>This paper understands three traversal methods of binary tree

This paper understands three traversal methods of binary tree

2021-11-25 17:56:43 High performance architecture exploration

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

版权声明
本文为[High performance architecture exploration]所创,转载请带上原文链接,感谢
https://chowdera.com/2021/11/20211109094145400Z.html

随机推荐