Scan tree structure from bottom to top?

Question

If the following tree structure or one of them is specified:

I would like to return the string ZYXWVUT. I know how to do this with a binary tree, but not with one that can have more children. Any help would be greatly appreciated.

Answer 1

This is called a tree traversal after-order : you print the contents of all subtrees of the tree before printing the contents of the node.

This can be done recursively, like this (pseudocode):

function post_order(Tree node) foreach n in node.children post_order(n) print(node.text) 

Answer 2

If you support an ArrayList (e.g. node_list) to track the number of branch branches from the current node tree, you can traverse the tree from the root until you find a node that has an empty node_list. This way you can identify the leaf nodes of the tree. A recursive approach will work for this case. I have not tested the code, but I believe that this should work for what you requested:

If you are building something similar to the class below to build your tree:

 class Node { String data; ArrayList<Node> node_list;} 

The following recursive function might be what you are looking for:

 public void traverse_tree(Node n){ if(n.node_list.isEmpty()){ System.out.print(n.data); } else{ for(Node current_node:n.node_list){ traverse_tree(current_node); } System.out.println(n.data); } } 

In fact, you look at the depth after ordering. The first tree walk.

Answer 3

something like this should do it

 public void traverse(){ for(Child child : this.children){ child.traverse(); } System.out.print(this.value); }