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

+3


source to share


3 answers


Use level traversal (first breadth first search), printing each node as you go through the level, with a new line at the end of each level.



You can find BFS pseudocode here

+3


source


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.

0


source


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;
    }
}

      

0


source







All Articles