home

หน้าแรก
 Computer >> บทช่วยสอนคอมพิวเตอร์ >  >> การเขียนโปรแกรม >> C++

หา Complete Subtree ใหญ่ที่สุดใน Binary Tree ใน C++

แนวคิด

Complete Binary Tree: ทุกระดับเต็มยกเว้นระดับสุดท้าย และโหนดชิดซ้ายสุด Perfect Binary Tree เป็น Complete เสมอ แต่กลับไม่จริง

โจทย์: หาขนาดของ Complete Subtree ใหญ่ที่สุดใน Binary Tree ที่กำหนด

วิธีการแก้ปัญหา

Traverse แบบ Bottom-up ส่งข้อมูลจากลูกขึ้นมาหา parent:

  • bool isPerfect: subtree นี้เป็น Perfect หรือไม่
  • bool isComplete: subtree นี้เป็น Complete หรือไม่
  • int size: ขนาด subtree
  • node* rootTree: รากของ Complete subtree ใหญ่ที่สุดที่พบ

3 กรณีที่ parent เป็น Complete:

  1. Left Perfect + Right Complete + ความสูงเท่ากัน → Complete (Perfect ถ้า Right ก็ Perfect)
  2. Left Complete + Right Perfect + ความสูง Left = Right + 1 → Complete (แต่ไม่ Perfect)
  3. อื่นๆ → ไม่ใช่ Complete, ส่ง size ใหญ่สุดของลูกขึ้นไป

ตัวอย่างโค้ด C++

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

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

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

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

returnType findCompleteBinaryTree(struct node1* root){
    returnType rt1;
    if (root == NULL) { rt1.isPerfect = rt1.isComplete = true; rt1.size1 = 0; rt1.rootTree = NULL; 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(){
    struct 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);
    
    struct returnType ans1 = findCompleteBinaryTree(root);
    cout << "Size : " << ans1.size1 << endl;
    cout << "Inorder Traversal : ";
    inorderPrint(ans1.rootTree);
    return 0;
}

ผลลัพธ์

Size : 4 Inorder Traversal : 10 45 60 70