C++实现二叉树非递归遍历方法实例总结

介绍

二叉树是计算机科学基础中的一个重要数据结构，它具有广泛的应用。在遍历二叉树时，我们可以使用递归算法进行遍历，但递归算法可能会导致堆栈溢出，因此我们需要一种非递归的方法来遍历二叉树。本文将介绍C++实现二叉树非递归遍历的方法实例。

二叉树的遍历方式

二叉树的遍历共有三种方式：前序遍历、中序遍历和后序遍历。它们的遍历顺序如下：

1. 前序遍历：先访问根节点，再先序遍历左子树，最后先序遍历右子树。
2. 中序遍历：先中序遍历左子树，再访问根节点，最后中序遍历右子树。
3. 后序遍历：先后序遍历左子树，再后序遍历右子树，最后访问根节点。

非递归遍历方法

前序遍历

为了遍历树的每个节点，我们需要使用栈来存储尚未遍历的节点。遍历的过程如下：

1. 将根节点压入栈中。
2. 当栈不为空时，弹出栈顶元素并输出它。
3. 将当前节点的右子树压入栈中（如果存在）。
4. 将当前节点的左子树压入栈中（如果存在）。

在代码实现前序遍历时，需要定义一个栈和一个指针。指针指向当前遍历的节点，起初指向根节点。代码示例：

vector<int> preorderTraversal(TreeNode* root) {
    vector<int> res;
    if (!root) return res;
    stack<TreeNode*> s;
    s.push(root);
    while (!s.empty()) {
        TreeNode* node = s.top();
        s.pop();
        res.push_back(node->val);
        if (node->right) s.push(node->right);
        if (node->left) s.push(node->left);
    }
    return res;
}

中序遍历

同样，我们需要使用栈来存储尚未遍历的节点。遍历的过程如下：

1. 当前节点不为空时，将当前节点压入栈中，然后移向左子树。
2. 如果当前节点为空，则弹出栈顶元素并输出它，然后移向右子树。

在代码实现中序遍历时，需要定义一个栈和一个指针。指针指向当前遍历的节点，初始时指向根节点。代码示例：

vector<int> inorderTraversal(TreeNode* root) {
    vector<int> res;
    stack<TreeNode*> s;
    TreeNode* cur = root;
    while (cur || !s.empty()) {
        while (cur) {
            s.push(cur);
            cur = cur->left;
        }
        cur = s.top();
        s.pop();
        res.push_back(cur->val);
        cur = cur->right;
    }
    return res;
}

后序遍历

后序遍历的实现方法与中序遍历稍有不同，因为我们需要在访问节点之前先遍历其左、右子树。因此我们需要一个额外的指针来追踪上一访问的节点，以确定当前需要访问的节点的位置。

遍历二叉树的过程如下：

1. 将根节点压入栈中。
2. 当栈不为空时，从栈里弹出最上面的节点，并检查它是否有右子树；
3. 如果没有，则访问这个节点并将它出栈。
4. 如果有右子树，则把这个节点再次压入栈中，然后将其右子树设置为NULL，后访问左子树。
5. 重复上述操作，直到栈为空为止。

在代码实现后序遍历时，同样需要定义一个栈和一个指针，代码示例如下：

vector<int> postorderTraversal(TreeNode* root) {
    vector<int> res;
    if (!root) return res;
    stack<TreeNode*> s;
    TreeNode* pre = NULL;
    s.push(root);
    while (!s.empty()) {
        TreeNode* cur = s.top();
        if ((!cur->left && !cur->right) || (pre && (pre == cur->left || pre == cur->right))) {
            res.push_back(cur->val);
            s.pop();
            pre = cur;
        } else {
            if (cur->right) s.push(cur->right);
            if (cur->left) s.push(cur->left);
        }
    }
    return res;
}

总结

本文介绍了在C++中如何实现二叉树的非递归遍历方法，包括前序、中序和后序遍历。我们使用一个栈来存储尚未遍历的节点，并使用一个指针来跟踪遍历的过程。除了递归方法，非递归遍历的方法更加迭代的。