algorithm - 设计一棵多子树并找到第 k 个祖先

Question

为具有多个节点的树提供一个数据结构，并编写一个算法来查找节点的第 k 个祖先。

数据结构可以是下面的吗？

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

我对找到第 k 个祖先感到困惑。

Answer 1

是的，提供的结构将是一个多子(k-ary)树。

但是，使用该结构，您不会获得特别有效的算法来查找第 k 个祖先 - 您将不得不递归地查看整个树(从根开始)以找到所需的元素，并向上递归找到第 k 个祖先。

• 如果当前元素是我们要查找的元素，则返回0。
• 如果其中一个子树包含我们要查找的元素(即调用不返回 -1):
  • 如果该值为 k，我们找到了第 k 个祖先。
  • 否则返回该值 +1。
• 否则返回-1。

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

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

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

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