用c++实现二叉树的顺序存储

在C++中，实现二叉树的顺序存储通常采用数组的方式，每个节点的数据结构包含两个指针（指向左孩子和右孩子），以及一个额外的域用于存储节点值。由于二叉树的非线性特性，我们一般会按照某种递归策略来存储，最常见的是前序遍历（根-左-右）或中序遍历（左-根-右）。

以下是前序遍历实现二叉树顺序存储的一个简单例子：

// 定义二叉树节点
struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

// 假设数组size是一个已知的足够大的整数，用于存储所有节点
TreeNode* createBinaryTreeFromArray(int arr[], int size) {
    if (size <= 0 || arr[size - 1] == -1) {
        return nullptr; // 如果数组为空或最后一个元素表示结束标志，返回空树
    }

    int rootVal = arr[0]; // 根节点值
    TreeNode* root = new TreeNode(rootVal);

    // 使用栈辅助存储节点及其索引
    std::stack<std::pair<TreeNode*, int>> stack;
    stack.push({root, 1}); // 初始化根节点和其下标

    for (int i = 1; i < size; ++i) {
        if (arr[i] != -1) { // 当前元素代表一个子节点
            TreeNode* newNode = new TreeNode(arr[i]);
            TreeNode* parent = stack.top().first;
            int parentIndex = stack.top().second;

            if (parent->left == nullptr) { // 将新节点作为左孩子
                parent->left = newNode;
            } else {
                // 如果左孩子不为空，则寻找右孩子位置
                while (parent->right && parent->right->val > arr[i]) {
                    stack.pop();
                    parent = stack.top().first;
                }
                parent->right = newNode; // 将新节点插入到合适的位置
            }
            stack.push({newNode, i + 1}); // 更新栈顶节点
        } else {
            // 找到结束标志，出栈直到找到空节点
            while (!stack.empty() && arr[stack.top().second] != -1) {
                stack.pop();
            }
        }
    }
    return root;
}