メインコンテンツへ移動
黯羽軽揚毎日少しずつ

二進木 (Binary Tree) 関連アルゴリズムの実装

無料2015-03-17#Math#二叉树

本稿は主に二進木関連アルゴリズムの C 言語実装について議論し、木の作成、3 種類の走査方法（再帰と非再帰）、葉ノードの出力、木の深さの計算、木形式の出力、階層別インデント出力、階層順出力、根から指定ノードへのパスの計算を含む

no_mkd

はじめに：

二進木は比較的単純なデータ構造であり、その関連アルゴリズムを理解し熟練して掌握することは複雑なデータ構造の学習に大いに有益です

一。二進木の作成

[理論が嫌いな方はここをクリックしてスキップ>>]

いわゆる二進木の作成とは、実はコンピュータにこの特殊なデータ構造を記憶させることです（どこが特殊か？それは私たちが自定义したものであるという点です）

まず、コンピュータ内部の記憶は線形的ですが、私たちの木構造は階層的であり、コンピュータは明らかに理解できません。コンピュータが受け入れられる原始データ型は私たちのニーズを満たせません

そのため、階層関係を表すためにデータ構造を自定义するしかありません

実際には構造 + 操作を定義する必要があります。構造は操作に奉仕するものです。例を挙げると、切符購入のプロセスをシミュレートする場合、既存のデータ構造ではニーズを満たせません（配列について言わないでください...）。必要な操作は以下の通りかもしれません：

1. 切符購入列の最前列に立っている人を取得；2. 切符を購入した人を列から除外；3. 最初の人が切符を購入した後、その後ろの全員が「自発的」に前に移動

この 3 つの操作を明確にし、操作に基づいて構造を定義し、最後にキュー（配列/リンクリスト + 対応する関数）を得ました

二進木も同様で、コンピュータが見ているのは構造 + 操作です。構造は Node 集合（二進リンクリスト）であり、操作は作成、走査、検索などの関数です

ノード：

struct bt
{
	char data;
	struct bt *left;
	struct bt *right;
};

ノードはバケツのようなもので、両手があります（バケツにはデータが入っており、両手を伸ばして左右の子供を掴みます）

操作：

//createBT();
//printBT();
//deleteNode(Node node);
//...

-上記は二進木の理解であり、以下は二進木作成の具体的な実装です-

二進木の作成プロセスは実は走査プロセスです（ここでは再帰方式を指します）。二進木のいずれの走査方式も木構造を線形化できることがわかります（簡単に言えば、一組の走査結果で一つの二進木を一意に表せます）。したがって、走査結果に基づいて二進木を復元できます

先行走査で再帰的に木を構築する具体的な考え方：

1. 現在の根ノードのデータを読み込む；2. 空白の場合は現在の根を空に設定し、そうでなければ新しいノードを申請し、データを保存；3. 現在の根ノードの左ポインタと右ポインタで再帰呼び出しを行い、左右の部分木を作成

言語での説明は理解しにくいかもしれないので、コードを以下に示します：

struct bt
{
	char data;
	struct bt *left;
	struct bt *right;
};

void createBT(struct bt ** root)
{
char c;
c=getchar();
if(c == ' ')*root=NULL;//空白の場合は空に設定
else
{
*root=(struct bt *)malloc(sizeof(struct bt));//新しいノードを申請
(*root)->data=c;//データを保存
createBT(&((*root)->left));//現在のノードの左部分木を構築
createBT(&((*root)->right));//現在のノードの右部分木を構築
}
}

例えば、二進木 a(b, c) を構築したい場合、その先行走査結果 ab××c××を入力すればよいです（×は空白を表します）。他の 2 つの木構築方式もこれと類似しており、詳しくは述べません。非再帰的な木構築方法については以下の非再帰走査を参照してください。非常に類似しています

二。走査

走査には実装方式において再帰と非再帰の 2 種類があります。いわゆる非再帰は実は再帰から変換されたものです（手動でスタックを維持）。オーバーヘッド（メモリ/時間）においては非再帰の方が良いかもしれません。結局、オペレーティングシステムのスタックで維持される情報の方が多く、現場の保存と回復のオーバーヘッドも大きいためです

走査順序には 3 種類あります：1. 先行走査（根 - 左 - 右）；2. 中順走査（左 - 根 - 右）；3. 後順走査（左 - 右 - 根）

例を挙げると、二進木 a(b, c(d, e)) の 3 種類の走査結果はそれぞれ：1.abcde；2.badce；3.bdeca です

-以下に後順走査の再帰と非再帰実装を示します。他のものはこれと類似しています-

後順走査 再帰：

void postOrder(struct bt * root)
{
	if(root == NULL)return;
	else
	{
		postOrder(root->left);
		postOrder(root->right);
		putchar(root->data);
	}
}

後順走査 非再帰：

void postOrder(struct st* root)
{
	struct st* stack[100];//ノードスタックを宣言
	int top=-1;//スタックトップインデックス
	struct bt* p=root;//現在のノード（present）
	struct bt* q=NULL;//前回処理したノード
	while(p!=NULL||top!=-1)
	{
		for(;p!=NULL;p=p->left)stack[++top]=p;//左部分木を走査
		if(top!=-1)
		{
			p=stack[top];
			if(p->right==NULL||p->right==q)//右子供がない、または右子供がすでに走査済み
			{
				putchar(p->data);//根ノードを出力
				q=p;
				p=stack[top];
				top--;
				p=NULL;
			}
			else p=p->right;//右部分木を走査
		}
	}
}

より明確に説明するために、上記では直接スタックの操作を実装しました。もちろん、より規範的な做法はスタックを独立したデータ構造としてカプセル化し、私たちの関数でスタックが提供する操作関数を呼び出して関連操作を行うことです

三。葉ノードの出力

特定のノードを検索する一連の操作はすべて走査を基礎としており、葉ノードの出力もその一例です。葉ノードが満たす条件は左右の子供がすべて空であることです。走査にこのような判断条件を追加するだけでよいです

//ここでは先行走査を採用
void printLeaves(struct bt* root)
{
	if(root == NULL)return;
	else
	{
		if(root->left == NULL&&root->right == NULL)putchar(root->data);
		else
		{
			printLeaves(root->left);
			printLeaves(root->right);
		}
	}
}

これと類似した操作には、二進木中で一定の条件を満たすノードを出力する、指定ノードを削除する、指定位置にノード（部分木）を追加する...などがあります。すべて走査を基礎としていくつかの追加操作を行うものです

四。木の深さの計算

木の深さを計算するには複数の方式があります。例えば：1. それぞれ根の下の左右部分木の高さを計算し、そのうちの大きい方を木の深さとする；2. 最大再帰深度を木の深さとする...

私たちは第一の方式を採用します。より明確です

int btDepth(struct bt* root)
{
	int rd,ld;
	if(root==NULL)return 0;//空木の深さは 0
	else
	{
		ld=1+btDepth(root->left);//再帰的に層を進み、深さを 1 加算
		rd=1+btDepth(root->right);//再帰的に層を進み、深さを 1 加算
		return ld > rd ? ld : rd;//最大値を返す
	}
}

五。木形式出力

いわゆる木形式出力とは、自然表現の二進木を反時計回りに 90 度回転させることです。実は依然として走査プロセス中に再帰層数を記録し、これによって出力結果を確定します

//depth は再帰深度を表し、初期値は 0
void btOutput(struct bt* root,int depth)
{
	int k;
	if(root==NULL)return;
	else
	{
		btOutput(root->right,depth+1);//右部分木を走査
		for(k=0;k<depth;k++)
			printf(" ");//再帰層数が幾つかによって、いくつかの空白を出力（数インデント）
		putchar(root->data);printf("\n");
		btOutput(root->left,depth+1);//左部分木を走査
	}
}
//「右 - 中 - 左」の走査順序は「逆中順」走査と呼ばれ、この順序を採用するのは出力規則（反時計回り 90 度）に合致させるためです

六。階層別インデント出力

階層別インデント出力はコードエディタ中の自動インデントのようです。根ノードから始めて逐層インデントします。上記のコードを少し変更するだけで実現できます

//k は依然として再帰深度を表し、初期値は 0
void indOutput(struct bt* root,int k)
{
	int i;
	if(root!=NULL)
	{
		for(i=1;i<=k;i++)
			putchar(' ');
		putchar(root->data);putchar('\n');
		indOutput(root->left,k+1);
		indOutput(root->right,k+1);
	}
	else return;
}
//階層別インデント出力と木形式出力の唯一の違いは走査方式が異なることで、前者は先行走査、後者は逆中順走査です

七。階層順出力

階層順出力は前述の 2 種類の出力方式と似ているように見えますが、実際には大きな違いがあります。少なくとも、いずれの走査プロセスもこの目標を達成するために単純に套用することはできません。そのため、キューを維持して走査順序を制御するしかありません

void layerPrint(struct bt* root)
{
	struct bt* queue[100];//ノードキューを宣言
	struct bt* p;//現在のノード
	int amount=0,head,tail,j,k;//キュー関連属性（要素総数、キュー先頭、キュー末尾インデックス）
	queue[0]=root;
	head=0;
	tail=1;
	amount++;
	while(1)
	{
		j=0;
		for(k=0;k<amount;k++)
		{
			p=queue[head++];//キュー先頭要素を取得
			if(p->left!=NULL)
			{
				queue[tail++]=p->left;//あれば左子供を記録
				j++;
			}
			if(p->right!=NULL)
			{
				queue[tail++]=p->right;//あれば右子供を記録
				j++;
			}
			putchar(p->data);//現在のノード値を出力
		}
		amount=j;//カウンタを更新
		if(amount==0)break;
	}
}

八。根から指定ノードへのパスの計算

パスを記録するには、もちろん再帰方式は適していません。ここでは後順走査の非再帰実装を採用します。なぜ後順走査を選択するのか？

この走査方式では、ある瞬間のスタック内の既存ノードがまさに根ノードから現在のノードへのパスだからです（スタック底からスタックトップまで）。厳密に言えば、この時キューを使用してパスを保存すべきです。スタックはスタック底からスタックトップまでの出栈操作をサポートしないためです（このような細かい詳細は省略しましょう...）

//パラメータ c は指定ノード値
void printPath(struct bt* root,char c)
{
	struct st* stack[100];//ノードスタックを宣言
	int top=-1;//スタックトップインデックス
	int i;
	struct bt* p=root;//現在のノード
	struct bt* q=NULL;//前回処理したノード
	while(p!=NULL||top!=-1)
	{
		for(;p!=NULL;p=p->left)stack[++top]=p;//左部分木を走査
		if(top!=-1)
		{
			p=stack[top];//スタックトップ要素を取得
			if(p->right==NULL||p->right==q)//現在のノードに右子供がない、または右子供が直前にアクセスされた
			{
				if(p->data==c)//見つかった場合、パスを出力
				{
					for(i=0;i<=top;i++)
					{
						p=stack[i];
						putchar(p->data);
					}
					printf("\n");
					//ここではループを抜けない。一意でないノード値が存在する可能性があるため、木全体を走査してすべてのパスを見つける
				}
				q=p;
				p=stack[top];
				top--;
				p=NULL;
			}
			else p=p->right;//右部分木を走査
		}
	}
}

九。完全ソースコードとスクリーンショット例

ソースコード：

#include<stdio.h>

struct bt
{
char data;
struct bt *left;
struct bt *right;
};


void createBT(struct bt ** root)
{
char c;
c=getchar();
if(c == ' ')*root=NULL;
else
{
*root=(struct bt *)malloc(sizeof(struct bt));
(*root)->data=c;
createBT(&((*root)->left));
createBT(&((*root)->right));
}
}


void preOrder(struct bt * root)
{
if(root == NULL)return;
else
{
putchar(root->data);
preOrder(root->left);
preOrder(root->right);
}
}


void inOrder(struct bt * root)
{
if(root == NULL)return;
else
{
inOrder(root->left);
putchar(root->data);
inOrder(root->right);
}
}


void printLeaves(struct bt* root)
{
if(root == NULL)return;
else
{
if(root->left == NULL&&root->right == NULL)putchar(root->data);
else
{
printLeaves(root->left);
printLeaves(root->right);
}
}
}


int btDepth(struct bt* root)
{
int rd,ld;
if(root==NULL)return 0;
else
{
ld=1+btDepth(root->left);
rd=1+btDepth(root->right);
return ld > rd ? ld : rd;
}
}


void btOutput(struct bt* root,int depth)
{
int k;
if(root==NULL)return;
else
{
btOutput(root->right,depth+1);
for(k=0;k<depth;k++)
printf(" ");
putchar(root->data);printf("\n");
btOutput(root->left,depth+1);
}
}


void postOrder(struct st* root)
{
struct st* stack[100];
int top=-1;
struct bt* p=root;
struct bt* q=NULL;
while(p!=NULL||top!=-1)
{
for(;p!=NULL;p=p->left)stack[++top]=p;
if(top!=-1)
{
p=stack[top];
if(p->right==NULL||p->right==q)
{
putchar(p->data);
q=p;
p=stack[top];
top--;
p=NULL;
}
else p=p->right;
}
}
}


void printPath(struct bt* root,char c)
{
struct st* stack[100];
int top=-1;
int i;
struct bt* p=root;
struct bt* q=NULL;
while(p!=NULL||top!=-1)
{
for(;p!=NULL;p=p->left)stack[++top]=p;
if(top!=-1)
{
p=stack[top];
if(p->right==NULL||p->right==q)
{
if(p->data==c)
{
for(i=0;i<=top;i++)
{
p=stack[i];
putchar(p->data);
}
printf("\n");
}
q=p;
p=stack[top];
top--;
p=NULL;
}
else p=p->right;
}
}
}


void layerPrint(struct bt* root)
{
struct bt* queue[100];
struct bt* p;
int amount=0,head,tail,j,k;
queue[0]=root;
head=0;
tail=1;
amount++;
while(1)
{
j=0;
for(k=0;k<amount;k++)
{
p=queue[head++];
if(p->left!=NULL)
{
queue[tail++]=p->left;
j++;
}
if(p->right!=NULL)
{
queue[tail++]=p->right;
j++;
}
putchar(p->data);
}
amount=j;
if(amount==0)break;
}
}


void indOutput(struct bt* root,int k)
{
int i;
if(root!=NULL)
{
for(i=1;i<=k;i++)
putchar(' ');
putchar(root->data);putchar('\n');
indOutput(root->left,k+1);
indOutput(root->right,k+1);
}
else return;
}


void main()
{
char c;
struct bt * root;
printf("先行走査結果を入力してください：");
createBT(&root);
printf("先行走査 (preOrder)[再帰]: \n");
preOrder(root);
printf("\n中順走査 (inOrder)[再帰]: \n");
inOrder(root);
printf("\n後順走査 (postOrder)[非再帰]: \n");
postOrder(root);
printf("\n葉ノード (leaves): \n");
printLeaves(root);
printf("\n深さ (depth): \n");
printf("%d\n",btDepth(root));
printf("木形式出力 (tree output): \n");
btOutput(root,0);
printf("インデント出力 (indentation output): \n");
indOutput(root,0);
printf("目標ノードを入力してください (target node): ");
getchar();
c=getchar();
printf("パス (path): \n");
printPath(root,c);
printf("階層出力 (layerPrint): \n");
layerPrint(root);
printf("\n");
}

スクリーンショット例：

比較的複雑な二進木：

その先行走査結果は：ABD××EG×××C×FH××I××（×は空を表し、入力する際に×を空白に置き換える必要があります）

D を H に変更して再度試す（重複要素が存在するため、H への 2 つのパスがあるはずです）

コメント

コメントはまだありません

コメントを書く