• Create Account

### #Actualhaegarr

Posted 29 April 2012 - 03:08 AM

1. How should the addressing of the node(s) of interest work? The "id" parameter is compared to what kind of member? From the snippets given so far it seems me that the "id" is just an index into the first level of the tree, i.e. into the list of children of the root node. So no deeper addressing is possible. Is this intention?

2. It seems me wise to differ between a routine getChildrenRecursively and countChildrenRecursively, although the latter one can actually be implemented using the result of the former one.

3. The skeleton implementation of counting may look as follows. Due to the lack of other information, the implementation makes the assumption that addressing the node of interest is done only at the level of a given node.

public class Node {

// returning the total count of children
//
public int countChildrenRecursively() {
int result = 0;
for( Node currentChild : myChildren ) {
result = result + currentChild.countChildrenRecursively() + 1;
}
return result;
}

// returning the count of children starting with the one addressed by index
//
public int countChildrenRecursively(int index) {
int result = 0;
if( index>=0 && index<myChildren.size() ) {
result = mychildren.at(index).countChildrenRecursively() + 1;
}
return result;
}

}


As you can see, the recursion terminates automatically at nodes that have no children, because the summation loop will not be entered in such cases.

4. Having a routine that returns a collection of nodes ... well, may be meaningful or may be not. Notice that such a routine does a flattening on a sub-tree. In principle it would be sufficient to return the addressed nodes itself, because all the other nodes of interest are naturally linked to it. E.g.

public class Node {

public Node getChild(int index) { ... }

}


If you actually want to flatten the sub-tree, then recursion is actually your friend. However, it means that you have a collection of nodes to return. Moreover, you obviously have to deal with a single collection for all children. The easiest way would be by providing the collection as parameter. E.g.

public class Node {

public void collectChildrenRecursively(List<Node> collector) {
if( collector == null ) {
throw new NullPointerException();
}
for( Node currentChild : myChildren ) {
currentChild.collectChildrenRecursively( collector );
}
}

}


The above solution adds the current child behind the children of the current child, and hence does a deep-first traversal.

/* all code above is untested */

### #5haegarr

Posted 28 April 2012 - 02:57 AM

1. How should the addressing of the node(s) of interest work? The "id" parameter is compared to what kind of member? From the snippets given so far it seems me that the "id" is just an index into the first level of the tree, i.e. into the list of children of the root node. So no deeper addressing is possible. Is this intention?

2. It seems me wise to differ between a routine getChildrenRecursively and countChildrenRecursively, although the latter one can actually be implemented using the result of the former one.

3. The skeleton implementation of counting may look as follows. Due to the lack of other information, the implementation makes the assumption that addressing the node of interest is done only at the level of a given node.

public class Node {

// returning the total count of children
//
public int countChildrenRecursively() {
int result = 0;
for( Node currentChild : myChildren ) {
result = result + currentChild.countChildrenRecursively() + 1;
}
return result;
}

// returning the count of children starting with the one addressed by index
//
public int countChildrenRecursively(int index) {
int result = 0;
if( index>=0 &amp;&amp; index<myChildren.size() ) {
result = mychildren.at(index).countChildrenRecursively() + 1;
}
return result;
}

}


As you can see, the recursion terminates automatically at nodes that have no children, because the summation loop will not be entered in such cases.

4. Having a routine that returns a collection of nodes ... well, may be meaningful or may be not. Notice that such a routine does a flattening on a sub-tree. In principle it would be sufficient to return the addressed nodes itself, because all the other nodes of interest are naturally linked to it. E.g.

public class Node {

public Node getChild(int index) { ... }

}


If you actually want to flatten the sub-tree, then recursion is actually your friend. However, it means that you have a collection of nodes to return. Moreover, you obviously have to deal with a single collection for all children. The easiest way would be by providing the collection as parameter. E.g.

public class Node {

public void collectChildrenRecursively(List<Node> collector) {
if( collector == null ) {
throw new NullPointerException();
}
for( Node currentChild : myChildren ) {
currentChild.collectChildrenRecursively( collector );
}
}

}


The above solution adds the current child behind the children of the current child, and hence does a deep-first traversal.

/* all code above is untested */

### #4haegarr

Posted 28 April 2012 - 02:55 AM

1. How should the addressing of the node(s) of interest work? The "id" parameter is compared to what kind of member? From the snippets given so far it seems me that the "id" is just an index into the first level of the tree, i.e. into the list of children of the root node. So no deeper addressing is possible. Is this intention?

2. It seems me wise to differ between a routine getChildrenRecursively and countChildrenRecursively, although the latter one can actually be implemented using the result of the former one.

3. The skeleton implementation of counting may look as follows. Due to the lack of other information, the implementation makes the assumption that addressing the node of interest is done only at the level of a given node.

public class Node {

// returning the total count of children
//
public int countChildrenRecursively() {
int result = 0;
for( Node currentChild : myChildren ) {
result = result + currentChild.countChildrenRecursively() + 1;
}
return result;
}

// returning the count of children starting with the one addressed by index
//
public int countChildrenRecursively(int index) {
int result = 0;
if( index>=0 &amp;&amp; index<myChildren.size() ) {
result = mychildren.at(index).countChildrenRecursively() + 1;
}
return result;
}

}


As you can see, the recursion terminates automatically at nodes that have no children, because the summation loop will not be entered in such cases.

4. Having a routine that returns a collection of nodes ... well, may be meaningful or may be not. Notice that such a routine does a flattening on a sub-tree. In principle it would be sufficient to return the addressed nodes itself, because all the other nodes of interest are naturally linked to it. E.g.
public class Node {

public Node getChild(int index) { ... }

}


If you actually want to flatten the sub-tree, then recursion is actually your friend. However, it means that you have a collection of nodes to return. Moreover, you obviously have to deal with a single collection for all children. The easiest way would be by providing the collection as parameter. E.g.

public class Node {

public void collectChildrenRecursively(List<Node> collector) {
if( collector == null ) {
throw new NullPointerException();
}
for( Node currentChild : myChildren ) {
currentChild.collectChildrenRecursively( collector );
}
}

}


The above solution adds the current child behind the children of the current child, and hence does a deep-first traversal.

### #3haegarr

Posted 28 April 2012 - 02:55 AM

1. How should the addressing of the node(s) of interest work? The "id" parameter is compared to what kind of member? From the snippets given so far it seems me that the "id" is just an index into the first level of the tree, i.e. into the list of children of the root node. So no deeper addressing is possible. Is this intention?

2. It seems me wise to differ between a routine getChildrenRecursively and countChildrenRecursively, although the latter one can actually be implemented using the result of the former one.

3. The skeleton implementation of counting may look as follows. Due to the lack of other information, the implementation makes the assumption that addressing the node of interest is done only at the level of a given node.

public class Node {

// returning the total count of children
//
public int countChildrenRecursively() {
int result = 0;
for( Node currentChild : myChildren ) {
result = result + currentChild.countChildrenRecursively() + 1;
}
return result;
}

// returning the count of children starting with the one addressed by index
//
public int countChildrenRecursively(int index) {
int result = 0;
if( index>=0 &amp;&amp; index<myChildren.size() ) {
result = mychildren.at(index).countChildrenRecursively() + 1;
}
return result;
}

}


As you can see, the recursion terminates automatically at nodes that have no children, because the summation loop will not be entered in such cases.

4. Having a routine that returns a collection of nodes ... well, may be meaningful or may be not. Notice that such a routine does a flattening on a sub-tree. In principle it would be sufficient to return the addressed nodes itself, because all the other nodes of interest are naturally linked to it. E.g.
public class Node {

public Node getChild(int index) { ... }

}


If you actually want to flatten the sub-tree, then recursion is actually your friend. However, it means that you have a collection of nodes to return. Moreover, you obviously have to deal with a single collection for all children. The easiest way would be by providing the collection as parameter. E.g.

public class Node {

public void collectChildrenRecursively(List<Node> collector) {
if( collector == null ) {
throw new NullPointerException();
}
for( Node currentChild : myChildren ) {
currentChild.collectChildrenRecursively( collector );
}
}

}


The above solution adds the current child behind the children of the current child, and hence does a deep-first traversal.

### #2haegarr

Posted 28 April 2012 - 02:55 AM

1. How should the addressing of the node(s) of interest work? The "id" parameter is compared to what kind of member? From the snippets given so far it seems me that the "id" is just an index into the first level of the tree, i.e. into the list of children of the root node. So no deeper addressing is possible. Is this intention?

2. It seems me wise to differ between a routine getChildrenRecursively and countChildrenRecursively, although the latter one can actually be implemented using the result of the former one.

3. The skeleton implementation of counting may look as follows. Due to the lack of other information, the implementation makes the assumption that addressing the node of interest is done only at the level of a given node.

public class Node {

// returning the total count of children
//
public int countChildrenRecursively() {
int result = 0;
for( Node currentChild : myChildren ) {
result = result + currentChild.countChildrenRecursively() + 1;
}
return result;
}

// returning the count of children starting with the one addressed by index
//
public int countChildrenRecursively(int index) {
int result = 0;
if( index>=0 &amp;&amp; index<myChildren.size() ) {
result = mychildren.at(index).countChildrenRecursively() + 1;
}
return result;
}

}


As you can see, the recursion terminates automatically at nodes that have no children, because the summation loop will not be entered in such cases.

4. Having a routine that returns a collection of nodes ... well, may be meaningful or may be not. Notice that such a routine does a flattening on a sub-tree. In principle it would be sufficient to return the addressed nodes itself, because all the other nodes of interest are naturally linked to it. E.g.
public class Node {

public Node getChild(int index) { ... }

}


If you actually want to flatten the sub-tree, then recursion is actually your friend. However, it means that you have a collection of nodes to return. Moreover, you obviously have to deal with a single collection for all children. The easiest way would be by providing the collection as parameter. E.g.

public class Node {

public void collectChildrenRecursively(List<Node> collector) {
if( collector == null ) {
throw new NullPointerException();
}
for( Node currentChild : myChildren ) {
currentChild.collectChildrenRecursively( collector );
}
}

}


The above solution adds the current child behind the children of the current child, and hence does a deep-first traversal.

### #1haegarr

Posted 28 April 2012 - 02:54 AM

1. How should the addressing of the node(s) of interest work? The "id" parameter is compared to what kind of member? From the snippets given so far it seems me that the "id" is just an index into the first level of the tree, i.e. into the list of children of the root node. So no deeper addressing is possible. Is this intention?

2. It seems me wise to differ between a routine getChildrenRecursively and countChildrenRecursively, although the latter one can actually be implemented using the result of the former one.

3. The skeleton implementation of counting may look as follows. Due to the lack of other information, the implementation makes the assumption that addressing the node of interest is done only at the level of a given node.

public class Node {

// returning the total count of children
//
public int countChildrenRecursively() {
int result = 0;
for( Node currentChild : myChildren ) {
result = result + currentChild.countChildrenRecursively() + 1;
}
return result;
}

// returning the count of children starting with the one addressed by index
//
public int countChildrenRecursively(int index) {
int result = 0;
if( index>=0 && index<myChildren.size() ) {
result = mychildren.at(index).countChildrenRecursively() + 1;
}
return result;
}

}

As you can see, the recursion terminates automatically at nodes that have no children, because the summation loop will not be entered in such cases.

4. Having a routine that returns a collection of nodes ... well, may be meaningful or may be not. Notice that such a routine does a flattening on a sub-tree. In principle it would be sufficient to return the addressed nodes itself, because all the other nodes of interest are naturally linked to it. E.g.
public class Node {

public Node getChild(int index) { ... }

}

If you actually want to flatten the sub-tree, then recursion is actually your friend. However, it means that you have a collection of nodes to return. Moreover, you obviously have to deal with a single collection for all children. The easiest way would be by providing the collection as parameter. E.g.

public class Node {

public void collectChildrenRecursively(List<Node> collector) {
if( collector == null ) {
throw new NullPointerException();
}
for( Node currentChild : myChildren ) {
currentChild.collectChildrenRecursively( collector );