如何表示非二叉树以及如何在树上进行LCA

Question

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

如何实现非二叉树

和后续问题，当你有一个n元树时(这是它们的正确名称吗?)找到树中两个给定节点/数据值的最小共同祖先的好方法是什么?我能找到的都是处理二叉树的算法，比如这个->

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(是的，这就是它们的名称)，您只需遵循与二叉树相同的策略，不同之处在于二叉树将有两个字段表示left和right子节点:

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;

使用父指针和/或在每个节点中存储深度，我们可以做得更好，但要付出存储成本。