Geek asks and answers

Total Java Total Traffic

I have a problem to solve in Java. I have a tree to go through. There he is:

        1
     /     \
   1 2 3  1 2 3      
 /   |  \    \
123 123 123  same for those three nodes

Now the way that you need to go through begins with the root and goes through the deepest left node (here 1) and its leftmost leaf (1). After that, he should start again with a root tracing all the numbers, and this time we get to the next sheet of the same deep left node .. etc., which starts from the top, every time, when all the other sheets of this one after another node. After all the leaves of the leftmost node have been traced, how it should happen, as usual (starting from the top), and now go to the next uninvited node (here 2) .. etc. For the whole tree. So, the first 6 tracks will be:

111 112 113 121 122 123 ... etc.

All numbered numbers must be tracked and recorded in order, as described above. Anyone can help with an algorithm on how to achieve it? Thank.

+3
source share
2 answers

You need a tree traversal algorithm.

void traverse(Node root, String path) {
    path += root.getValue();
    for (Node child : root.getChildren())
        traverse(child, path);

    // end of current traversal
    if (root.getChildren().isEmpty())
        System.out.print(path + " ");
}
+4
source

What you describe is called the depth of the first search . You should know that this is not the most effective algorthim for work, there are better ones like Dijkstra's .

Depending on what you are trying to do, there is an even more specialized tactic that you can use, such as Alpha Beta Trimming or other heuristics to search for games.

Depth First Search node, - , node. , node node...

List<Node> path = new ArrayList<Node>();
path.add(node);
while(node.parent != null){
  path.add(node.parent);
  node = node.parent;
}
return path; //returns a path from {goal,...,root}
+1

More articles:


All Articles