7

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

如何实现非二叉树

并跟进问题，当您有一个 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;
}
4

1 回答 1

4

邻接矩阵听起来是个坏主意，它会非常稀疏（大多数单元格都是空的）。通常对于n-ary trees（是的，这就是它们的名称），您只需遵循与二叉树相同的策略，不同之处在于二叉树将有 2 个字段表示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 leftand的部分，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;

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

于 2015-08-03T04:06:18.327 回答