Databases
StackOverflow2013
Postsdbo
POTraversing a level-oriented structure
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POTraversing a level-oriented structure
    primarykey
    data
    text
    <p>I have a linear data structure where every node has a level. The parent node has a level of 1, a node that is child of the parent has a level 2, a node that is child of child has node of 3, another parent node would have a level of 1. e.g. below</p> <pre><code>&lt;node level=1&gt; //parent node &lt;node level=2&gt; //child of encountered parent node &lt;node level=2&gt; //child of encountered parent node &lt;node level=3&gt; //child of encountered child node &lt;node level=2&gt; //child of encountered parent node &lt;node level=1&gt; //parent node &lt;node level=1&gt; //parent node &lt;node level=2&gt; //child of encountered parent node &lt;node level=3&gt; //child of encountered child node &lt;node level=4&gt; //child of encountered child node &lt;node level=1&gt; //parent node </code></pre> <p>Essentially I am trying to build a List .. (open to other suggestions), such that each element in the list is a parent node, each parent node will have list of child nodes, each child node can have list of child nodes etc. Each of the element is a node and all properties are same.</p> <p>I have tried code by keeping track of the current level but than I am not sure how to properly add a child node, that has child node, that has child node, back to the parent node of the first child node. I feel this might be handled best by recursion but I am have never been able to truly implement recursion in a orderly fashion.</p> <h1>My Solution</h1> <p>Here is my <strong>working implementation</strong> of this traversal. Please feel free to comment on how to optimize this:</p> <pre><code>Node currNode = root; List&lt;Root&gt; roots = new ArrayList&lt;Root&gt;(); do { Node node = generateNode(nodesList.next()); if (node.getLevel() == 1) { //implies root level node roots.add(node); currNode = node; index++; continue; } if (node.getLevel() == currNode.getLevel() +1) { currNode.childrenList.addChild(node); node.setParent(currNode); currNode = node; } else { while (node.getLevel() &lt;= currNode.getLevel()) { if (currNode.getParent() == null) { currNode = roots.get(roots.size()-1); } else { currNode = currNode.getParent(); } if (node.getLevel() == currNode.getLevel() + 1) { currNode.childrenList.addChild(node); node.setParent(currNode); currNode = node; } else { currNode = roots.get(roots.size()-1); currNode.childrenList.addChild(node); } } while (hasMoreNodes(nodesList)); </code></pre> <p>I wrote the following logic to print this structure, let me know if this can be improved:</p> <pre><code>private void printNodes(List&lt;Node&gt; node) { for (int j = 0; j &lt; node.size(); j++) { printContents(node.get(j)); printChildren(node.get(j)); } } private void printChildren(Node node) { for (int i = 0; i &lt; node.getChildrenList().size(); i++) { printContents(node.getChildrenList().get(i)); printChildren(node.getChildrenList().get(i)); } } </code></pre>
    singulars
    1. PO
      singulars
      1. PTAnswer
    1. This table or related slice is empty.
    1. PTQuestion
    1. This table or related slice is empty.
    1. USJohn Brown
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. PO
      singulars
      1. PTAnswer
    1. VO
      singulars
      1. POTraversing a level-oriented structure
      1. USJohn Brown
      1. VTFavorite
    1. COTry to reduce that to an usual binary tree and use some known algorithms.
      singulars
      1. POTraversing a level-oriented structure
      1. USuser1929959
    2. COMy understanding is that in a binary tree each node has 2 children; in my case that is not necessarily true since one node could have more than 2 child nodes.
      singulars
      1. POTraversing a level-oriented structure
      1. USJohn Brown
    3. COBinary trees are well understood and well explained in available literature. The principles used with them would help you solve your puzzle once you learn them.
      singulars
      1. POTraversing a level-oriented structure
      1. USLee Meador
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload