二叉树的非递归创建c加加

在C++中，二叉树的非递归创建可以通过使用栈来实现。以下是一个示例代码，展示了如何使用非递归的方法创建二叉树：

#include <iostream>
#include <stack>

// 定义二叉树节点结构
struct TreeNode {
    int data;
    TreeNode* left;
    TreeNode* right;

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

// 非递归创建二叉树
TreeNode* createBinaryTree() {
    int val;
    std::cout << "Enter root value (or -1 to stop): ";
    std::cin >> val;

    if (val == -1) {
        return nullptr;
    }

    TreeNode* root = new TreeNode(val);
    std::stack<std::pair<TreeNode*, bool>> nodeStack;
    nodeStack.push({root, false});

    while (!nodeStack.empty()) {
        TreeNode* currentNode = nodeStack.top().first;
        bool leftProcessed = nodeStack.top().second;
        nodeStack.pop();

        if (!leftProcessed) {
            // 处理左子节点
            std::cout << "Enter left child of " << currentNode->data << " (or -1 to stop): ";
            std::cin >> val;
            if (val != -1) {
                currentNode->left = new TreeNode(val);
                nodeStack.push({currentNode, true});
                nodeStack.push({currentNode->left, false});
            } else {
                nodeStack.push({currentNode, true});
            }
        } else {
            // 处理右子节点
            std::cout << "Enter right child of " << currentNode->data << " (or -1 to stop): ";
            std::cin >> val;
            if (val != -1) {
                currentNode->right = new TreeNode(val);
                nodeStack.push({currentNode->right, false});
            }
        }
    }

    return root;
}

// 中序遍历二叉树
void inorderTraversal(TreeNode* root) {
    if (root == nullptr) {
        return;
    }

    inorderTraversal(root->left);
    std::cout << root->data << " ";
    inorderTraversal(root->right);
}

int main() {
    TreeNode* root = createBinaryTree();
    std::cout << "Inorder traversal of the binary tree: ";
    inorderTraversal(root);
    std::cout << std::endl;

    return 0;
}

在这个示例中，我们使用了一个栈来存储节点和它们的处理状态。栈中的每个元素都是一个`std::pair`，包含一个节点和一个布尔值，表示该节点的左子节点是否已经处理过。