Tìm cây con hoàn chỉnh lớn nhất trong cây nhị phân (C++)

Khái niệm

Cho cây nhị phân, tìm kích thước cây con hoàn chỉnh (Complete Binary Tree) lớn nhất. Cây hoàn chỉnh: mọi cấp độ đều đầy trừ cấp cuối, và nút cấp cuối nghiêng trái. Cây hoàn hảo (Perfect) luôn hoàn chỉnh, nhưng ngược lại không đúng.

Ví dụ 1: Cây hoàn chỉnh → Size 10, Inorder: 9 5 10 3 11 6 2 7 4 8.

Ví dụ 2: Cây không hoàn chỉnh → Size 4 (cây con bên phải), Inorder: 11 46 61 71.

Phương pháp

Duyệt cây bottom-up. Mỗi nút con trả về thông tin cho nút cha:

• isPerfect: cây con có phải hoàn hảo không.
• isComplete: cây con có phải hoàn chỉnh không.
• size: kích thước cây con hoàn chỉnh lớn nhất tìm thấy.
• rootTree: gốc của cây con hoàn chỉnh lớn nhất.

1. Con trái hoàn hảo, con phải hoàn chỉnh, cùng chiều cao → cha hoàn chỉnh (và hoàn hảo nếu con phải cũng hoàn hảo).
2. Con trái hoàn chỉnh, con phải hoàn hảo, chiều cao trái = chiều cao phải + 1 → cha hoàn chỉnh (không hoàn hảo).
3. Ngược lại → cha không hoàn chỉnh, trả về max(size trái, size phải).

Ví dụ (C++)

#include <bits/stdc++.h>
using namespace std;

struct node1 { int data; node1 *left, *right; };
node1* newNode(int data){ /* ... */ }

struct returnType {
    bool isPerfect, isComplete;
    int size1;
    node1* rootTree;
};

int getHeight(int size1){ return ceil(log2(size1 + 1)); }

returnType findCompleteBinaryTree(node1* root){
    returnType rt1;
    if (!root) { rt1 = {true, true, 0, nullptr}; return rt1; }
    returnType lv1 = findCompleteBinaryTree(root->left);
    returnType rv1 = findCompleteBinaryTree(root->right);
    // Case A
    if (lv1.isPerfect && rv1.isComplete && getHeight(lv1.size1) == getHeight(rv1.size1)) {
        rt1.isComplete = true;
        rt1.isPerfect = rv1.isPerfect;
        rt1.size1 = lv1.size1 + rv1.size1 + 1;
        rt1.rootTree = root;
        return rt1;
    }
    // Case B
    if (lv1.isComplete && rv1.isPerfect && getHeight(lv1.size1) == getHeight(rv1.size1) + 1) {
        rt1.isComplete = true; rt1.isPerfect = false;
        rt1.size1 = lv1.size1 + rv1.size1 + 1;
        rt1.rootTree = root;
        return rt1;
    }
    // Case C
    rt1.isPerfect = rt1.isComplete = false;
    rt1.size1 = max(lv1.size1, rv1.size1);
    rt1.rootTree = (lv1.size1 > rv1.size1) ? lv1.rootTree : rv1.rootTree;
    return rt1;
}

void inorderPrint(node1* root){ /* ... */ }

int main(){
    node1* root = newNode(50);
    root->left = newNode(30); root->right = newNode(60);
    root->left->left = newNode(5); root->left->right = newNode(20);
    root->right->left = newNode(45); root->right->right = newNode(70);
    root->right->left->left = newNode(10);
    returnType ans1 = findCompleteBinaryTree(root);
    cout << "Size : " << ans1.size1 << endl;
    cout << "Inorder Traversal : "; inorderPrint(ans1.rootTree);
    return 0;
}

Đầu ra

Size : 4 Inorder Traversal : 10 45 60 70