二叉树的递归和迭代遍历-C++版

朴灿烈づ我的快乐病毒、 2022-11-05 03:22 181阅读 0赞

### 文章目录 ###

*   *   *  1. 前序遍历
         *  2. 中序遍历
         *  3. 后序遍历
         *  4. 层序遍历
         *  5. 测试函数

// binary_tree.h
    // 结点
    struct TreeNode { 
      int val;
      TreeNode *left;
      TreeNode *right;
    
      TreeNode(int value) : val(value), left(nullptr), right(nullptr) { }
    };
    
    /********************** 二叉树增加结点 **********************/
    void addTreeNode(TreeNode *&root, TreeNode *node) { 
      if (node->val <= root->val && root->left) { 
        addTreeNode(root->left, node);
      } else if (node->val <= root->val && root->left == nullptr) { 
        root->left = node;
      } else if (root->right) { 
        addTreeNode(root->right, node);
      } else { 
        root->right = node;
      }
    }

### 1. 前序遍历 ###

/********************** 前序遍历-递归版 **********************/
    void preorderRecursive(TreeNode *root) { 
      if (nullptr == root) { 
        return;
      }
      cout << root->val << " ";
      preorderRecursive(root->left);
      preorderRecursive(root->right);
      return;
    }
    
    /********************** 前序遍历-迭代版 **********************/
    void preorderIterative(TreeNode *root) { 
      if (nullptr == root) { 
        return;
      }
      std::stack<TreeNode *> stk;
      TreeNode *node = root;
      stk.push(node);
      while (!stk.empty()) { 
        node = stk.top();
        stk.pop();
        cout << node->val << " ";
        if (node->right) { 
          stk.push(node->right);
        }
        if (node->left) { 
          stk.push(node->left);
        }
      }
      return;
    }

### 2. 中序遍历 ###

/********************** 中序遍历-递归版 **********************/
    void inorderRecursive(TreeNode *root) { 
      if (root) { 
        inorderRecursive(root->left);
        cout << root->val << " ";
        inorderRecursive(root->right);
      }
      return;
    }
    
    /********************** 中序遍历-迭代版 **********************/
    void inorderIterative(TreeNode *root) { 
      std::stack<TreeNode *> stk;
      TreeNode *node = root;
      while (node || !stk.empty()) { 
        if (node) { 
          stk.push(node);
          node = node->left;
        } else { 
          node = stk.top();
          stk.pop();
          cout << node->val << " ";
          node = node->right;
        }
      }
      return;
    }

### 3. 后序遍历 ###

/********************** 后序遍历-递归版 **********************/
    void postorderRecursive(TreeNode *root) { 
      if (root) { 
        postorderRecursive(root->left);
        postorderRecursive(root->right);
        cout << root->val << " ";
      }
      return;
    }
    
    /********************** 后序遍历-迭代版 **********************/
    void postorderIterative(TreeNode *root) { 
      if (nullptr == root) { 
        return;
      }
      std::stack<TreeNode *> stk;
      std::vector<int> result;
      TreeNode *node = root;
      stk.push(node);
      while (!stk.empty()) { 
        node = stk.top();
        stk.pop();
        result.emplace(result.begin(), node->val);
        if (node->left) { 
          stk.push(node->left);
        }
        if (node->right) { 
          stk.push(node->right);
        }
      }
      std::copy(result.begin(), result.end(), std::ostream_iterator<int>{ cout, " "});
      return;
    }

### 4. 层序遍历 ###

/********************** 层序遍历-迭代版 **********************/
    void levelorderTraversal(TreeNode *root) { 
      if (nullptr == root) { 
        return;
      }
      std::queue<TreeNode *> que;
      TreeNode *node = root;
      que.push(node);
      while (!que.empty()) { 
        node = que.front();
        que.pop();
        cout << node->val << " ";
        if (node->left) { 
          que.emplace(node->left);
        }
        if (node->right) { 
          que.emplace(node->right);
        }
      }
      return;
    }

### 5. 测试函数 ###

void binaryTreeTest() { 
      TreeNode *root = new TreeNode(3);
      std::vector<int> treeElem{ 1, 2, 4, 5};
    
      for (int i{ }; i < treeElem.size(); ++i) { 
        TreeNode *node = new TreeNode(treeElem.at(i));
        addTreeNode(root, node);
      }
    
      cout << "\ntraversal result: " << endl;
      cout << std::string(32, '*') << endl;
    
      // preorderRecursive(root); // 3 1 2 4 5
      // preorderIterative(root); // 3 1 2 4 5
    
      // inorderRecursive(root); // 1 2 3 4 5
      // inorderIterative(root); // 1 2 3 4 5
    
      // postorderRecursive(root); // 2 1 5 4 3
      // postorderIterative(root); // 2 1 5 4 3
    
      levelorderTraversal(root); // 3 1 4 2 5
    
      cout << endl;
      cout << std::string(32, '*') << endl;
    
      return;
    }