建立完全二叉树C++

在C++中，可以使用指针和动态内存分配来建立完全二叉树。完全二叉树是一种特殊的二叉树，除了最后一层外，其他层的节点都是满的，并且最后一层的节点都尽量靠左排列。

下面是一个建立完全二叉树的示例代码：

#include <iostream>
#include <queue>

using namespace std;

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

// 创建新节点
TreeNode* createNode(int data) {
    TreeNode* newNode = new TreeNode();
    if (!newNode) {
        cout << "内存分配失败！" << endl;
        return NULL;
    }
    newNode->data = data;
    newNode->left = newNode->right = NULL;
    return newNode;
}

// 建立完全二叉树
TreeNode* createCompleteBinaryTree(int arr[], int size) {
    if (size == 0) {
        return NULL;
    }

    // 创建根节点
    TreeNode* root = createNode(arr[0]);

    // 使用队列辅助进行层序遍历
    queue<TreeNode*> q;
    q.push(root);

    // 从数组的第二个元素开始，依次创建节点并连接到二叉树中
    for (int i = 1; i < size; i++) {
        TreeNode* currentNode = q.front();
        q.pop();

        // 创建左子节点
        currentNode->left = createNode(arr[i]);
        q.push(currentNode->left);

        // 如果数组还有剩余元素，则创建右子节点
        if (i < size - 1) {
            currentNode->right = createNode(arr[i + 1]);
            q.push(currentNode->right);
            i++;  // 因为右子节点已经被创建，所以需要跳过下一个元素
        }
    }

    return root;
}

// 层序遍历二叉树
void levelOrderTraversal(TreeNode* root) {
    if (root == NULL) {
        return;
    }

    queue<TreeNode*> q;
    q.push(root);

    while (!q.empty()) {
        TreeNode* currentNode = q.front();
        q.pop();

        cout << currentNode->data << " ";

        if (currentNode->left) {
            q.push(currentNode->left);
        }
        if (currentNode->right) {
            q.push(currentNode->right);
        }
    }
}

int main() {
    int arr[] = {1, 2, 3, 4, 5, 6, 7};
    int size = sizeof(arr) / sizeof(arr[0]);

    TreeNode* root = createCompleteBinaryTree(arr, size);

    cout << "完全二叉树的层序遍历结果为：";
    levelOrderTraversal(root);

    return 0;
}

这段代码中，我们首先定义了一个`TreeNode`结构体来表示二叉树的节点。然后，我们使用`createNode`函数来创建新的节点，并使用`createCompleteBinaryTree`函数来建立完全二叉树。在`createCompleteBinaryTree`函数中，我们使用队列来辅助进行层序遍历，并依次创建节点并连接到二叉树中。最后，我们使用`levelOrderTraversal`函数来进行层序遍历并输出结果。