Complete binary tree là gì?

Cây nhị phân hoàn chỉnh (complete binary tree) là cây nhị phân (binary tree) trong đó tất cả các mức (level) được lấp đầy hoàn toàn ngoại trừ mức thấp nhất có thể được lắp đầy từ bên trái. Một cây nhị phân hoàn chỉnh cũng giống như một cây nhị phân đầy đủ ( full binary tree), nhưng có hai điểm khác biệt chính.

• Tất cả các nút lá (leaf node) phải nghiêng về bên trái.
• Nút lá cuối cùng có thể không có sibling bên phải, tức là một cây nhị phân hoàn chỉnh không nhất thiết phải là một cây nhị phân đầy đủ.

Bên dưới là mã kiểm tra xem cây nhị phân có phải là cây nhị phân hoàn chỉnh trong C hay không:

// Checking if a binary tree is a complete binary tree in C

#include 
#include 
#include 

struct Node {
  int key;
  struct Node *left, *right;
};

// Node creation
struct Node *newNode(char k) {
  struct Node *node = (struct Node *)malloc(sizeof(struct Node));
  node->key = k;
  node->right = node->left = NULL;
  return node;
}

// Count the number of nodes
int countNumNodes(struct Node *root) {
  if (root == NULL)
    return (0);
  return (1 + countNumNodes(root->left) + countNumNodes(root->right));
}

// Check if the tree is a complete binary tree
bool checkComplete(struct Node *root, int index, int numberNodes) {
  // Check if the tree is complete
  if (root == NULL)
    return true;

  if (index >= numberNodes)
    return false;

  return (checkComplete(root->left, 2 * index + 1, numberNodes) && checkComplete(root->right, 2 * index + 2, numberNodes));
}

int main() {
  struct Node *root = NULL;
  root = newNode(1);
  root->left = newNode(2);
  root->right = newNode(3);
  root->left->left = newNode(4);
  root->left->right = newNode(5);
  root->right->left = newNode(6);

  int node_count = countNumNodes(root);
  int index = 0;

  if (checkComplete(root, index, node_count))
    printf("The tree is a complete binary tree\n");
  else
    printf("The tree is not a complete binary tree\n");
}