Tree structure where children have different parent

Question

I need a data structure that stores integers in such a way that each number is connected to the two (or more) adjacent ones immediately below itself, like

      1
     / \
    3   2
   / \ / \
  5   6   4
 / \ / \ / \
7   9   8  10

I am trying to implement this in java. I am new to data structure and i am able to implemnet tree structure but finding it difficult to implement this in java.

What have you tried so far? Where are you stuck? Please read http://stackoverflow.com/help/how-to-ask — reto, Oct 30 '15 at 07:28
The Java Collections class doesn't have a default `Tree` implementation, but you can easily create your own as was done in [this SO post](http://stackoverflow.com/questions/3522454/java-tree-data-structure). — Tim Biegeleisen, Oct 30 '15 at 07:31
that's not a tree. well, unless the edges are directed from top to bottom. and even in that case it is not a tree : ) — mangusta, Oct 30 '15 at 07:57

score 1 · Answer 1 · answered Oct 30 '15 at 08:50

1

you can store it in the form of variable length 2-D matrix.

for index (i,j) it's left child would be index (i+1,j) and right child index will be (i+1,j+1) provided i+1 and j+1 are within the range in case of 2 child. You can extend this for more child as well.

answered Oct 30 '15 at 08:50

Nishant Kumar

2,199
2
22
43

can you elaborate this little bit more with some more example – Ranjeet SIngh Oct 30 '15 at 09:38
@RanjeetSIngh can u give your expected structure for 3 child case? – Nishant Kumar Oct 30 '15 at 11:30

score 1 · Answer 2 · answered Oct 30 '15 at 10:32

1

You can create a tree structure as follows

class Node
{
    Node mNodeLeftParent;
    Node mNodeRightParent;
    Node mNodeLeftChild;
    Node mNodeRightChild;
    int miValue;
}

class MyTree
{
    Node root;
}

answered Oct 30 '15 at 10:32

Vaibhav Jhunjhunwala

31
2

I am also trying this way only my creating a node but while traversing through root and creating the child nodes but i am facing difficulty while putting tht common child to two different parent refernce. – Ranjeet SIngh Oct 30 '15 at 12:14
put your add function in your question. – Vaibhav Jhunjhunwala Oct 30 '15 at 12:17

score 0 · Answer 3 · answered Oct 30 '15 at 11:51

As data structures go, your situation is not a tree but a graph (more general). The JDK does not have a Graph data type (nor a Tree, for that matter) so you have to look to something like JGraphT.

DirectedGraph<Integer, DefaultEdge> g = 
    SimpleDirectedGraph.<Integer, DefaultEdge> builder(DefaultEdge.class)
        .addEdgeChain(1, 3, 5, 7)
        .addEdgeChain(1, 3, 5, 9)
        .addEdgeChain(1, 3, 6, 9)
        .addEdgeChain(1, 3, 6, 8)
        .addEdgeChain(1, 2, 6, 9)
        .addEdgeChain(1, 2, 6, 8)
        .addEdgeChain(1, 2, 4, 8)
        .build();

// the edge chains are just to be exhaustive in all the paths
// but only one edge is added, for each pair, like the following
g.addVertex(10);
g.addEdge(8, 10);

Stream<Integer> parents = g.incomingEdgesOf(6).stream().map(g::getEdgeSource);
Stream<Integer> children = g.outgoingEdgesOf(6).stream().map(g::getEdgeTarget);

System.out.println(" parents of 6 = " + parents.collect(Collectors.toList()));
System.out.println("children of 6 = " + children.collect(Collectors.toList()));

You can also used undirected graphs but then you would need to get all edges connecting 6 and check if 6 is the source or the target to get what you want.

There might be an overhead, for your scenario, because JGraphT is very generic. Still it's very convenient and, after the first tries with the API, simple to use.

Tree structure where children have different parent

3 Answers3