ページ 1 ／ 1
再帰関数を利用した深さ優先探索関数DFSの実装について
Posted: 2018年5月01日(火) 17:35
by snr
木構造を深さ優先探索する関数DFSの作成を目標にしています
コード:
typedef struct _treenode{
int data;
struct _treenode *left;
struct _treenode *right;
}Tree;
以上が木のデータ構造です。
これを再帰関数を使って深さ優先探索を実装したいのですが、
関数の定義は引数に制約があるため自作できません。
どうかご教授お願いいたします。
以下が関数とその引数です。
呼び出し時に木の根を引数にし、dataに探索するデータを入れることで、
データと一致するノードを返すという関数です。
コード:
Tree *dfs(Tree *node ,long data)
ネットで調べたのですが、やはり探索済みかどうかを記録したり
など変数を作っていましたが、それは今回の制約の外で
実際、そういった変数は必要なく、コールスタックを利用することで
作れるそうです。
Re: 再帰関数を利用した深さ優先探索関数DFSの実装について
Posted: 2018年5月01日(火) 20:31
by かずま
グラフなら探索済み変数が必要かもしれませんが、
木構造なら不要だと思います。
コード:
#include <stdio.h>
typedef struct _treenode {
int data;
struct _treenode *left;
struct _treenode *right;
} Tree;
Tree *dfs(Tree *node, long data)
{
Tree *p;
if (node->data == data) return node;
if (node->left && (p = dfs(node->left, data))) return p;
if (node->right && (p = dfs(node->right, data))) return p;
return NULL;
}
Tree root[] = {
{ 1, root+1, root+3 },
{ 2, root+2, NULL },
{ 3, root+4, root+5 },
{ 4, NULL, NULL },
{ 5, NULL, NULL },
{ 6, NULL, NULL },
};
int main(void)
{
int data = 5;
Tree *p = dfs(root, data);
if (p)
printf("%d found\n", p->data);
else
printf("%d not found\n", data);
}
root[] は自分で図を書いてみてくださいね。
Re: 再帰関数を利用した深さ優先探索関数DFSの実装について
Posted: 2018年5月01日(火) 21:18
by snr
回答ありがとうございます
図を描いて、動作することを確認しました。
自分には難解ですが時間をかけてみようと思います