001package algs32;
002import java.util.Scanner;
003import algs13.Queue;
004import stdlib.*;
005
006public class XTree {
007        private Node root;
008        private XTree (Node root) { this.root = root; }
009        private static class Node {
010                public final int val;
011                public final Queue<Node> children; // children must not be null
012                public Node (int val) {
013                        this.val = val;
014                        this.children = new Queue<>();
015                }
016        }
017
018        // tree input has the form "num ( ... )"
019        // where num is an integer and ... is another tree input
020        // example: "0 ( 1 ( 11 12 13 ) 2 ( 21 22 ( 221 222 223 ) ) 3 ( ) 4 )"
021        // empty parens "( )" are optional.
022        public static XTree parse (String in) {
023                Scanner sc = new Scanner (in);
024                Node root = parseHelper (sc);
025                return new XTree (root);
026        }
027        private static Node parseHelper (Scanner sc) {
028                int val = sc.nextInt ();
029                Node result = new Node (val);
030                if (sc.hasNext ("\\(")) {
031                        sc.next (); // gobble "("
032                        while (sc.hasNextInt ()) {
033                                Node child = parseHelper (sc);
034                                result.children.enqueue (child);
035                        }
036                        sc.next ("\\)"); //gobble ")"
037                }
038                return result;
039        }
040
041        // prefix with parenthesis
042        public String toString() {
043                StringBuilder sb = new StringBuilder();
044                if (root != null) toString (sb, root);
045                return sb.toString ();
046        }
047        private static void toString (StringBuilder sb, Node n) {
048                sb.append (n.val);
049                sb.append (" ");
050                if (!n.children.isEmpty ()) {
051                        sb.append ("( ");
052                        for (Node child : n.children)
053                                toString (sb, child);
054                        sb.append (") ");
055                }
056        }
057
058        public void toGraphviz(String filename) {
059                GraphvizBuilder gb = new GraphvizBuilder ();
060                if (root != null) toGraphviz (gb, null, root);
061                gb.toFileUndirected (filename, "ordering=\"out\"");
062        }
063        private static void toGraphviz (GraphvizBuilder gb, Node parent, Node n) {
064                gb.addLabeledNode (n, Integer.toString (n.val));
065                if (parent != null) gb.addEdge (parent, n);
066                for (Node child : n.children)
067                        toGraphviz (gb, n, child);
068        }
069
070        // prefix order traversal
071        public void printPre () {
072                if (root != null) printPre (root);
073                StdOut.println ();
074        }
075        private static void printPre (Node n) {
076                StdOut.print (n.val + " ");
077                for (Node child : n.children) {
078                        printPre (child);
079                }
080        }
081
082        // level order traversal
083        public void printLevel () {
084                Queue<Node> queue = new Queue<>();
085                if (root != null) queue.enqueue(root);
086                while (!queue.isEmpty()) {
087                        Node n = queue.dequeue();
088                        StdOut.print (n.val + " ");
089                        for (Node child : n.children) {
090                                queue.enqueue(child);
091                        }
092                }
093                StdOut.println ();
094        }
095
096        public static void main(String[] args) {
097                XTree xtree = XTree.parse ("0 ( 1 ( 11 12 ( 121 ( 1211 1212 ) 122 123 124 125 ) 13 ) 2 ( 21 22 ( 221 222 223 ) ) 3 )");
098                StdOut.println (xtree);
099                xtree.printPre ();
100                xtree.printLevel ();
101                xtree.toGraphviz ("xtree.png");
102        }
103}