c++ stack 遍历

C++中的stack（堆栈）是一个容器类，实现了一个先进后出（FILO）的数据结构。stack提供了以下操作：empty()、pop()、push()、size()、top()等方法来操作栈中的元素。可以使用这些方法来遍历和操作stack中的数据。

例如，可以使用top()方法获取栈顶元素，然后使用pop()方法将栈顶元素弹出，从而实现遍历stack的操作。

相关问题

C++中序遍历非递归

C++中的二叉树序遍历有三种方式：前序遍历、中序遍历和后序遍历。下面我将介绍一下C++中的中序遍历非递归实现方法。

中序遍历的非递归实现可以使用栈来辅助完成。具体步骤如下：

1. 创建一个空栈，用于存储待访问的节点。
2. 初始化当前节点为根节点。
3. 当当前节点不为空或者栈不为空时，执行以下操作：
- 若当前节点不为空，则将当前节点入栈，并将当前节点更新为其左子节点。
- 若当前节点为空，则从栈中弹出一个节点并访问它，然后将当前节点更新为其右子节点。
4. 重复步骤3，直到当前节点为空且栈为空。

下面是C++中实现中序遍历非递归的示例代码：

#include <iostream>
#include <stack>
using namespace std;

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

void inorderTraversal(TreeNode* root) {
    stack<TreeNode*> s;
    TreeNode* curr = root;

    while (curr != NULL || !s.empty()) {
        while (curr != NULL) {
            s.push(curr);
            curr = curr->left;
        }

        curr = s.top();
        s.pop();
        cout << curr->val << " ";

        curr = curr->right;
    }
}

int main() {
    // 构造一个二叉树
    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    root->left->left = new TreeNode(4);
    root->left->right = new TreeNode(5);

    cout << "中序遍历结果：";
    inorderTraversal(root);

    return 0;
}

运行以上代码，将输出中序遍历的结果。

满二叉树C++前序遍历构造树

满二叉树是一种特殊的二叉树，其中每个节点都有0个或2个子节点，并且所有层级都是完全填充的。对于满二叉树的前序遍历构造树，前序遍历的顺序通常是“根-左-右”，即先访问根节点，然后遍历左子树，最后遍历右子树。

C++中，可以按照这个顺序来构建满二叉树。首先，我们需要保存一个队列用于存储遍历过程中的节点，因为前序遍历时根节点总是第一个出栈。以下是基本步骤：

1. 定义一个结构体或类表示树的节点，包含值和左右子节点指针。
2. 创建一个空的根节点。
3. 接收前序遍历序列作为输入，例如`vector<int> preorder`。
4. 初始化队列，将根节点入队。
5. 当队列非空时：
a. 出队当前节点，将其添加到结果树的对应位置。
b. 如果当前节点的右子节点在前序序列中，找到它的索引并减一（因为序列是从0开始的），然后将该节点入队。
c. 同理，如果当前节点有左子节点，也找到其索引并减一，将左子节点入队。

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

vector<TreeNode*> buildTree(vector<int>& preorder) {
    if (preorder.empty()) return {};

    TreeNode* root = new TreeNode(preorder[0]);
    stack<TreeNode*> s({root});
    int i = 1;

    while (!s.empty() && i < preorder.size()) {
        TreeNode* node = s.top();
        s.pop();

        if (i < preorder.size() && preorder[i] == node->val) {
            // 找到右子节点
            node->right = new TreeNode(preorder[i + 1]);
            s.push(node->right);
            i += 2;
        } else {
            // 左子节点已经在前面处理过了，直接出队等待处理
            assert(i < preorder.size());
            node->left = s.top(); // 右子节点已经出队，所以左子节点还在栈顶
            s.pop();
        }
    }

    return {root};
}