Perfect binary tree là gì?

Cây nhị phân hoàn hảo (perfect binary tree) là một loại cây nhị phân (binary tree) trong đó mỗi nút trong (internal node ) có đúng hai nút con (child node) và tất cả các nút lá (leaf node) đều ở cùng một mức (level). Tất cả các nút trong có bậc (degree) là 2.

Một cách đệ quy, một cây nhị phân hoàn hảo có thể được định nghĩa là:

• Nếu một nút duy nhất không có nút con, nó là một cây nhị phân hoàn hảo (perfect binary tree) có chiều cao (height) h = 0.
• Nếu một nút có h> 0, nó là một cây nhị phân hoàn hảo nếu cả hai cây con (subtree) của nó có chiều cao h - 1 và không chồng chéo.

Đoạn mã sau đây là để kiểm tra xem một cây có phải là một cây nhị phân hoàn hảo (perfect binary tree) hay không.

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

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

struct node {
  int data;
  struct node *left;
  struct node *right;
};

// Creating a new node
struct node *newnode(int data) {
  struct node *node = (struct node *)malloc(sizeof(struct node));
  node->data = data;
  node->left = NULL;
  node->right = NULL;

  return (node);
}

// Calculate the depth
int depth(struct node *node) {
  int d = 0;
  while (node != NULL) {
    d++;
    node = node->left;
  }
  return d;
}

// Check if the tree is perfect
bool is_perfect(struct node *root, int d, int level) {
    // Check if the tree is empty
  if (root == NULL)
    return true;

  // Check the presence of children
  if (root->left == NULL && root->right == NULL)
    return (d == level + 1);

  if (root->left == NULL || root->right == NULL)
    return false;

  return is_perfect(root->left, d, level + 1) &&
       is_perfect(root->right, d, level + 1);
}

// Wrapper function
bool is_Perfect(struct node *root) {
  int d = depth(root);
  return is_perfect(root, d, 0);
}

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);

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

Định lý cây nhị phân hoàn hảo:

• Một cây nhị phân hoàn hảo có chiều cao h có 2h + 1 - 1 nút.
• Một cây nhị phân hoàn hảo với n nút có chiều cao log (n + 1) - 1 = Θ (ln (n)).
• Một cây nhị phân hoàn hảo có chiều cao h có 2 nút lá.
• Độ sâu (depth) trung bình của một nút trong cây nhị phân hoàn hảo là Θ (ln (n)).