二叉树的遍历算法有哪些?通常用在何处?

XIAO 2020-05-30 18:44:50 java常见问答 3503

使用过java软件开发行业的遍历数据功能的小伙伴,应该对二叉树不会陌生了,那么也是否了解过二叉树的遍历算法有哪些呢?一般都会用到哪些地方呢?

首先呢,我们来引用一下leetcode中有关于二叉树节点的相关定义。

 // Definition for binary tree
  struct TreeNode {
       int val;
       TreeNode *left;
       TreeNode *right;
       TreeNode(int x) : val(x), left(NULL), right(NULL) {}
   };

需要注意的是,以下所有的代码遵照都leetcode要求,将遍历结果储存在了vectorend里面。

首先我们来看看前序遍历。

递归实现如下所示:

class Solution {
  public:
     vector<int> preorderTraversal(TreeNode *root) {
          preorder(root);
         return end;
      }
     void preorder(TreeNode *r){
          if(!r)
          return;
         end.push_back(r->val);//先处理父节点
         postorder(r->left);//再处理左子节点
         postorder(r->right);//最后处理右子节点
         
     }
     
     vector<int> end;
 };

非递归实现如下所示:

 class Solution {
  public:
      vector<int> preorderTraversal(TreeNode *root) {
          preorder(root);
         return end;
      }
      void preorder(TreeNode *r){
          if(!r)
              return ;
         stack<TreeNode *>t;
         t.push(r);
         while(!t.empty()){
             TreeNode *root=t.top();
             t.pop();
             end.push_back(root->val);
             if(root->right)
                 t.push(root->right);//要改一起改!
             if(root->left)//堆栈是后入先出。如果要先遍历左子数,应该先把右节点压入堆栈!
                 t.push(root->left);
             
         }
     }
     
     vector<int> end;
 };

其次是后序遍历。

递归实现如下所示:

 class Solution {
  public:
     vector<int> postorderTraversal(TreeNode *root) {
         postorder(root);
          return end;
      }
      void postorder(TreeNode *r){
         if(!r)
         return;
         postorder(r->left);
         postorder(r->right);
        end.push_back(r->val);
      }
     vector<int> end;
  }

那么后序遍历比前序遍历实现起来是要稍微复杂一点的。这里就使用到了两个堆栈s,t。堆栈t用于储存正确的节点输出顺序,堆栈s可以帮助我们建立正确的t。后序遍历的输出顺序是先输出左子节点,输出右子节点之后,最后输出父节点。

非递归实现如下所示:

class Solution {
  public:
    vector<int> postorderTraversal(TreeNode *root) {
          postorder(root);
          return end;
     }
      void postorder(TreeNode *r){
          if(!r)
          return;
         stack <TreeNode *>s,t;
         TreeNode *root;
         s.push(r);
         while(!s.empty()){
             root=s.top();
             s.pop();
             t.push(root);
             if(root->left)
                 s.push(root->left);
             if(root->right)
                 s.push(root->right);
         }
         while(!t.empty()){
             end.push_back(t.top()->val);
             t.pop();
        }
     }
    
     vector<int> end;
 };

那么以上就是有关二叉树遍历算法的所有内容了,还想了解更多java常见问答的话,记得关注本站消息获取更多精彩内容。

推荐阅读:

二叉树中序遍历是如何实现?示例

重建二叉树(思路和实现)

二叉树的度是什么意思?二叉树是什么?