พิมพ์จำนวน Set Bits ในแต่ละโหนดของ Binary Tree ใน C++

กำหนด Binary Tree ฟังก์ชันจะสร้างค่าไบนารีของคีย์ที่จัดเก็บในโหนด และส่งคืนจำนวนบิตที่ตั้งค่าเป็น 1 (set bits) ในค่าไบนารีนั้น

ตัวอย่าง

Binary tree ที่มีคีย์: 10, 3, 211, 140, 162, 100, 146

ที่นี่เราใช้ฟังก์ชัน __builtin_popcount

โพรโทไทป์ของฟังก์ชัน:

int __builtin_popcount(unsigned int)

ฟังก์ชันนี้ส่งคืนจำนวนบิตที่ตั้งค่าเป็น 1 ในจำนวนเต็ม หมายถึงจำนวน 1 ในการแทนค่าไบนารีของจำนวนเต็มนั้น

อัลกอริทึม

START
ขั้นตอนที่ 1: สร้างโครงสร้างโหนด struct Node { Node *left, *right; int data; }
ขั้นตอนที่ 2: ฟังก์ชันสร้างโหนด newnode(int data)
ขั้นตอนที่ 3: ฟังก์ชันสร้างบิตของข้อมูลโหนด bits(Node* root)
    ถ้า root = NULL return
    พิมพ์ __builtin_popcount(root->data)
    bits(root->left)
    bits(root->right)
ขั้นตอนที่ 4: ใน main() สร้างต้นไม้ เรียก bits(root)
STOP

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

#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 << "bits in node " << 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;
}

ผลลัพธ์

bits in node 10 = 2
bits in node 3 = 2
bits in node 140 = 3
bits in node 162 = 3
bits in node 211 = 5
bits in node 100 = 3
bits in node 146 = 3