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: }
24: private static String[] treeToLines(Node subtreeRoot)
25: {
26: if (subtreeRoot == null)
27: {
28: return new String[0];
29: }
31: // Make a string with the subtreeRoot's key enclosed in brackets
32: String rootString = "[" + subtreeRoot.key + "]";
33: int rootStrLen = rootString.length();
35: // Case 1: subtreeRoot is a leaf
36: if (subtreeRoot.left == null && subtreeRoot.right == null)
37: {
38: String[] oneLine = new String[1];
39: oneLine[0] = rootString;
40: return oneLine;
41: }
43: // Recursively make line strings for each child
44: String[] leftLines = treeToLines(subtreeRoot.left);
45: String[] rightLines = treeToLines(subtreeRoot.right);
47: int lineCount = Math.max(leftLines.length, rightLines.length);
48: String[] allLines = new String[lineCount + 2];
50: // Case 2: subtreeRoot has no left child
51: if (subtreeRoot.left == null)
52: {
53: // Create the first 2 lines, not yet indented
54: allLines[0] = rootString;
55: allLines[1] = getSpaces(rootStrLen) + "\\";
57: // Find where the right child starts
58: int rightChildIndent = rightLines[0].indexOf('[');
60: // Goal: Indent lines appropriately so that the parent's right
61: // branch character ('\') matches up with the right child's '['.
63: if (rightChildIndent <= rootStrLen)
64: {
65: // Indent all lines below
66: indentLines(rightLines, rootStrLen - rightChildIndent);
67: }
68: else
69: {
70: // Indent first 2 lines
71: String indent = getSpaces(rightChildIndent - rootStrLen);
72: allLines[0] = indent + allLines[0];
73: allLines[1] = indent + allLines[1];
74: }
76: // Copy rightLines into allLines starting at index 2
77: System.arraycopy(rightLines, 0, allLines, 2, rightLines.length);
79: return allLines;
80: }
82: // Case 3: subtreeRoot has no right child
83: if (subtreeRoot.right == null)
84: {
85: // Goal: Indent lines appropriately so that the parent's left
86: // branch character ('/') matches up with the left child's ']'.
88: // Create the first 2 lines
89: String indent = getSpaces(leftLines[0].indexOf(']'));
90: allLines[0] = indent + " " + rootString;
91: allLines[1] = indent + "/";
93: // Copy leftLines into allLines starting at index 2
94: System.arraycopy(leftLines, 0, allLines, 2, leftLines.length);
96: return allLines;
97: }
99: // Case 4: subtreeRoot has both a left and right child
101: // The goal is to have the two child nodes as close to the parent as
102: // possible without overlap on any level.
104: // Compute absolute indentation, in number of spaces,
105: // needed for right lines
106: int indentNeeded = 0;
107: if (rightLines.length > 0)
108: {
109: // Indent should at least get the immediate right child
110: // to be to the right of the root
111: indentNeeded = Math.max
112: (
113: 0,
114: leftLines[0].length()
115: + rootString.length()
116: - rightLines[0].indexOf('[')
117: );
118: }
119: for (int i = 0; i < leftLines.length && i < rightLines.length; i += 2)
120: {
121: // Lines with branches are skipped, so the line of interest has
122: // only nodes. The difference between where the left line ends and
123: // the right line begins should be at least 3 spaces for clarity.
124: int leftEnd = leftLines[i].lastIndexOf(']');
125: int rightBegin = rightLines[i].indexOf('[');
127: int forThisLine = leftLines[i].length() + 3 - rightBegin;
128: indentNeeded = Math.max(indentNeeded, forThisLine);
129: }
131: // Build final lines in allLines starting at index 2
132: String absoluteIndent = getSpaces(indentNeeded);
133: for (int i = 0; i < leftLines.length || i < rightLines.length; i++)
134: {
135: // If no right line, just take the left
136: if (i >= rightLines.length)
137: {
138: allLines[2 + i] = leftLines[i];
139: }
140: else
141: {
142: String left = "";
143: if (i < leftLines.length)
144: {
145: left = leftLines[i];
146: }
147: String right = absoluteIndent + rightLines[i];
148: allLines[2 + i] = left + right.substring(left.length());
149: }
150: }
152: // The first 2 lines remain. allLines[2] has the proper string for the
153: // 2 child nodes, and so can be used to create branches in allLines[1].
154: int leftIndex = allLines[2].indexOf(']');
155: int rightIndex = allLines[2].lastIndexOf('[');
156: allLines[1] = getSpaces(leftIndex) + "/" +
157: getSpaces(rightIndex - leftIndex - 1) + "\\";
159: // The space between leftIndex and rightIndex is the space that
160: // subtreeRoot's string should occupy. If rootString is too short,
161: // put underscores on the sides.
162: rootStrLen = rightIndex - leftIndex - 1;
163: if (rootString.length() < rootStrLen)
164: {
165: int difference = rootStrLen - rootString.length();
166: String underscores = getRepeated('_', difference / 2);
167: if (difference % 2 == 0)
168: {
169: rootString = underscores + rootString + underscores;
170: }
171: else
172: {
173: rootString = underscores + rootString + underscores + "_";
174: }
175: }
176: allLines[0] = getSpaces(leftIndex + 1) + rootString;
178: return allLines;
179: }
181: private static String getRepeated
182: (
183: char toRepeat,
184: int numberOfTimes
185: )
186: {
187: if (numberOfTimes <= 0)
188: {
189: return "";
190: }
192: char[] chars = new char[numberOfTimes];
193: for (int i = 0; i < numberOfTimes; i++)
194: {
195: chars[i] = toRepeat;
196: }
197: return new String(chars);
198: }
200: private static String getSpaces(int numberOfSpaces)
201: {
202: return getRepeated(' ', numberOfSpaces);
203: }
205: private static void indentLines
206: (
207: String[] lines,
208: int numberOfSpaces
209: )
210: {
211: if (numberOfSpaces <= 0)
212: {
213: return;
214: }
216: // Prepend indentation to each line
217: String indent = getSpaces(numberOfSpaces);
218: for (int i = 0; i < lines.length; i++)
219: {
220: lines[i] = indent + lines[i];
221: }
222: }
223: }