chatgpt非递归前序遍历二叉树

非递归前序遍历二叉树.md

非递归前序遍历二叉树可以使用栈来实现。具体步骤如下：

1. 创建一个空栈，并将根节点入栈。

2. 循环执行以下步骤直到栈为空：

   • 弹出栈顶节点，并访问该节点。
   • 如果该节点有右子节点，将右子节点入栈。
   • 如果该节点有左子节点，将左子节点入栈。

以下是一个使用C++实现非递归前序遍历二叉树的示例代码：

#include <iostream>
#include <stack>

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;

    TreeNode(int value) : val(value), left(nullptr), right(nullptr) {}
};

void preorderTraversal(TreeNode* root) {
    if (root == nullptr) {
        return;
    }

    std::stack<TreeNode*> nodeStack;
    nodeStack.push(root);

    while (!nodeStack.empty()) {
        TreeNode* node = nodeStack.top();
        nodeStack.pop();

        std::cout << node->val << " ";

        if (node->right != nullptr) {
            nodeStack.push(node->right);
        }
        if (node->left != nullptr) {
            nodeStack.push(node->left);
        }
    }
}

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);

    std::cout << "Preorder traversal: ";
    preorderTraversal(root);
    std::cout << std::endl;

    return 0;
}

在这个示例中，我们定义了一个TreeNode结构体表示二叉树的节点。我们使用栈nodeStack来存储待访问的节点。

在preorderTraversal函数中，我们首先将根节点入栈。然后循环执行以下步骤：弹出栈顶节点，访问该节点的值，并将其右子节点和左子节点依次入栈。这样可以保证在访问根节点之前，先访问其左子节点。

在main函数中，我们创建了一个二叉树，并进行非递归前序遍历。输出结果为：

Preorder traversal: 1 2 4 5 3

这表示二叉树的非递归前序遍历结果为1 2 4 5 3。

希望对你有帮助！