В спецификации сказано:
Каждый узел в дереве имеет все значения как дочерние элементы домена, за исключением тех, которые уже включены в него или его родителей
Немного неясно, но я предполагаю, что , охватываемый в нем или его родителях , означает, что узел со значением 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