C++二叉树的前序中序后序非递归实现方法详细讲解

二叉树是一种常见的树形数据结构，可以用于解决很多问题，在二叉树的遍历中，常见的有前序遍历、中序遍历和后序遍历。本文将详细讲解如何使用C++来实现二叉树的前序中序后序非递归遍历。

二叉树的遍历方式

• 前序遍历：先输出根节点，再遍历左子树和右子树
• 中序遍历：先遍历左子树，再输出根节点，最后遍历右子树
• 后序遍历：先遍历左子树和右子树，最后输出根节点

二叉树的遍历的非递归实现

前序遍历

前序遍历的顺序是 根节点 -> 左子树 -> 右子树，因此，我们可以借助栈来实现非递归的前序遍历。

先将根节点入栈，然后进入循环，每次从栈中弹出一个节点，输出该节点，然后依次将其右子节点和左子节点入栈。直到栈为空，遍历结束。

以下展示一个实例：

void pre_order_traversal(BinaryTreeNode* root) {
    if (root == nullptr) {
        return;
    }
    std::stack<BinaryTreeNode*> node_stack;
    node_stack.push(root);
    while (!node_stack.empty()) {
        BinaryTreeNode* node = node_stack.top();
        node_stack.pop();
        std::cout << node->value << " "; // 输出节点的值
        if (node->right) {
            node_stack.push(node->right);
        }
        if (node->left) {
            node_stack.push(node->left);
        }
    }
}

中序遍历

中序遍历的顺序是 左子树 -> 根节点 -> 右子树，同样地，我们也可以借助栈来实现非递归的中序遍历。

首先我们将根节点入栈，然后进入循环，在每次循环中，如果栈顶元素不为空，我们就将其弹出，并输出节点的值，然后将其右子节点入栈，接着将其左子节点入栈。这样，在下一次循环时，会先输出节点的左子树和根节点，然后会输出节点的右子树。

以下展示一个实例：

void in_order_traversal(BinaryTreeNode* root) {
    std::stack<BinaryTreeNode*> node_stack;
    BinaryTreeNode* current = root;
    while (current || !node_stack.empty()) {
        while (current) {
            node_stack.push(current);
            current = current->left;
        }
        current = node_stack.top();
        node_stack.pop();
        std::cout << current->value << " "; // 输出节点的值
        current = current->right;
    }
}

后序遍历

后序遍历的顺序是 左子树 -> 右子树 -> 根节点，同样地，我们仍然可以借助栈来实现非递归的后序遍历。

我们可以使用两个栈，一个栈来存储节点，另一个栈来输出遍历的结果。将根节点压入第一个栈中，然后从第一个栈中弹出该节点，将其压入第二个栈中，然后依次将该节点的左子节点和右子节点压入第一个栈中。直到第一个栈为空，遍历结束。最后，从第二个栈中输出遍历的结果即可。

以下展示一个实例：

void post_order_traversal(BinaryTreeNode* root) {
    std::stack<BinaryTreeNode*> node_stack1;
    std::stack<BinaryTreeNode*> node_stack2;
    node_stack1.push(root);
    while (!node_stack1.empty()) {
        BinaryTreeNode* node = node_stack1.top();
        node_stack1.pop();
        node_stack2.push(node);
        if (node->left) {
            node_stack1.push(node->left);
        }
        if (node->right) {
            node_stack1.push(node->right);
        }
    }
    while (!node_stack2.empty()) {
        std::cout << node_stack2.top()->value << " ";
        node_stack2.pop();
    }
}

总结

C++二叉树的前序中序后序非递归实现方法，可以通过栈来实现，结合以上几个遍历方式的代码标准实现，我们可以更好的掌握二叉树的遍历，从而更好的应用于实际开发中。

阅读剩余 55%