java - 从数组构造(非二叉)树

Question

我需要用 Java 构建一棵树。我已经完成了树作为数据结构的工作。但是我在将数据从数组提供给树时遇到了一些问题。这是我需要做的。

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

那么，树应该是这样的:

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

所以基本上我希望一个节点的子节点拥有域中尚未包含在父节点中的所有子节点。问题是尽管进行了很多尝试，我还是无法编写代码来完成它。我知道这可以用递归函数来完成。我不想要完整的代码。对解决方案的任何提示将不胜感激。谢谢。

附言

我会清除规范。 ""树中的每个节点都具有域中的所有子值，除了已经包含在它或其父节点中的值""

如图，a为基数(假设为null)。它具有来自域 (b,c) 的所有值。 b 有 c，c 有 b。

Answer 1

规范说:

Every node in the tree has all the values as children from the domain apart from the ones that are already covered in it or its parents

有点不清楚，但我假设包含在它或其父节点中意味着如果值为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 中，这是 Haskell 程序的算法:

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