Printing Binary Tree Nodes
I am programming a BinaryTree project. I ended up with everything (insert, delete, create, search) but one function is the print operation. I have to print it like this:
5 46 X557 XXX6XXX9
Basically print all nodes, but print X if node is empty. I have been trying to figure out how to do this and I continue to stump. Would this be a bit of a workaround? Thanks you
source to share
You can use BFS, but with a slight modification:
In plain BFS, after visiting a node, you add your children to the queue. If there are no children, nothing is added.
For your problem, if there are no children for the node that have been visited, add a special node with its value as "x" to the queue so that it will print "X" on your output accordingly. Print a new line after each level.
source to share
As Dream Lane said, BFS will be working here. I have offered my own JAVA implementation for reference.
public static void printBST(Node root) {
// empty tree
if (root == null)
return;
Queue<Node> que = new LinkedList<Node>();
que.add(root);
boolean allChildNull = false;// end condition
while (que.size() > 0 && !allChildNull) {
allChildNull = true;
Queue<Node> childQue = new LinkedList<Node>();
for (Node n : que) {
// print out noe value, X for null
if (n == null)
System.out.printf("%1$s", "X");
else
System.out.printf("%1$s", n.value);
// add next level child nodes
if (n == null) {
childQue.add(null);
childQue.add(null);
} else {
childQue.add(n.left);
childQue.add(n.right);
if (n.left != null || n.right != null)
allChildNull = false;
}
}
System.out.printf("\n");// newline
que = childQue;
}
}
source to share