CODEWITHSUNDEEP
javaalgorithmdata-structurestree
Ranjeet SIngh
Ranjeet SIngh

Reputation: 673

Tree structure where children have different parent

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.

Upvotes: 0

Views: 313

Answers (3)

m4ktub
m4ktub

Reputation: 3121

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.

Upvotes: 0

Vaibhav Jhunjhunwala
Vaibhav Jhunjhunwala

Reputation: 31

You can create a tree structure as follows 

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

class MyTree
{
    Node root;
}

Upvotes: 1

Nishant Kumar
Nishant Kumar

Reputation: 2169

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

1
3 2
5 6 4
7 9 8 10

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.

Upvotes: 1

Related Questions