C++プログラミングのバイナリツリーの各ノードのセットビット数を出力します。
バイナリツリーが与えられると、関数はノードに格納されているキーのバイナリ値を生成し、そのバイナリに相当するビット数(1)を返します。
例
次のようなキーを持つ二分木:10 3 211 140162100および146
キー | 同等のバイナリ | ビット(出力)を設定 |
---|---|---|
10 | 1010 | 2 |
3 | 0011 | 2 |
211 | 11010011 | 5 |
140 | 10001100 | 3 |
162 | 10100010 | 3 |
100 | 1100100 | 3 |
146 | 10010010 | 3 |
ここでは、関数__builtin_popcountを使用しています
関数プロトタイプは次のとおりです-
int __builtin_popcount(unsigned int)
整数のセットビット数、つまり整数のバイナリ表現の1の数を返します。
アルゴリズム
START Step 1 -> create a structure of a node as struct Node struct node *left, *right int data End Step 2 -> function to create a node node* newnode(int data) node->data = data node->left = node->right = NULL; return (node) Step 3 -> Create function for generating bits of a node data void bits(Node* root) IF root = NULL return print __builtin_popcount(root->data) bits(root->left) bits(root->right) step 4 -> In main() create tree using Node* root = newnode(10) root->left = newnode(3) call bits(root) STOP
例
#include <bits/stdc++.h> using namespace std; // structure of a node struct Node { int data; struct Node *left, *right; }; //function to create a new node Node* newnode(int data) { Node* node = new Node; node->data = data; node->left = node->right = NULL; return (node); } //function for finding out the node void bits(Node* root){ if (root == NULL) return; //__builtin_popcount counts the number of set bit of a current node 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
-
C++プログラミングでツリーの奇数レベルにノードを出力します。
二分木が与えられた場合、プログラムはツリーの奇数レベルでノードを出力する必要があり、二分木のレベルは1からnまで始まります。 何も言及されていないので、2つのアプローチのいずれか、つまり再帰または反復を実装できます。 再帰的アプローチを使用しているため、プログラムは、奇数レベルのノードをフェッチして返す関数を再帰的に呼び出します。 上記の二分木で- Nodes at level 1: 10 Nodes at level 2: 3 and 211 Nodes at level 3: 140, 162, 100 and 146 したがって、レベル1とレベル3のノードが出力されます。
-
C++プログラミングのバイナリツリーの各ノードのセットビット数を出力します。
バイナリツリーが与えられると、関数はノードに格納されているキーのバイナリ値を生成し、そのバイナリに相当するビット数(1)を返します。 例 次のようなキーを持つ二分木:10 3 211 140162100および146 キー 同等のバイナリ ビット(出力)を設定 10 1010 2 3 0011 2 211 11010011 5 140 10001100 3 162 10100010 3 100 1100100 3 146 10010010 3 ここでは、関数_