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）：
  • 如果该值为k，则我们找到了k第 - 个祖先。
  • 否则返回该值+1。
• 否则返回-1。

运行时间将是O(n)，其中n是树中的节点数。

如果我们被允许使用不同的结构：

除了 / 之外，我们还可以为每个节点存储一个父节点指针，而不是子节点指针。然后我们可以简单地迭代地查看父节点，直到达到所需的深度。

运行时间将是O(k)，我们要在其中找到第 k 个祖先。