java - Print binary search tree using text -

i want print binary search tree in format:

     4      / \    /   \   2     5   / \   / \ 1   3 4   6 

i think have depth of tree and, then, each level, print number of spaces before , after each element.

public void printtree(bstnode t, int depth) {     (int = 1; <= depth; i++){         //then what?     } 

i not know how proceed.

the node class:

public class bstnode {     private int value;     private bstnode left;     private bstnode right;      public bstnode(){         value = 0;         left = null;         right = null;     }      public bstnode(int x){         value = x;         left = null;         right = null;     }      void setvalue(int x){         value = x;     }      int getvalue(){         return value;     }      void setleft(bstnode l){         left = l;     }      bstnode getleft(){         return left;     }      void setright(bstnode r){         right = r;     }      bstnode getright(){         return right;     } } 

one thing's sure: not easy problem. here's approach.

first things first, let's recursion straight. i'd able print left subtree of node, print right subtree, somehow combine 2 final result. this, i'm going need data class intermediate values:

public class treestring {     private list<string> lines;     private int columncount;     private int rootcolumn;      public treestring(list<string> lines, int columncount, int rootcolumn) {         this.lines = new arraylist<>(lines);         this.columncount = columncount;         this.rootcolumn = rootcolumn;     }      /** @return number of lines */     public int getlinecount() {         return lines.size();     }      /** @return number of columns */     public int getcolumncount() {         return columncount;     }      /** @return index of column containing center of root */     public int getrootcolumn() {         return rootcolumn;     }      /** @return number of columns right of column containing center of root */     public int getrootcolumnfromright() {         return getcolumncount() - (getrootcolumn() + 1);     }      /** @return line @ {@code index} */     public string getline(int index) {         return lines.get(index);     } } 

so, instance, tree

    4    / \   2   5  / \ 1   3 

would represented treestring:

lines = new arraylist<>(arrays.aslist("    4  ", "   / \\ ", "  2   5", " / \\   ", "1   3  ")); columncount = 7; rootcolumn = 4; 

notice lines have same length. important later on.

ok, how implement printtree? well, it's simple: kill batman write boilerplate.

public void printtree(bstnode node, int depth) {     if (depth > 0) {         treestring treestring = treestringfrombstnode(node, depth);         (int = 0; < treestring.getlinecount(); ++i) {             system.out.println(treestring.getline(i));         }     } }  public treestring treestringfromstring(string string) {     return new treestring(collections.singletonlist(string), string.length(), string.length() / 2); }  public treestring treestringfrombstnode(bstnode node, int depth) {     treestring value = treestringfromstring(string.valueof(node.getvalue()));     treestring left = depth <= 1 || node.getleft() == null ? null : treestringfrombstnode(node.getleft(), depth - 1);     treestring right = depth <= 1 || node.getright() == null ? null : treestringfrombstnode(node.getright(), depth - 1);     return combinetreestrings(value, left, right); } 

now, on main event:

public string spaces(int numspaces) {     string string = "";     (int = 0; < numspaces; ++i) {         string += " ";     }     return string; }  public treestring combinetreestrings(treestring parent, treestring left, treestring right) {     if (left == null && right == null) {         return parent;     }      // number of lines between bottom of parent , tops of left , right     // number of columns between parent's root column , root columns of left or right     int verticalgap = 1;     // number of columns between left end of right , right end of left     int middlegap =  0;     if (left != null && right != null) {         verticalgap = math.max(verticalgap, (left.getrootcolumnfromright() + 1 + right.getrootcolumn()) / 2);         middlegap = (verticalgap - left.getrootcolumnfromright()) + 1 + (verticalgap - right.getrootcolumn());     }      // number of columns between left end of left (or right, if left null) , left end of result     int lowerleftgap;     // number of columns between left end of parent , left end of result     int upperleftgap;     if (left != null) {         lowerleftgap = math.max(0, parent.getrootcolumn() - verticalgap - 1 - left.getrootcolumn());         upperleftgap = math.max(0, left.getrootcolumn() + 1 + verticalgap - parent.getrootcolumn());     } else {         lowerleftgap = math.max(0, parent.getrootcolumn() + 1 + verticalgap - right.getrootcolumn());         upperleftgap = math.max(0, right.getrootcolumn() - verticalgap - 1 - parent.getrootcolumn());     }      // number of columns between right end of result , right end of right (or left, if right null)     int lowerrightgap;     // number of columns between right end of result , right end of parent     int upperrightgap;     if (right != null) {         lowerrightgap = math.max(0, -right.getrootcolumnfromright() - 1 - verticalgap + parent.getrootcolumnfromright());         upperrightgap = math.max(0, -parent.getrootcolumnfromright() + verticalgap + 1 + right.getrootcolumnfromright());     } else {         lowerrightgap = math.max(0, -left.getrootcolumnfromright() + verticalgap + 1 + parent.getrootcolumnfromright());         upperrightgap = math.max(0, -parent.getrootcolumnfromright() - 1 - verticalgap + left.getrootcolumnfromright());     }      list<string> lines = new arraylist<>();     // parent lines     (int = 0; < parent.getlinecount(); ++i) {         lines.add(spaces(upperleftgap) + parent.getline(i) + spaces(upperrightgap));     }     // slash , backslash lines     (int = 0; < verticalgap; ++i) {         string leftleg;         if (left != null) {             leftleg = "/";         } else if (upperleftgap > 0) {             leftleg = " ";         } else {             leftleg = "";         }          string rightleg;         if (right != null) {             rightleg = "\\";         } else if (upperrightgap > 0) {             rightleg = " ";         } else {             rightleg = "";         }          int numleftspaces = upperleftgap + parent.getrootcolumn() - leftleg.length() - i;         int numrightspaces = upperrightgap + parent.getrootcolumnfromright() - rightleg.length() - i;         lines.add(spaces(numleftspaces) + leftleg + spaces(i + 1 + i) + rightleg + spaces(numrightspaces));     }     // left , right lines     (int = 0; < math.max(left == null ? 0 : left.getlinecount(), right == null ? 0 : right.getlinecount()); ++i) {         string leftline;         if (left == null) {             leftline = "";         } else if (i >= left.getlinecount()) {             leftline = spaces(left.getcolumncount());         } else {             leftline = left.getline(i);         }          string rightline;         if (right == null) {             rightline = "";         } else if (i >= right.getlinecount()) {             rightline = spaces(right.getcolumncount());         } else {             rightline = right.getline(i);         }          lines.add(spaces(lowerleftgap) + leftline + spaces(middlegap) + rightline + spaces(lowerrightgap));     }     return new treestring(lines, upperleftgap + parent.getcolumncount() + upperrightgap, upperleftgap + parent.getrootcolumn()); } 

hopefully solves problem! if there's way can cleaned up, don't hesitate comment.