C++で二分木の奇数レベルのみを出力するプログラム
本記事では、二分木（バイナリツリー）のうち奇数番目のレベル（1層目・3層目・5層目…）に存在するノードだけを順に出力するC++プログラムを紹介します。
アルゴリズム
使用する構造体と各関数の処理の流れを、擬似コードで以下に示します。
Begin 構造体 nod を宣言する 整数型のメンバ d を宣言 構造体 nod へのポインタ l を宣言 構造体 nod へのポインタ r を宣言 関数 struct nod* newNod(int d) を呼び出す 関数 struct nod* newNod(int d) を定義 構造体 nod へのポインタ node を宣言 node = (struct nod*) malloc(sizeof(struct nod)) で初期化 node->d = d node->l = NULL node->r = NULL node を返す 関数 printLevel(struct nod* root, int lvl) を呼び出す 関数 printLevel(struct nod* root, int lvl) を定義 if (root == NULL) ならば return if (lvl == 1) ならば root->d の値を出力 else if (lvl > 1) ならば printLevel(root->l, lvl - 1) を呼び出す printLevel(root->r, lvl - 1) を呼び出す 関数 height(struct nod* node) を呼び出す 関数 height(struct nod* node) を定義（木の高さを計算） if (node == NULL) ならば return 0 else ならば int lhght = height(node->l) int rhght = height(node->r) if (lhght > rhght) ならば return (lhght + 1) else ならば return (rhght + 1) 関数 printLevelOrder(struct nod* root) を定義 整数型の h を宣言し、h = height(root) で初期化 整数型の i を宣言 for (i = 1; i <= h; i+=2) printLevel(root, i) を呼び出す 木に値を挿入する 「Odd numbered Level Order traversal of binary tree is」を出力 printLevelOrder(root) を呼び出す End
サンプルコード
以下が実際のC++による実装例です。再帰的に高さを求め、奇数レベルごとにノードの値を表示しています。
#include <iostream>
#include<stdlib.h>
using namespace std;
struct nod {
int d;
struct nod* l;
struct nod* r;
};
struct nod* newNod(int d);
struct nod* newNod(int d) {
struct nod* node = (struct nod*) malloc(sizeof(struct nod));
node->d = d;
node->l = NULL;
node->r = NULL;
return (node);
}
void printLevel(struct nod* root, int lvl);
void printLevel(struct nod* root, int lvl) {
if (root == NULL)
return;
if (lvl == 1)
printf("%d ", root->d);
else if (lvl > 1) {
printLevel(root->l, lvl - 1);
printLevel(root->r, lvl - 1);
}
}
int height(struct nod* node);
int height(struct nod* node) {
if (node == NULL)
return 0;
else {
int lhght = height(node->l);
int rhght = height(node->r);
if (lhght > rhght)
return (lhght + 1);
else
return (rhght + 1);
}
}
void printLevelOrder(struct nod* root) {
int h = height(root);
int i;
for (i = 1; i <= h; i+=2)
printLevel(root, i);
}
int main() {
struct nod *root = newNod(7);
root->l = newNod(6);
root->r = newNod(4);
root->l->l = newNod(3);
root->l->r = newNod(5);
root->r->l = newNod(2);
root->r->r = newNod(1);
cout<<"Odd numbered Level Order traversal of binary tree is \n";
printLevelOrder(root);
return 0;
}実行結果
Odd numbered Level Order traversal of binary tree is 7 3 5 2 1
解説
このサンプルでは、レベル1に「7」、レベル2に「6」「4」、レベル3に「3」「5」「2」「1」が配置されています。printLevelOrder関数はループ変数を2ずつ増やしながらprintLevelを呼び出すため、レベル1とレベル3のノード値である「7 3 5 2 1」のみが出力されます。
-
C++で二分木のすべてのノードのレベルを出力する方法
二分木（バイナリツリー）が与えられたとき、各ノードに格納されたすべてのキーについて、そのノードが属するレベル（根をレベル1として数える）を出力するのが本記事の目的です。上記の木では、ノードは次のように配置されています。10 はレベル 1 3 と 211 はレベル 2 140、162、100、146 はレベル 3特定のキーが与えられた場合、プログラムはそのキーが属するレベルを出力できなければなりません。入出力例入力: 10 3 211 140 162 100 146 出力: 10 のレベルは 1 3
-
C++でAVL木（AVLツリー）を実装する方法：回転操作とサンプルコードを徹底解説
AVL木とは AVL木（AVL Tree）は、自己平衡型二分探索木（Self-balancing Binary Search Tree）の一種です。すべてのノードにおいて、左部分木と右部分木の高さの差が「1以下」に保たれるという性質を持っています。この平衡条件により、木が片側に偏って成長することを防ぎ、検索・挿入・削除といった操作を常に効率的（O(log n)）に行うことができます。 木の回転（Tree Rotation）とは 木の回転とは、要素の順序（ソート順）を崩すことなく木の構造を変更する操作のことです。あるノードを一段上へ移動させ、別のノードを一段下へ移動させることで実現されます。 回