从数组构建一棵（非二叉）树

Question

我需要在Java中构建一棵树。 我已经完成树作为数据结构的部分。 但是，我在将数据从数组馈送到树时遇到了一些问题。 这里是我需要做的事情。

domain = {"b", "c"};

那么，树应该是这样的:

null -> b,c
b->c  c->b

基本上，我希望一个节点的子节点拥有来自域中尚未被父节点覆盖的所有子节点。问题在于，尽管尝试了很多次，我仍然无法编写执行此操作的代码。我知道可以使用递归函数来完成它。 我不需要完整的代码。任何指向解决方案的提示都将不胜感激。谢谢。

附言: 我会明确规范。""树中的每个节点都具有来自域的所有值作为其子节点，除了已经在其本身或其父节点中被覆盖的那些值"" 如图所示，a是基础（假设为空）。它拥有来自域的所有值（b，c）。b有c，c有b。

- mihsathe

---

符号有些令人困惑。你能画一个实际的图表（你希望树是什么样子），并将其附加到你的问题上吗？在示例c->b中，据我理解，父节点已经包含了b，因此不应该有任何子节点。如果你画出了树结构的图表，它会更加清晰明了。即使你只是手工在纸上画一张图，再用手机拍照，也会更清晰。 - jefflunt

看起来你有一个图，而不是树。树没有循环。而你的树有一个循环 b -> c -> b。 - Mikita Belahlazau

不，这不是一个循环。那些是值而不是节点。我会放置图表。 - mihsathe

我已经放置了这个图表。需要注意的是，“B”两个节点具有相同的值但不属于同一图。 - mihsathe

非二进制。你有最大的孩子数量吗？ - user802421

是的，我意识到我的规格说明中有一个错误。现在它更清晰了，希望能够理解。 - mihsathe

Answer 1

规范说明：

树中的每个节点都有来自域的所有值作为子节点，除了已经在其本身或其父节点中涵盖的值

这有点不清楚，但我假设“在其本身或其父节点中涵盖”意味着如果值x不在从该节点到根的路径上，则允许具有值x的节点。在这种情况下，可以像这样构建树（语言为Haskell）：

import List

data Tree = Tree String [Tree]

build x xs = Tree x children
    where
    children = map (\x -> build x (delete x xs)) xs

例如，给定一个根值"a"和一个域值列表["b", "c", "d"]，程序递归地构造了一个具有值"a"和3个子节点的根节点，这些子节点分别由以下内容构成：

• 根值"b"和域["c", "d"],
• 根值"c"和域["b", "d"],
• 以及根值"d"和域["b", "c"]。

伪Python代码如下：

def build(root_value, domain):
    node = Tree(root_value)

    # For each value in the domain:
    for i in range(len(domain)):
        child_root = domain[i]

        # The child domain is equal to the original domain
        # with value at position 'i' removed.
        child_domain = domain[: i] + domain[i + 1:]

        # Recursively build the child
        child = build(child_root, child_domain)

        # - and add the child to the node.
        node.add_child(child)

    return node

这是一个测试build函数的示例，它打印出问题示例和上面的示例的树形结构：

pretty level (Tree x children) = do
    mapM_ putStr [indent, x, "\n"]
    mapM_ (pretty (level + 3)) children
    where
    indent = replicate level ' '

main = do
    putStrLn "Tree for a -> b, c:"
    pretty 0 (build "a" ["b", "c"])
    putStrLn "\nTree for a -> b, c, d:"
    pretty 0 (build "a" ["b", "c", "d"])

测试使用缩进来显示树中每个节点的深度：

Tree for a -> b, c:
a
   b
      c
   c
      b

Tree for a -> b, c, d:
a
   b
      c
         d
      d
         c
   c
      b
         d
      d
         b
   d
      b
         c
      c
         b

- antonakos

---

你确实理解了我的问题并且也解决了它。但是我不懂Haskell，所以我不明白这句话的意思 children = map (\x -> build x (delete x xs)) xs。你能解释一下吗？ - mihsathe

Answer 2

您需要更清晰/准确地指定构建树的规则：

• 根据您的原始规范，左下角的“C”节点应该有一个“A”子节点。（我看到您已经纠正了这个问题。）

• 您的规范没有说明如何决定放置在根节点中的内容。（为什么您的图表中是“A”？）

我有一种感觉，正确指定规则将帮助您看到为什么以前尝试的解决方案没有奏效。如果不行，这至少可以帮助我们找出问题所在。

如果您对规则感到困惑，也许您可以解释一下这个“树”在语义上应该代表什么。（我怀疑它可能意味着输入字符串的排列组合表示法。）

- Stephen C

---

我意识到了这个问题。我已经从域中删除了大写字母“A”。将a视为一个空节点。 - mihsathe

树中的每个节点都具有来自该域的除其或其父项已涵盖的值之外的所有子值。 “c”不会被“b”的父级或其中涵盖，因此这是一个正确的选择。 - mihsathe