java – 从数组构造(非二进制)树

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”,
>根值“c”和域[“b”,
>和根值“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

这是对构建函数的测试,它打印问题示例的树和上面的示例：

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,d:
a
   b
      c
         d
      d
         c
   c
      b
         d
      d
         b
   d
      b
         c
      c
         b