在计算机科学中，二叉树是一种非常重要和常见的数据结构，它具有广泛的应用，例如在搜索引擎和数据库中都有广泛的应用。在二叉树的遍历过程中，我们可以使用递归和非递归两种方法来实现。本文将介绍如何使用C++实现二叉树的非递归遍历。

一、中序遍历

中序遍历的顺序为：左子树、根节点、右子树。使用栈的非递归写法如下：

void inorder(TreeNode* root) {
  stack<TreeNode*> st;
  TreeNode* node = root;
  while(!st.empty() || node != NULL) {
    while(node != NULL) {
      st.push(node);
      node = node->left;
    }
    if(!st.empty()) {
      node = st.top();
      cout << node->val << " ";
      st.pop();
      node = node->right;
    }
  }
}

我们使用一个栈来帮助我们实现二叉树的中序遍历。将树的根节点入栈，然后将栈顶元素出栈并输出，再将当前节点的右子树和左子树分别入栈。如果当前节点为空且栈为空，则中序遍历完成。

二、前序遍历

前序遍历的顺序为：根节点、左子树、右子树。使用栈的非递归写法如下：

void preorder(TreeNode* root) {
  if(root == NULL) return;
  stack<TreeNode*> st;
  st.push(root);
  while(!st.empty()) {
    TreeNode* node = st.top();
    cout << node->val << " ";
    st.pop();
    if(node->right != NULL) {
      st.push(node->right);
    }
    if(node->left != NULL) {
      st.push(node->left);
    }
  }
}

我们使用一个栈来帮助我们实现二叉树的前序遍历。首先将根节点入栈，然后将栈顶元素出栈并输出，再将当前节点的右子树和左子树分别入栈。

三、后序遍历

后序遍历的顺序为：左子树、右子树、根节点。使用栈的非递归写法如下：

void postorder(TreeNode* root) {
  stack<TreeNode*> st;
  TreeNode* node = root;
  TreeNode* last_visited = NULL;
  while(!st.empty() || node != NULL) {
    while(node != NULL) {
      st.push(node);
      node = node->left;
    }
    TreeNode* tmp = st.top();
    if(tmp->right == NULL || tmp->right == last_visited) {
      cout << tmp->val << " ";
      st.pop();
      last_visited = tmp;
    } else
      node = tmp->right;
    
  }
}

我们使用一个栈来帮助我们实现二叉树的后序遍历。我们先将根节点入栈，并且使用一个指针记录上一个访问的节点。当栈顶元素没有右子树或者右子树已经被访问过的时候，我们就可以将其弹出并输出。如果当前节点有右子树，则将其压入栈中并将当前节点指向右子树。

总结

本文介绍了如何使用C++实现二叉树的非递归遍历。中序遍历、前序遍历和后序遍历是二叉树最重要的三种遍历方式，在实际开发中都有广泛的应用。通过本文的介绍，相信读者们已经掌握了如何实现二叉树的非递归遍历，并且可以根据需要灵活的使用二叉树的遍历方式。

相似文章

友情链接
• 网站定制开发
• 帮你发
• 小蓄群站获客
• 雅圣洁家政