CSC403: Trees: Printing

(Click here for one slide per page)

    public void printPre () {
        printPre (root, 0);
    }
    private static void printPre (Node x, int d) {
        if (x == null) return;
        indent (d);
        StdOut.println (x.key);
        printPre (x.left, d+1);
        printPre (x.right, d+1);
    }
    private static void indent (int d) {
        for (int i=0; i<d; i++)
            StdOut.print ("  ");
    }

This is Pretty Printing where we use indentation to show depth.

    public void printPre () {
        printPre (root);
        StdOut.println ();
    }
    private static void printPre (Node x) {
        if (x == null) return;
        StdOut.print (x.key + " ");
        printPre (x.left);
        printPre (x.right);
    }

Print prefix (simple version).

What about infix? postfix?

    public void printIn () {
        printIn (root);
        StdOut.println ();
    }
    private static void printIn (Node x) {
        if (x == null) return;
        printIn (x.left);
        StdOut.print (x.key + " ");
        printIn (x.right);
    }

Yeah!

    public void printPost () {
        printPost (root);
        StdOut.println ();
    }
    private static void printPost (Node x) {
        if (x == null) return;
        printPost (x.left);
        printPost (x.right);
        StdOut.print (x.key + " ");
    }

Yeah!

What about using a loop?

    public void printPre () {
        Stack<Node> s = new Stack<> ();
        s.push (root);
        while (!s.isEmpty ()) {
            Node x = s.pop ();
            if (x == null) continue;
            StdOut.print (x.key + " ");
            s.push (x.right);
            s.push (x.left);
        }
        StdOut.println ();
    }

Print prefix with a loop

Not so bad.

    public void printPost () {
        Stack<int>  r = new Stack<> ();  // keys to print out
        Stack<Node> s = new Stack<> ();  // nodes for the traversal
        s.push (root);
        while (!s.isEmpty ()) {
            Node x = s.pop ();
            if (x == null) continue;
            r.push (x.key);
            s.push (x.left);
            s.push (x.right);
        }
        while (!r.isEmpty ())
            StdOut.print (r.pop () + " ");
        StdOut.println ();
    }

Print postfix with a loop

Hmmm.

    public void printIn () {
        Stack<Node> s = new Stack<> ();
        Node x = root;
        while (x != null || !s.isEmpty ()) {
            if (x != null) {
                s.push (x);
                x = x.left;
            } else {
                x = s.pop ();
                StdOut.print (x.key + " ");
                x = x.right;
            }
        }
        StdOut.println ();
    }

Print infix with a loop (from here)

Yeesh.

    public void printPost () {
        Stack<Node> s = new Stack<>();
        s.push (root);

        Node prev = root;
        while (!s.isEmpty ()) {
            Node x = s.pop ();
            if (x == null) continue;
            if (x.right == prev || x.left == prev || (x.left == null && x.right == null)) {
                StdOut.print (x.key + " ");
                prev = x;
            } else {
                s.push (x);
                s.push (x.right);
                s.push (x.left);
            }
        }
        StdOut.println ();
    }

Print postfix with only one loop (from here and here)

Horror.

    public void printPre () {
        Stack<Node> s = new Stack<> ();
        s.push (root);
        while (!s.isEmpty ()) {
            Node x = s.pop ();
            if (x == null) continue;
            StdOut.print (x.key + " ");
            s.push (x.right);
            s.push (x.left);
        }
        StdOut.println ();
    }

Print level-order in a loop: not bad

    public void printLevel () {
        Queue<Node> q = new Queue<> ();
        q.enqueue (root);
        while (!q.isEmpty ()) {
            Node x = q.dequeue ();
            if (x == null) continue;
            StdOut.print (x.key + " ");
            q.enqueue (x.left);
            q.enqueue (x.right);
        }
        StdOut.println ();
    }

Print level-order in a loop: not bad

Postfix and infix are bad.