n叉树的最低共同祖先

Question

我正在尝试找出二叉树的最低公共祖先。这是我在 C++ 中尝试过的，但程序停止工作（运行时间错误）。有人可以建议我如何改进吗？

此外，我知道这个程序将输出给定节点的最右边的祖先，但我无法找到找到正确 LCA 的方法？

#include<cstdio>
#include<iostream>
using namespace std;
#define MARKER ')'
#define N 5
using namespace std;

// A node of N-ary tree
struct Node {
   char key;
   Node *child[N];  // An array of pointers for N children
};


Node *newNode(char key)
{
    Node *temp = new Node;
    temp->key = key;
    for (int i = 0; i < N; i++)
        temp->child[i] = NULL;
    return temp;
}

int height(struct Node *root)
{
    if(root==NULL)
        return 0;
    int hg[N];
    int maxx=-9999;
    for(int i=0;i<N;i++)
    {
        hg[i]=height(root->child[i])+1;
        if(hg[i]>maxx)
        maxx=hg[i];
    }
    return maxx;
}
int size(struct Node*root)
{
    int sz=1;
    if(root==NULL)
    return 0;
   else
   {
    for(int i=0;i<N;i++) sz=sz+size(root->child[i]);
   } 
   return sz;
}

struct Node *LCA(struct Node *a,struct Node *b, struct Node *root)
    {
        cout<<a->key<<" "<<b->key<<endl;
        if(a==root || b==root)
            return root;


        struct Node *temp=NULL;

       for(int i=0;i<N;i++)
        {
            struct Node *res=LCA(a,b,root->child[i]);
            if(res!=NULL)
            {
                temp=res;
            }
        }

        return temp;
}

Node *createDummyTree()
{
    Node *root = newNode('A');
    root->child[0] = newNode('B');
    root->child[1] = newNode('C');
    root->child[2] = newNode('D');
    root->child[0]->child[0] = newNode('E');
    root->child[0]->child[1] = newNode('F');
    root->child[2]->child[0] = newNode('G');
    root->child[2]->child[1] = newNode('H');
    root->child[2]->child[2] = newNode('I');
    root->child[2]->child[3] = newNode('J');
    root->child[0]->child[1]->child[0] = newNode('K');
    return root;
}


void traverse(Node *root)
{
    if (root)
    {
        printf("%c ", root->key);
        for (int i = 0; i < N; i++)
            traverse(root->child[i]);
    }
}

int main()
{
        Node *root = createDummyTree();
        cout<<height(root)<<endl;
        cout<<size(root)<<endl;
        cout<<LCA(root->child[2]->child[0],root->child[2]->child[1],root)->key<<endl;


    return 0;
}

Answer 1

如果您要在只有向下指针的 n 叉树中查找 lca，您希望在树中搜索最低的节点，该节点认为 a 和 b 都可以从试试这个角度

我建议创建一个方法来判断 a 是否是 b 的后代。然后我会创建一个方法来接收一个节点、祖先节点和另外两个节点 a 和 b，然后说：a 和 b 是否可以从祖先节点到达？然后我将有一个执行以下操作的函数：对于每个儿子，我儿子可以访问 a 和 b，return 与那个儿子一起调用的递归函数的结果。如果没有儿子满足这个要求，我会 return 父亲，如果 a 和 b 可以从他那里得到。然后我将调用第三个方法，以 root 为父，a 和 b。希望这有帮助

Answer 2

朋友，解决方法很简单。首先，我们为每个节点包含一个父指针和级别字段。

struct Node {
   char key;
   Node *child[N];
   Node *parent;
   int level; // An array of pointers for N children
};

现在我们将利用上面的结构。

要点是首先将两个指针放在同一层，如果这样做，它们变得相等，那么我们就完成了，如果它们不相等，我们只需将两个指针向上移动 1 层，直到他们变得平等。就是这样。

还有一点很重要，不需要把根指针传给LCA，所以你的main函数是这样的：

int main()
{
        Node *root = createDummyTree();
        cout<<LCA(root->child[2]->child[0],root->child[2]->child[1])->key<<endl;
    return 0;
}

你的LCA函数会是这样的

struct Node *LCA(struct Node *a,struct Node *b)
    {
      struct Node *larger,*smaller;
      if(a->level>b->level)
        {larger=a;smaller=b;}
      else {larger=b;smaller=a;}    
      while(larger->level!=smaller->level)
         larger=larger->parent;    
      while(larger!=smaller)
      {
          larger=larger->parent;
          smaller=smaller->parent;
      }
      return larger;//you can also return smaller here.
    }

在您的 createDummyTree 中，您唯一需要做的就是设置每个节点的父级和级别，它会像这样。

Node *createDummyTree()
{
    Node *root = newNode('A');
    root->level=0;
    root->child[0] = newNode('B');
    root->child[0]->parent=root;
    root->child[0] ->level=1;
    root->child[1] = newNode('C');
    root->child[1]->parent=root;
    root->child[1] ->level=1;
    root->child[2] = newNode('D');
    root->child[2]->parent=root;
    root->child[2] ->level=1;
    root->child[0]->child[0] = newNode('E');
    root->child[0]->child[0]->parent=root->child[0];
    root->child[0]->child[0]->level=2;
    root->child[0]->child[1] = newNode('F');
    root->child[0]->child[1]->parent=root->child[0];
    root->child[0]->child[1]->level=2;
    root->child[2]->child[0] = newNode('G');
    root->child[2]->child[0]->parent=root->child[2];
    root->child[2]->child[0]->level=2;
    root->child[2]->child[1] = newNode('H');
    root->child[2]->child[1]->parent=root->child[2];
    root->child[2]->child[1]->level=2;
    root->child[2]->child[2] = newNode('I');
    root->child[2]->child[2]->parent=root->child[2];
    root->child[2]->child[2]->level=2;
    root->child[2]->child[3] = newNode('J');
    root->child[2]->child[3]->parent=root->child[2];
    root->child[2]->child[3]->level=2;
    root->child[0]->child[1]->child[0] = newNode('K');
    root->child[0]->child[1]->child[0]->parent=root->child[0]->child[1];
    root->child[0]->child[1]->child[0]->level=3;
    return root;
}

即使在最坏的情况下，上面的代码也会给你 O(height) 的答案。

Answer 3

我找到了许多不同的方法来解决这个问题，例如：

跟踪节点结构中每个节点的父节点 (link)
在将原始节点映射到 Euler 数的同时使用 Euler tour (link) or keeping track of depth of each node (link)
但是下面的小代码在我看来是最简单的：

假设：

它假定给定的两个节点都存在于给定的 n 叉树中。要修复它，我们可以运行另一种方法来首先验证它们是否都存在于树中。

它是如何工作的：

我们需要考虑两个选项来找到给定节点的最低公共祖先
选项 1：给定的两个节点都在同一子树中，其中一个是最低公共祖先，给定算法 return temp
就是这种情况

选项2：给定的一个节点属于访问节点的一个子树，另一个属于另一个子树，在这种情况下我们需要return访问节点这是在 (if count==2 )

的条件检查下在此算法中实现的

Node LCA(Node a, Node b, Node root) {
if(a == root || b == root)
    return root;

int count = 0;
Node temp = null;

for(Node iter : root.children) {
    Node res = LCA(a, b, iter);
    if(res != null) {
        count++;
        temp = res;
    }
}

if(count == 2)
    return root;    
return temp;

}

n叉树的最低共同祖先

lowest common ancestor of n-ary tree

c++

algorithm

tree

data-structures