データ構造学習ノート＜4＞二分木

一、木とは何か#

1. 木の定義#

木（Tree）：n（n≥0）個のノードから構成される有限集合。
n=0 のとき、空の木と呼ぶ；
任意の非空の木（n>0）について、以下の性質を持つ：

木には「根（Root）」と呼ばれる特別なノードがあり、r で表す。
残りのノードは m（m>0）個の互いに交わらない有限集合 T1、T2、……、Tm に分けられ、それぞれの集合自体も木であり、元の木の「部分木（SubTree）」と呼ばれる。
部分木は交わらない。
根ノードを除いて、各ノードはちょうど 1 つの親ノードを持つ；
N 個のノードを持つ木にはN-1 本の辺がある。

2. 木の基本用語#

1. ノードの次数（Degree）：ノードが持つ子ノードの数
2. 木の次数： 最大のノードの次数を木の次数と呼ぶ
3. 葉ノード（Leaf）： 次数が 0 のノード
4. 親ノード（Parent）： 前のノードがある場合、その前のノードを親ノードと呼び、前のノードがない場合、この属性は親ノードを持たない。
5. 子ノード（Child）： A ノードが B ノードの親ノードである場合、B ノードは A ノードの子ノードと呼ばれる；子ノードは子供ノードとも呼ばれる。
6. 兄弟ノード（Sibling）： 同じ親ノードを持つノード同士は兄弟ノードである。
7. パスとパスの長さ：ノード n1 から nk へのパスはノードの列 n1、n2、……、nk であり、ni は ni+1 の親ノードである。パスに含まれる辺の数がパスの長さである
8. 祖先ノード（Ancestor）： 木の根からあるノードへのパス上のすべてのノードはそのノードの祖先ノードである。
9. 子孫ノード（Descendant）：あるノードの部分木に含まれるすべてのノードはそのノードの子孫である。
10. ノードのレベル（Level）： 根ノードは 1 レベルとし、他の任意のノードのレベルはその親ノードのレベルに 1 を加えたものである。
11. 木の深さ（Depth）：木のすべてのノードの最大レベルがこの木の深さである。
12. 森： m 本の互いに交わらない木の集合

二、木の表現#

1. 子 - 兄弟表現法#

ここに画像の説明を挿入

三、二分木#

1. 定義#

二分木 T: 有限のノード集合。
このノードは空であってもよい。
空でない場合、根ノードとその左部分木 TLおよび右部分木 TRという 2 つの互いに交わらない二分木から構成される。
二分木には具体的に 5 つの基本形態がある：a 空の木 b ノードが 1 つだけ c ノードが 1 つと左部分木 d ノードが 1 つと左部分木 e ノードが 1 つと左右部分木。
ここに画像の説明を挿入
PS：二分木の部分木には左右の順序がある。

いくつかの特殊な二分木
ここに画像の説明を挿入
二分木の抽象データ型の定義
型名：二分木
データオブジェクト集合：有限のノード集合。
空でない場合、根ノードとその左、右の二分部分木から構成される。
操作集合：BT∈BinTree，Item∈ElementType，重要な操作は：

Boolean IsEmpty (BinTree BT); //BT が空かどうかを判定
void Traversal (BinTree BT); // ある順序でノードを訪問する；
BinTree CreatBinTree (); // 二分木を作成する

一般的な遍歴方法は：

void PreOrderTraversal(BinTree BT); //先行順序--- 根、左部分木、右部分木
void InOrderTraversal(BinTree BT); //中間順序--- 左部分木、根、右部分木
void PostOrderTraversal(BinTree BT); //後行順序--- 左部分木、右部分木、根
void LevelOrderTraversal(BinTree BT); //レベル順序遍歴、上から下、左から右

2. 二分木のいくつかの重要な性質#

二分木の第 i 層の最大ノード数は 2^i-1^、i≥1。
深さが kの二分木の最大ノード数は 2^k^-1、k≥1。
任意の非空の二分木 T について、n0 が葉ノードの数、n2 が次数 2 の非葉ノードの数を表すとき、両者は関係 n0=n2+1 を満たす。
n 個のノードを持つ完全二分木の深さ kは必ずlog~2~n+1である。

3. 二分木のストレージ構造#

1、順序ストレージ構造#

完全二分木：上から下、左から右の順序でn個のノードをストレージするノードの親子関係

根ノードでないノード（番号 i > 1）の親ノードの番号は [i / 2] ;(切り捨て)
ノード（番号 i）の左の子の番号は 2i(2i ≤ n、さもなくば左の子は存在しない)
ノード（番号 i）の右の子の番号は 2i+1(2i + 1 ≤ n、さもなくば右の子は存在しない)

一般的な二分木もこの順序ストレージ構造を採用できるが、スペースの無駄が生じる。

満二分木：最後の層に子ノードが存在しない場合を除き、各層のすべてのノードが 2 つの子ノードを持つ二分木で、完全二分木とは異なる。ここに画像の説明を挿入

2、連結ストレージ#

(1) 定義#

typedef struct TreeNode *BinTree;
typedef BinTree Position;
struct TreeNode {
		ElementType Data;
		BinTree Left;
		BinTree Right;
}

(2) 遍歴（再帰的実装）#

先行順序遍歴：

1. まず根ノードを訪問；
2. その左部分木を先行順序遍歴；
3. その右部分木を先行順序遍歴。

void PreOrderTraversal(BinTree BT) {
	if(BT) {
		printf("%d", BT->Data);
		PreOrderTraversal( BT->Left);
		PreOrderTraversal( BT->Right);
	}
}

中間順序遍歴：

1. その左部分木を中間順序遍歴；
2. 根ノードを訪問；
3. その右部分木を中間順序遍歴。

void InOrderTraversal(BinTree BT) {
	if(BT) {
		InOrderTraversal( BT->Left);
		printf("%d", BT->Data);
		InOrderTraversal( BT->Right);
	}
}

後行順序遍歴：

1. その左部分木を後行順序遍歴；
2. その右部分木を後行順序遍歴；
3. 根ノードを訪問。

void PostOrderTraversal(BinTree BT) {
	if(BT) {
		PostOrderTraversal( BT->Left);
		PostOrderTraversal( BT->Right);
		printf("%d", BT->Data);
	}
}

(2) 遍歴（非再帰的実装）#

基本的な考え方：スタックまたはキューを使用する。

中間順序遍歴の非再帰的アルゴリズム

ノードに出会ったら、それをスタックにプッシュし、その左部分木を遍歴する；
左部分木の遍歴が終了したら、スタックのトップからこのノードをポップし、訪問する；
その後、右ポインタに従ってこのノードの右部分木を中間順序遍歴する。

void InOrderTraversal(BinTree BT) {
	BinTree T = BT;
	Stack S = CreatStack(MaxSize);//スタックSを作成し初期化
	while( T || !IsEmpty(S) ) {
		while(T) {//左に進み、途中のノードをスタックにプッシュ
			Push(S, T);
			T = T->Left;
		}
		if( !IsEmpty(S) ) {
			T = Pop(S);	//ノードをスタックからポップ
			printf("%5d", T->Data);//ノードを訪問
			T = T->Right;//右部分木に移動
		}
	}
}

レベル順序遍歴

一時的に訪問しないノードを保存するストレージ構造が必要（スタック、キュー）
キュー実装：根ノードから遍歴を開始し、まず根ノードをキューに入れる。その後、ループを実行する：ノードをキューから出し、そのノードを訪問し、その左右の子をキューに入れる。
1. 根ノードをキューに入れる；
2. キューから要素を取り出す；
3.その要素が指すノードを訪問；
4. その要素が指すノードの左、右の子ノードが空でない場合、その左、右の子のポインタを順にキューに入れる。

void LevelOrderTraversal(BinTree BT) {
	Queue Q;  BinTree T;
	if ( !BT ) return;	//空の木の場合は直接戻る
	Q = CreateQueue(MaxSize);//キューQを作成し初期化
	AddQ(Q, BT);
	while( !IsEmpty(Q) ) {
		T = DeleteQ(Q);
		printf("%d\n", T->Data);//ノードを訪問
		if(T->Left) AddQ(Q, T->Left);//左の子をキューに入れる
		if(T->Right) AddQ(Q, T->Right);//右の子をキューに入れる
	}
}

補足知識
データ管理の基本操作である探索：特定のキーワード K に基づいて、集合 R から K と同じキーワードを持つレコードを見つける。静的探索と動的探索に分かれる。
静的探索：集合内のレコードは固定されており、挿入や削除操作はなく、探索のみ。
方法 1：順序探索（哨兵の概念：配列の境界に値を設定し、哨兵に出会ったらループを終了できるため、分岐判断を 1 つ減らせる）複雑度 O (n);
方法 2：二分探索（前提：配列が連続しており、順序がある）
動的探索：集合内のレコードが動的に変化し、探索の他に挿入や削除が発生する可能性がある。