二叉树遍历 非递归 C++实现代码

下面我就来详细讲解一下“二叉树遍历 非递归 C++实现代码”的完整攻略。

标题

问题描述

在实现二叉树的遍历时，可以用递归方法实现。但是递归方法的缺点在于会占用过多的栈空间。因此，我们需要一种非递归的方法来遍历二叉树，以节省空间。请你给出实现这些方法的C++代码。

解答方法

在非递归方法的实现中，需要用到栈来保存节点。我们可以将树的根节点压入栈中，然后弹出根节点，将其右节点和左节点依次压入栈中。这样就能实现二叉树的前序遍历。

而中序遍历，则是先将根节点入栈，然后一路向左找到最左的节点。弹出最左节点并输出，再查找该节点的右子树。如果存在右子树，则入栈继续查找最左节点。依次重复以上步骤，直到栈为空。

后序遍历，则需要用到两个栈。第一个栈的实现方式同前序遍历。我们可以将每次弹出的节点压入第二个栈中。当第一个栈为空时，说明二叉树已经遍历完成。这时我们就可以输出第二个栈的元素。因为第二个栈中的元素是我们实际需要输出的遍历结果。

解答代码

下面是C++实现二叉树全遍历的代码。代码中Tree类型需要根据具体的情况进行修改。

// 非递归方式实现前序遍历
void preOrderTraversal(Tree *root)
{
    if (root == nullptr) return;
    stack<Tree*> s;
    s.push(root);
    Tree *cur;
    while (!s.empty()) {
        cur = s.top();
        s.pop();
        cout << cur->val << " ";
        if (cur->right) s.push(cur->right);
        if (cur->left) s.push(cur->left);
    }
}

// 非递归方式实现中序遍历
void inOrderTraversal(Tree *root)
{
    if (root == nullptr) return;
    stack<Tree*> s;
    Tree *cur = root;
    while (cur || !s.empty()) {
        if (cur) {
            s.push(cur);
            cur = cur->left;
        } else {
            cur = s.top();
            s.pop();
            cout << cur->val << " ";
            cur = cur->right;
        }
    }
}

// 非递归方式实现后序遍历
void postOrderTraversal(Tree *root)
{
    if (root == nullptr) return;
    stack<Tree*> s1;
    stack<Tree*> s2;
    s1.push(root);
    Tree *cur;
    while (!s1.empty()) {
        cur = s1.top();
        s1.pop();
        s2.push(cur);
        if (cur->left) s1.push(cur->left);
        if (cur->right) s1.push(cur->right);
    }
    while (!s2.empty()) {
        cur = s2.top();
        s2.pop();
        cout << cur->val << " ";
    }
}

示例说明

假设给定二叉树如下所示，使用上述的遍历方式，得到的结果如下：

Tree *root = new Tree(1);
root->left = new Tree(2);
root->left->left = new Tree(4);
root->left->right = new Tree(5);
root->right = new Tree(3);
root->right->left = new Tree(6);
root->right->right = new Tree(7);

preOrderTraversal(root);
// 输出结果：1 2 4 5 3 6 7

inOrderTraversal(root);
// 输出结果：4 2 5 1 6 3 7

postOrderTraversal(root);
// 输出结果：4 5 2 6 7 3 1

另外，为了进一步说明非递归遍历的实现方法，我们给出一个带注释的具体例子：

void inOrderTraversal(Tree *root)
{
    if (root == nullptr) return;
    stack<Tree*> s;
    Tree *cur = root;
    while (cur || !s.empty()) { // (1)
        if (cur) { // (2)
            s.push(cur); // 将当前节点压栈
            cur = cur->left; // 查找左子树
        } else {
            cur = s.top(); // 弹出栈中的元素
            s.pop();
            cout << cur->val << " "; // 输出当前节点
            cur = cur->right; // 查找右子树
        }
    }
}

以上代码中，注释部分标记了整个过程中的重点步骤。使用具体示例来进行理解和实践是非常有帮助的。