0

私は十分に単純な課題を持っています。この構造を使用してツリーを作成する必要があります。

 struct gennode
{
 int item;
 gennode * firstChild;
 gennode * siblingList;
 gennode * prevSibling;
 gennode * parent;
};

私の検索アルゴリズムはこれでした：

gennode* general::search(int element, gennode *t)
{
  if(t == NULL)
    {
      return t;
    }
  if(t->item == element)
    {
      return t;
    }
  if(t->firstChild != NULL)
    {
      return search(element, t->firstChild);
    }
    return search(element, t->siblingList);
}

何が問題なのかわかりません。すべての子を見つけたいわけではないようです。たとえば、ルートとして 1 があり、その子として 2、3、4 があり、2 の子として 5、6、7 があり、4 の子として 8、9 がある場合、検索で 2 の子を見つけることはできません。

問題がどこにあるのかわかりません。

編集: これは、1 をルートとし、2 と 3 を子とするツリーで gennode 構造がどのように見えるかの例です。

gennode * one;
gennode * two;
gennode * three;

one->item = 1;
one->firstChild = two;
one->siblingList = NULL;
one->prevSibling = NULL;
one->parent = NULL;

two->item = 2;
two->firstChild = NULL;
two->siblingList = three;
two->prevSibling = NULL;
two->parent = one;

three->item = 3;
three->firstChild = NULL;
three->siblingList = NULL;
three->prevSibling = two;
three->parent = one;
4

1 に答える 1

4

あなたの問題は、firstChild OR siblingListを検索するロジックにあるようです。つまり、firstChild がある場合、兄弟は決して見られません。ツリーが後ろから前に構築されている場合、ノード 4 が検索される理由を説明できるかもしれませんが、ノード 2 は検索されません。代わりに、おそらく search(element, t->firstChild) が成功するかどうかを確認し、成功しない場合はフォールスルーします。検索(要素、t->兄弟リスト):

if(t->firstChild != NULL)
{
  auto result = search(element, t->firstChild);
  if( result != nullptr )
    return result;
}
return search(element, t->siblingList);
于 2013-04-29T03:51:18.780 に答える