Độ rộng tối đa của cây nhị phân trong C++

Đề bài

Cho một cây nhị phân, viết hàm để lấy độ rộng tối đa của cây đã cho. Độ rộng của một cây là tối đa của độ rộng của tất cả các cấp độ.

Xét cây dưới đây –

        10
       /  \
      7    4
     / \    \
    9   2    1
           / \
          2   5
1. Độ rộng cấp 1: 1
2. Độ rộng cấp 2: 2
3. Độ rộng cấp 3: 3
4. Độ rộng cấp 4: 2
Đáp án cho cây trên là 3.

Thuật toán

1. Sử dụng duyệt theo cấp độ (level order traversal) để tìm đáp án

Ví dụ

#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<<"Độ rộng tối đa = " << getMaxWidth(root) << endl;
    return 0;
}

Kết quả

Khi bạn biên dịch và thực thi chương trình trên, nó tạo ra đầu ra sau:

Độ rộng tối đa = 3