Kiểm tra cây nhị phân đầy đủ (Full Binary Tree) trong C++

Cây nhị phân đầy đủ (Full Binary Tree): mọi node đều có 0 hoặc 2 con.

Ví dụ

Input 1: → Output: 1 (True)

Mọi node không phải lá đều có 2 con.

Input 2: → Output: 0 (False)

Node 2 chỉ có 1 con.

Cách tiếp cận: Đệ quy

• Hàm isFullBinaryTree(root)
• Base: root NULL → True
• Nếu cả 2 con NULL → True
• Nếu cả 2 con không NULL → đệ quy left AND right
• Ngược lại → False

Code C++

#include <iostream>
using namespace std;

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

struct treenode* createNode(int d) {
    struct treenode* root = new treenode;
    root->data = d; root->left = NULL; root->right = NULL;
    return root;
}

bool isFullBinaryTree(struct treenode* root) {
    if (!root) return true;
    if (!root->left && !root->right) return true;
    if (root->left && root->right)
        return isFullBinaryTree(root->left) && isFullBinaryTree(root->right);
    return false;
}

int main() {
    struct treenode* root = NULL;
    root = createNode(1);
    root->left = createNode(2);
    root->right = createNode(3);
    root->left->right = createNode(4);
    root->left->left = createNode(5);
    root->right->left = createNode(6);
    if (isFullBinaryTree(root)) cout << "1" << endl;
    else cout << "0" << endl;
    return 0;
}

Kết quả

0

Cây không đầy đủ (node 3 chỉ có 1 con) → 0.