二分木構造

昨日と今日で二分木構造の写経が完了しました。

最近は写経ばっかりで、どこまで理解してて、
どんだけ上達してるのか、よくわからないなぁ

つまみ食い勉強法とか言うように、ほかの言語も合わせて勉強しなきゃ

でも、C言語は覚えときたいしなぁ〜
ということで、ここからは二分木構造についてのお話です。

• 二分木構造とは？

二分木構造はノードと呼ばれる構造体に大小関係を持つリンクを持たせることで木のように構成されたデータ構造をさします。

一般的な二分木構造のノード構造体を以下に表します。

typedef struct node {

	struct node *left;

	struct node *right;

	int count;

	char *pstr;

} NODE;

このように1つの構造体の中に2つのリンクを持っています。
一般的に、leftがより小さいノードを持つポインタで
rightはより大きいノードを持つポインタとして定義されることが多いです。

countは同じ値のようその数を保持します。

pstrはそのノードが持つ実データ用のポインタです。

• 概要

基本的な考え方を説明したいと思います。

二分木構造では1つのノードが2つのリンクを持ち、
そのリンクの先のノードがさらに2つのリンクを持ち。。。

という風に増加していきます。

そして、データ構造が作られる際に2つのリンクに対して
ノード自身を基準とした大小関係を考慮して格納されていきます。
そのため、二分木構造は構造が完成した時点で、二分木探索と同等の
意味を持つことになります。

また、再帰関数を用いることで、動的にメモリの確保が行えます。