ความกว้างสูงสุดของต้นไม้ไบนารีใน C++

ข้อความของปัญหา

กำหนดต้นไม้ไบนารี ให้เขียนฟังก์ชันเพื่อหาความกว้างสูงสุดของต้นไม้ที่กำหนด ความกว้างของต้นไม้คือค่าสูงสุดของความกว้างของทุกระดับ

พิจารณาต้นไม้ด้านล่าง -

        10
       /  \
      7    4
     / \    \
    9   2    1
           /  \
          2    5

1. ความกว้างที่ระดับ 1: 1
2. ความกว้างที่ระดับ 2: 2
3. ความกว้างที่ระดับ 3: 3
4. ความกว้างที่ระดับ 4: 2
สำหรับต้นไม้ข้างต้น คำตอบคือ 3

อัลกอริทึม

1. ใช้ Level Order Traversal เพื่อหาคำตอบ

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

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

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

int getWidth(node* root, int level);
int height(node* node);
node* newNode(int data);

int getMaxWidth(node* root){
    int maxWidth = 0;
    int width;
    int h = height(root);
    int i;
    for (i = 1; i <= h; ++i) {
        width = getWidth(root, i);
        if (width > maxWidth) {
            maxWidth = width;
        }
    }
    return maxWidth;
}

int getWidth(node* root, int level){
    if (root == NULL) {
        return 0;
    }
    if (level == 1) {
        return 1;
    }
    else if (level > 1) {
        return getWidth(root->left, level - 1) + getWidth(root->right, level - 1);
    }
}

int height(node* node){
    if (node == NULL) {
        return 0;
    }
    int lHeight = height(node->left);
    int rHeight = height(node->right);
    return (lHeight > rHeight)? (lHeight + 1): (rHeight + 1);
}

node* newNode(int data){
    node* Node = new node();
    Node->data = data;
    Node->left = NULL;
    Node->right = NULL;
    return(Node);
}

int main(){
    node *root = newNode(10);
    root->left = newNode(7);
    root->right = newNode(4);
    root->left->left = newNode(9);
    root->left->right = newNode(2);
    root->right->right = newNode(1);
    root->right->right->left = newNode(2);
    root->right->right->right = newNode(5);
    cout<<"Maximum width = " << getMaxWidth(root) << endl;
    return 0;
}

ผลลัพธ์

เมื่อคุณคอมไพล์และรันโปรแกรมข้างต้น จะได้ผลลัพธ์ดังนี้ -

Maximum width = 3