二分探索木

目次

二分探索木とは

二分探索木は木構造の一つで、全てのノードは左部分木より大きく右部分木より小さいという特徴があります。

二分探索が実現しやすい構造になっています。

サンプルプログラム

今回はこのデータ構造を構造体で表現します。

構造体nodeにはデータのほかに、左右の部分木へのポインタをもっています。
このサンプルコードではデータの追加と検索を実装していますが、どちらもキー値の大小により分岐して再帰呼び出しをしています。

#include <stdio.h>

struct node
{
	int data;
	struct node *left;
	struct node *right;
};

struct node *addNode(int data, struct node *n)
{
	if (n == NULL)
	{
		struct node newNode;
		n = &newNode;
	}
	else
	{
		if (data < n->data)
			n->left = addNode(data, n->left);
		else
			n->right = addNode(data, n->right);
	}

	return n;
}

struct node *searchNode(int data, struct node *n)
{
	if (n == NULL)
		return NULL;
	else if (data == n->data)
		return n;
	else if (data < n->data)
		return searchNode(data, n->left);
	else
		return searchNode(data, n->right);
}

int main(void)
{
	struct node *n = NULL;

	addNode(4, n);
	addNode(3, n);
	addNode(9, n);
	addNode(1, n);
	addNode(5, n);
	addNode(7, n);

	return 0;
}

(参考:応用情報技術者試験27年度秋季試験問題)


「二分探索木」への2件のフィードバック

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です