二分探索木

tunasalmon

8年前

二分探索木とは
サンプルプログラム

二分探索木とは

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

二分探索が実現しやすい構造になっています。
https://tunasalmon.com/2017/09/09/%e4%ba%8c%e5%88%86%e6%8e%a2%e7%b4%a2/

二分探索木 (出典)Wikipedia – 二分探索木 https://ja.wikipedia.org/wiki/%E4%BA%8C%E5%88%86%E6%8E%A2%E7%B4%A2%E6%9C%A8

図のように全ての親子関係に左部分木<親<右部分木の関係が成り立ちます。

サンプルプログラム

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

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

binary_search_tree_sample1.c

#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年度秋季試験問題)

(adsbygoogle = window.adsbygoogle || []).push({});