CODEWITHSUNDEEP
java
Armin
Armin

Reputation: 89

String Array (Tree)

Suppose we have 5 String arrays:

String[] array1 = {"hello", "i", "cat"};
String[] array2 = {"hello", "i", "am"};
String[] array3 = {"hello", "James"};'
String[] array4 = {"hello", "i", "bob"};
String[] array5 = {"hello", "mike", "wasup"};

How would I create a tree where "hello" is always the root, and the second element is the child of the root and and the other elements become the children of the sub root. (each node could have 0-n node children)

An an example:

           hello
        /   \    \
      i    james   mike
    / \ \           /
  cat  am bob    wasup

The diagram above is a type of tree I want. Please don't write any code. I want to understand the concept. Explain your approach as a programmer.

Upvotes: 1

Views: 211

Answers (3)

Joop Eggen
Joop Eggen

Reputation: 109567

It is a tree of which words may immediately follow a given word.

As such there should be an artifical root, as there could have been sentences with an other word than "hello."

Have all those sentences (array1, ...) themselves put in an array (or collection or database). So one can walk over them; can think of them as iterable.

Have a partial tree, initially empty, only containing the ROOT.

Then loop till all words are in the tree, looking for new words to add to allready present words. For every sentence put the first word under the root (ROOT is already present). For every other word, if the previous word is in the tree, put that word under the previous tree.

As you see, a naive approach (following the above) would on stable fixed data would need to skip much. One can of course have a mapping of word to its a tree node holding all its successors, and then the algorithm becomes quite simple.

Upvotes: 1

tsolakp
tsolakp

Reputation: 5948

Define a Node class that is Composite. Create Map where the key is your Strings in those arrays and value is the Node. Iterate over the array check if there is an already created Node for that value, if not create one. Then check the previous value and add your Node to that values associated Node.

Upvotes: 1

Juli3n
Juli3n

Reputation: 221

I would use a tree structure then I would iterate on each array filling the tree. Root = hello

Then for each wore of the array, check the leaves for this word

  • if it does not contain your word, then create a new leaf with key = current word

Then I go down in the tree and move forward in the array

Do this till the end of your array

Java tree data-structure?

Upvotes: 1

Related Questions