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