完全二叉树

完全二叉树（Complete Binary Tree）是指除了最后一层节点可能不满外，其他层节点都是满的二叉树。在最后一层上，如果有叶子节点，那么它们都在左侧连续位置上。

下面是一个简单的C语言实现完全二叉树的代码：

#include <stdio.h>
#include <stdlib.h>

typedef struct node {
    int value;
    struct node *left;
    struct node *right;
} node;

int get_height(node *root) {
    if (root == NULL) {
        return 0;
    }
    int left_height = get_height(root->left);
    int right_height = get_height(root->right);
    return 1 + (left_height > right_height ? left_height : right_height);
}

int is_perfect(node *root, int height, int level) {
    if (root == NULL) {
        return 1;
    }
    if (root->left == NULL && root->right == NULL) {
        return height == level + 1;
    }
    if (root->left == NULL || root->right == NULL) {
        return 0;
    }
    return is_perfect(root->left, height, level + 1) && is_perfect(root->right, height, level + 1);
}

node *create_node(int value) {
    node *new_node = (node *)malloc(sizeof(node));
    new_node->value = value;
    new_node->left = NULL;
    new_node->right = NULL;
    return new_node;
}

void destroy_tree(node *root) {
    if (root == NULL) {
        return;
    }
    destroy_tree(root->left);
    destroy_tree(root->right);
    free(root);
}

int main() {
    node *root = create_node(1);
    root->left = create_node(2);
    root->right = create_node(3);
    root->left->left = create_node(4);
    root->left->right = create_node(5);
    root->right->left = create_node(6);
    // root->right->right = create_node(7);  // Uncomment to make the tree non-perfect
    int height = get_height(root);
    int level = 0;
    if (is_perfect(root, height, level)) {
        printf("The tree is a perfect binary tree\n");
    } else {
        printf("The tree is not a perfect binary tree\n");
    }
    destroy_tree(root);
    return 0;
}

这个代码创建了一个完全二叉树，并在销毁时递归地释放了所有节点的内存。在创建时，我们使用 create_node 函数来创建节点，该函数会分配一块新的内存并返回指向该内存的指针。