如何表示非二叉树以及如何对该树进行 LCA？

Question

非二叉树通常如何表示？一个节点可以拥有的子节点数量没有限制的树。最好是使用邻接矩阵或邻接列表并假设没有循环，或者做类似这个问题的事情 ->

How to implement a Non-Binary tree

然后跟进问题，当你有一个 n 元树时（这是它们的正确名称吗？）找到树中两个给定 nodes/data 值的最小公共祖先的好方法是什么？我能找到的都是处理二叉树的算法，比如这个 ->

static Node lca(Node root,int v1,int v2)
{
  if (root == null || root.data == v1 || root.data == v2) {
    return root;
  }

  Node left = lca(root.left, v1, v2);
  Node right = lca(root.right, v1, v2);

  if (left != null && right != null) {
    return root;
  }

  return (left != null) ? left : right;
}

Answer 1

邻接矩阵听起来不是个好主意，它会非常稀疏（大多数单元格都是空的）。通常对于 n-ary trees（是的，这就是它们的名称），您只需遵循与二叉树相同的策略，不同之处在于二叉树将有 2 个字段代表 left 和 right children:

class Node<T> {
   T value;
   Node<T> left;
   Node<T> right;
}

在这里，您将这些字段更改为类似数组的数据结构（静态或动态）：

class Node<T> {
   T value;
   List<Node<T>> children;
}

至于LCA，你打算在节点中存储parent指针吗？这些值应该是一棵具有唯一值的树吗？这些值会以任何方式排序吗？

如果不是，但您可以假设节点在树中（尽管处理其他情况并不难），那么 LCA 与上面显示的非常相似。您只需要更改获得 Node left 和 Node right 的部分，以便它遍历所有 children:

int count = 0;
Node<T> temp = null;
for(Node<T> child : root.children) {
    Node<T> result = lca(child, v1, v2);
    if(result != null) {
        count++;
        temp = result;
    }
}

if(count == 2) {
    return root;
}

return temp;

使用 parent 指针 and/or 在每个节点中存储部门，我们可以做得更好，但需要存储成本。

如何表示非二叉树以及如何对该树进行 LCA？

How to represent a non binary tree and how to do LCA on that tree?

algorithm

tree

least-common-ancestor