Full binary tree là gì?

Cây nhị phân đầy đủ (full binary tree) là một loại cây nhị phân (binary tree) đặc biệt trong đó mọi nút cha (parent node)/ nút trong (internal node) đều có hai hoặc không có nút con (child node). Nó còn được gọi là cây nhị phân thích hợp.

Định lý cây nhị phân đầy đủ:

Let, i = Tổng số nút là 2i + 1.
     n = là tổng số nút
     l = số nút lá
     λ = số mức (level)

• Số nút lá là i + 1.
• Tổng số nút (n) là 2i + 1.
• Số nút trong là (n - 1) / 2.
• Số nút lá là (n + 1) / 2.
• Tổng số nút là 2l - 1.
• Số nút trong là l - 1.
• Số nút lá nhiều nhất là 2^{λ - 1}.

Đoạn mã sau dùng để kiểm tra xem một cây có phải là một cây nhị phân đầy đủ hay không trong C.

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

#include 
#include 
#include 

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

// Creation of new Node
struct Node *createNewNode(char k) {
  struct Node *node = (struct Node *)malloc(sizeof(struct Node));
  node->item = k;
  node->right = node->left = NULL;
  return node;
}

bool isFullBinaryTree(struct Node *root) {
  // Checking tree emptiness
  if (root == NULL)
    return true;

  // Checking the presence of children
  if (root->left == NULL && root->right == NULL)
    return true;

  if ((root->left) && (root->right))
    return (isFullBinaryTree(root->left) && isFullBinaryTree(root->right));

  return false;
}

int main() {
  struct Node *root = NULL;
  root = createNewNode(1);
  root->left = createNewNode(2);
  root->right = createNewNode(3);

  root->left->left = createNewNode(4);
  root->left->right = createNewNode(5);
  root->left->right->left = createNewNode(6);
  root->left->right->right = createNewNode(7);

  if (isFullBinaryTree(root))
    printf("The tree is a full binary tree\n");
  else
    printf("The tree is not a full binary tree\n");
}