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

Question

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

How to implement a Non-Binary tree

并跟进问题，当您有一个 n 元树时(这是它们的正确名称吗？)为该树中的两个给定节点/数据值找到最小公共(public)祖先的好方法是什么？我所能找到的都是处理二叉树的算法，比如这个 ->

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 和正确的 child :

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 的部分，以便它遍历所有子节点:

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;

使用父指针和/或在每个节点中存储部门，我们可以做得更好，但会增加存储成本。