Building a tree (not binary) from an array

Question

I need to build a tree in Java. I have already processed the tree as a data structure. But I am having problems feeding data from an array to a tree. Here is what I need to do.

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

then the tree should look like this:

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

So basically, I want the node child to have all the children from the domain that have not yet been covered by the parent. The problem is that, despite many attempts, I can not write code for this. I know that this can be done with a recursive function. I do not need the full code. Any hints of a solution would be much appreciated. Thanks.

PS

I would clarify the specification. "Each node in the tree has all the values ​​in the form of children from the domain, except those that are already covered by it or its parents."

as in the figure, a is the base (say null). It has all the values ​​from the region (b, c). b has c and c has b.

Answer 1

The specification states:

Each node in the tree has all the values ​​as children of the domain, except for those that have already been covered in it or its parents.

A bit unclear, but I assume that covered by him or his parents means that a node with a value of x allowed if the value of x not in the path from node to root. In this case, the tree can be constructed in this way (Haskell language):

 import List data Tree = Tree String [Tree] build x xs = Tree x children where children = map (\x -> build x (delete x xs)) xs 

For example, taking into account the root value "a" and the list of domain values ["b", "c", "d"] , the program creates the root directory node with the value "a" and 3 children recursively constructed from:

• root value "b" and domain ["c", "d"] ,
• root value "c" and domain ["b", "d"] ,
• and the root value of "d" and the domain ["b", "c"] .

In pseudo python, this is the Haskell program algorithm:

 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 

Here is a test of the build function that prints a tree of sample question and example above:

 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"]) 

The test uses indentation to show the depth of each node in the tree:

 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 

Answer 2

You need to specify the rules for constructing the tree more clearly / precisely:

• According to your original specification, the “C” node in the lower left should have a child element “A” node. (You fixed it ... I see.)

• Your specification does not say how you decide what to put in the root directory of a node. (How did “A” appear in your diagram?)

I have the feeling that the correct definition of the rules will help you understand why your previous solution attempts did not work. If not, it will at least help us understand this.

If you are struggling with the rules, perhaps you could explain what this “tree" should represent ... in a semantic sense. (I suspect that this could mean introducing permutations of input strings.)