In số bit 1 (set bits) của mỗi nút trong cây nhị phân (C++)

Cho cây nhị phân, hàm tạo nhị phân của khóa trong nút và trả về số bit 1 (set bits) trong biểu diễn nhị phân.

Ví dụ

Cây nhị phân có khóa: 10, 3, 211, 140, 162, 100, 146

Dùng hàm __builtin_popcount

Nguyên mẫu:

int __builtin_popcount(unsigned int)

Trả về số bit 1 trong biểu diễn nhị phân của số nguyên.

Thuật toán

BẮT ĐẦU
BƯỚC 1: CẤU TRÚC NÚT: struct Node { Node *left, *right; int data; }
BƯỚC 2: HÀM TẠO NÚT newnode(int data)
BƯỚC 3: HÀM TẠO BIT bits(Node* root)
    NẾU root == NULL TRẢ VỀ
    IN __builtin_popcount(root->data)
    bits(root->left)
    bits(root->right)
BƯỚC 4: TRONG main(): TẠO CÂY, GỌI bits(root)
KẾT THÚC

Ví dụ mã C++

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

struct Node { 
    int data; 
    struct Node *left, *right; 
}; 

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

void bits(Node* root) { 
    if (root == NULL) return; 
    cout << "Số bit 1 trong nút " << root->data << " = " 
         << __builtin_popcount(root->data) << "\n"; 
    bits(root->left); 
    bits(root->right); 
} 

int main() { 
    Node* root = newnode(10); 
    root->left = newnode(3); 
    root->left->left = newnode(140); 
    root->left->right = newnode(162); 
    root->right = newnode(211); 
    root->right->left = newnode(100); 
    root->right->right = newnode(146); 
    bits(root); 
    return 0; 
}

Kết quả

Chạy chương trình cho kết quả:

Số bit 1 trong nút 10 = 2 
Số bit 1 trong nút 3 = 2 
Số bit 1 trong nút 140 = 3 
Số bit 1 trong nút 162 = 3 
Số bit 1 trong nút 211 = 5 
Số bit 1 trong nút 100 = 3 
Số bit 1 trong nút 146 = 3