CODEWITHSUNDEEP
javadata-structurestree
mihsathe
mihsathe

Reputation: 9154

Constructing a (non binary) tree from an array

I need to construct a tree in Java. I am already done with tree as a data structure. But I am having some problem feeding data from an array to the tree. Here is what I need to do.

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

then, the tree should be like:

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

So basically I want a node's child to have all children from the domain that are not already covered in the parent. The problem is that in spite of a lot of tries, I am not able to write code for doing it. I know it can be done with a reccursive function. I do not want full code. Any hint towards the solution will be highly appreciated. Thank you.

enter image description here

P.S.

I'd clear the specification. ""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""

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

Upvotes: 4

Views: 1890

Answers (2)

antonakos
antonakos

Reputation: 8361

The specification says:

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

It is a little unclear, but I am assuming that covered in it or its parents means that a node with value x is allowed if the value x is not on the path from the node to the root. In that case the tree can be constructed like this (the language is Haskell):

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, given a root value "a" and a list of domain values ["b", "c", "d"], the program constructs a root node with value "a" and 3 children recursively constructed from:

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

In pseudo-Python this is the algorithm of the Haskell program:

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 the tree of the example of the question and the 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

Upvotes: 1

Stephen C
Stephen C

Reputation: 718826

You need to specify the rules for building the tree more clearly / accurately:

  • According to your original specification, the "C" node at the bottom left should have an "A" child node. (You've corrected that ... I see.)

  • Your specification doesn't say how you decide what to put in the root node. (How come it is "A" in your diagram?)

I have a feeling that specifying the rules correctly will help you see why your previous attempted solutions haven't worked. If not, this will at least help us to figure it out.

If you are struggling with the rules, perhaps you could explain what this "tree" is supposed to represent ... in a semantic sense. (I suspect that it might be meant to be a representation of the permutations of the input strings.)

Upvotes: 0

Related Questions