algorithm - 多子ツリーを設計し、k 番目の祖先を見つける

Question

k複数のノードを持つツリーのデータ構造を与え、ノードのth 祖先を見つけるアルゴリズムを書きます。

データ構造は以下でよいでしょうか？

struct node
{
   int data;
   int n;
   struct node** child;
}

k番目の祖先を見つけることについて混乱しています。

Answer 1

次のようなツリーを考えてください。

          h
    d           l
 b     f     j     n
a c   e g   i k   m o

そして、次のようなメソッド: getParent(int k, char value)

If my call was getParent(3, 'm') it would return 'h'
The search would go: h->l->n->m; back three spots from m is h


If my call was getParent(2, 'e') it would return 'd'
The search would go: h->d->f->e; back two spots from e is d

Answer 2

はい、提供される構造は多子 (k-ary) ツリーになります。

しかし、その構造では、k 番目の祖先を見つけるための特に効率的なアルゴリズムを取得することはできません。必要な要素を見つけるために (ルートから) ツリー全体を再帰的に調べ、上に再帰する必要があります。 k 番目の祖先を検索します。

• 現在の要素が探しているものである場合は、 を返し0ます。
• 探している要素が子サブツリーの 1 つに含まれている場合 (つまり、呼び出しが を返さない場合-1):
  • その値が の場合、 - 番目の祖先kが見つかりました。k
  • それ以外の場合は、その値を返します+1。
• それ以外の場合は戻り-1ます。

実行時間は になりますO(n)。ここnで、 はツリー内のノードの数です。

別の構造が許可されている場合:

子ノード ポインターの代わりに / に加えて、各ノードの親ノード ポインターを格納できます。次に、目的の深さに到達するまで、単純に親ノードを繰り返し見ることができます。

実行時間はO(k)、k 番目の祖先を見つけたい場所です。