class BSTPrint
1: //BSTPrint.java
3: class BSTPrint
4: {
5: public static String treeToString(Node subtreeRoot)
6: {
7: if (subtreeRoot == null)
8: {
9: return "(empty tree)";
10: }
12: // First convert the tree to an array of line strings
13: String[] lines = treeToLines(subtreeRoot);
15: // Combine all lines into 1 string
16: String treeString = lines[0];
17: for (int i = 1; i < lines.length; i++)
18: {
19: treeString += ("\n" + lines[i]);
20: }
21: return treeString;
22: //return String.join("\n", lines);
23: }
25: private static String[] treeToLines(Node subtreeRoot)
26: {
27: if (subtreeRoot == null)
28: {
29: return new String[0];
30: }
32: // Make a string with the subtreeRoot's key enclosed in brackets
33: String rootString = "[" + subtreeRoot.key + "]";
34: int rootStrLen = rootString.length();
36: // Case 1: subtreeRoot is a leaf
37: if (subtreeRoot.left == null && subtreeRoot.right == null)
38: {
39: String[] oneLine = new String[1];
40: oneLine[0] = rootString;
41: return oneLine;
42: }
44: // Recursively make line strings for each child
45: String[] leftLines = treeToLines(subtreeRoot.left);
46: String[] rightLines = treeToLines(subtreeRoot.right);
48: int lineCount = Math.max(leftLines.length, rightLines.length);
49: String[] allLines = new String[lineCount + 2];
51: // Case 2: subtreeRoot has no left child
52: if (subtreeRoot.left == null)
53: {
54: // Create the first 2 lines, not yet indented
55: allLines[0] = rootString;
56: allLines[1] = getSpaces(rootStrLen) + "\\";
58: // Find where the right child starts
59: int rightChildIndent = rightLines[0].indexOf('[');
61: // Goal: Indent lines appropriately so that the parent's right
62: // branch character ('\') matches up with the right child's '['.
64: if (rightChildIndent <= rootStrLen)
65: {
66: // Indent all lines below
67: indentLines(rightLines, rootStrLen - rightChildIndent);
68: }
69: else
70: {
71: // Indent first 2 lines
72: String indent = getSpaces(rightChildIndent - rootStrLen);
73: allLines[0] = indent + allLines[0];
74: allLines[1] = indent + allLines[1];
75: }
77: // Copy rightLines into allLines starting at index 2
78: System.arraycopy(rightLines, 0, allLines, 2, rightLines.length);
80: return allLines;
81: }
83: // Case 3: subtreeRoot has no right child
84: if (subtreeRoot.right == null)
85: {
86: // Goal: Indent lines appropriately so that the parent's left
87: // branch character ('/') matches up with the left child's ']'.
89: // Create the first 2 lines
90: String indent = getSpaces(leftLines[0].indexOf(']'));
91: allLines[0] = indent + " " + rootString;
92: allLines[1] = indent + "/";
94: // Copy leftLines into allLines starting at index 2
95: System.arraycopy(leftLines, 0, allLines, 2, leftLines.length);
97: return allLines;
98: }
100: // Case 4: subtreeRoot has both a left and right child
102: // The goal is to have the two child nodes as close to the parent as
103: // possible without overlap on any level.
105: // Compute absolute indentation, in number of spaces,
106: // needed for right lines
107: int indentNeeded = 0;
108: if (rightLines.length > 0)
109: {
110: // Indent should at least get the immediate right child
111: // to be to the right of the root
112: indentNeeded = Math.max
113: (
114: 0,
115: leftLines[0].length()
116: + rootString.length()
117: - rightLines[0].indexOf('[')
118: );
119: }
120: for (int i = 0; i < leftLines.length && i < rightLines.length; i += 2)
121: {
122: // Lines with branches are skipped, so the line of interest has
123: // only nodes. The difference between where the left line ends
124: // and the right line begins should be at least 3 spaces for
125: // clarity.
126: int leftEnd = leftLines[i].lastIndexOf(']');
127: int rightBegin = rightLines[i].indexOf('[');
129: int forThisLine = leftLines[i].length() + 3 - rightBegin;
130: indentNeeded = Math.max(indentNeeded, forThisLine);
131: }
133: // Build final lines in allLines starting at index 2
134: String absoluteIndent = getSpaces(indentNeeded);
135: for (int i = 0; i < leftLines.length || i < rightLines.length; i++)
136: {
137: // If no right line, just take the left
138: if (i >= rightLines.length)
139: {
140: allLines[2 + i] = leftLines[i];
141: }
142: else
143: {
144: String left = "";
145: if (i < leftLines.length)
148: {
149: left = leftLines[i];
150: }
151: String right = absoluteIndent + rightLines[i];
152: allLines[2 + i] = left + right.substring(left.length());
153: }
154: }
156: // The first 2 lines remain. allLines[2] has the proper string
157: // for the 2 child nodes, and thus can be used to create branches
158: // in allLines[1].
159: int leftIndex = allLines[2].indexOf(']');
160: int rightIndex = allLines[2].lastIndexOf('[');
161: allLines[1] = getSpaces(leftIndex) + "/" +
162: getSpaces(rightIndex - leftIndex - 1) + "\\";
164: // The space between leftIndex and rightIndex is the space that
165: // subtreeRoot's string should occupy. If rootString is too short,
166: // put underscores on the sides.
167: rootStrLen = rightIndex - leftIndex - 1;
168: if (rootString.length() < rootStrLen)
169: {
170: int difference = rootStrLen - rootString.length();
171: String underscores = getRepeated('_', difference / 2);
172: if (difference % 2 == 0)
173: {
174: rootString = underscores + rootString + underscores;
175: }
176: else
177: {
178: rootString = underscores + rootString + underscores + "_";
179: }
180: }
181: allLines[0] = getSpaces(leftIndex + 1) + rootString;
183: return allLines;
184: }
186: private static String getRepeated
187: (
188: char toRepeat,
189: int numberOfTimes
190: )
191: {
192: if (numberOfTimes <= 0)
193: {
194: return "";
195: }
197: char[] chars = new char[numberOfTimes];
198: for (int i = 0; i < numberOfTimes; i++)
199: {
200: chars[i] = toRepeat;
201: }
202: return new String(chars);
203: }
205: private static String getSpaces(int numberOfSpaces)
206: {
207: return getRepeated(' ', numberOfSpaces);
208: }
210: private static void indentLines
211: (
212: String[] lines,
213: int numberOfSpaces
214: )
215: {
216: if (numberOfSpaces <= 0)
217: {
218: return;
219: }
221: // Prepend indentation to each line
222: String indent = getSpaces(numberOfSpaces);
223: for (int i = 0; i < lines.length; i++)
224: {
225: lines[i] = indent + lines[i];
226: }
227: }
228: }