C++完全二叉树建立

C++中构建完全二叉树通常有两种常见方法：递归法和迭代法。

1. **递归法**：
- 对于最后一个节点，直接插入到已知结构中；
- 如果当前节点有右孩子，那么左孩子的值应该是当前节点的下一个可用位置，然后递归处理右子树；
- 如果当前节点没有右孩子，但在左边还有空位，说明应该从上一层向下填充直到找到合适的位置。

void buildCompleteTree(vector<int>& nodes, int& index, int root = 0) {
    if (index >= nodes.size()) return;
    // 先处理左子树
    buildCompleteTree(nodes, index, 2 * root + 1);
    // 然后处理根节点
    nodes[root] = index++;
    // 最后处理右子树，如果有
    if (index < nodes.size()) {
        buildCompleteTree(nodes, index, 2 * root + 2);
    }
}

2. **迭代法（自底向上）**：
- 使用栈来辅助存储待插入的节点索引；
- 当根节点为空时，将剩余元素依次压入栈中；
- 每次取出栈顶元素作为当前节点，并检查其是否已经有两个子节点；如果没有，就给它分配一个子节点并继续处理剩余元素。

void buildCompleteTree(vector<int>& nodes, vector<int>& stack, int root = 0) {
    for (int i = nodes.size() - 1; i >= 0; --i) {
        nodes[root] = i;
        root = 2 * root + 1;
        stack.push_back(root); // 添加右子节点
        if (root + 1 < nodes.size()) {
            root = 2 * root + 2; // 更新左子节点
            stack.push_back(root);
        } else {
            break;
        }
    }
}