Đây là một phần của việc thực hiện BST của riêng tôi.Phần xấu của vấn đề này là bạn phải biết không gian mà con bạn chiếm giữ trước khi bạn có thể in ra.Bởi vì bạn có thể có những con số rất lớn như 217348746327642386478832541267836128736 ... nhưng cũng có những con số nhỏ như 10, vì vậy nếu bạn có mối quan hệ giữa cha mẹ giữa hai người này, thì nó có thể có khả năng chồng chéo với đứa trẻ khác.Do đó, trước tiên chúng ta cần phải trải qua những đứa trẻ, đảm bảo chúng ta có được bao nhiêu không gian chúng có, sau đó chúng ta sử dụng thông tin đó để tự xây dựng.
def __str__[self]:
h = self.getHeight[]
rowsStrs = ["" for i in range[2 * h - 1]]
# return of helper is [leftLen, curLen, rightLen] where
# leftLen = children length of left side
# curLen = length of keyStr + length of "_" from both left side and right side
# rightLen = children length of right side.
# But the point of helper is to construct rowsStrs so we get the representation
# of this BST.
def helper[node, curRow, curCol]:
if[not node]: return [0, 0, 0]
keyStr = str[node.key]
keyStrLen = len[keyStr]
l = helper[node.l, curRow + 2, curCol]
rowsStrs[curRow] += [curCol -len[rowsStrs[curRow]] + l[0] + l[1] + 1] * " " + keyStr
if[keyStrLen < l[2] and [node.r or [node.p and node.p.l == node]]]:
rowsStrs[curRow] += [l[2] - keyStrLen] * "_"
if[l[1]]:
rowsStrs[curRow + 1] += [len[rowsStrs[curRow + 2]] - len[rowsStrs[curRow + 1]]] * " " + "/"
r = helper[node.r, curRow + 2, len[rowsStrs[curRow]] + 1]
rowsStrs[curRow] += r[0] * "_"
if[r[1]]:
rowsStrs[curRow + 1] += [len[rowsStrs[curRow]] - len[rowsStrs[curRow + 1]]] * " " + "\\"
return [l[0] + l[1] + 1, max[l[2] - keyStrLen, 0] + keyStrLen + r[0], r[1] + r[2] + 1]
helper[self.head, 0, 0]
res = "\n".join[rowsStrs]
#print["\n\n\nStart of BST:****************************************"]
#print[res]
#print["End of BST:****************************************"]
#print["BST height: ", h, ", BST size: ", self.size]
return res
Đây là một số ví dụ về việc chạy này:
[26883404633, 10850198033, 89739221773, 65799970852, 6118714998, 31883432186, 84275473611, 25958013736, 92141734773, 91725885198, 131191476, 81453208197, 41559969292, 90704113213, 6886252839]
26883404633___________________________________________
/ \
10850198033__ 89739221773___________________________
/ \ / \
6118714998_ 25958013736 65799970852_______________ 92141734773
/ \ / \ /
131191476 6886252839 31883432186_ 84275473611 91725885198
\ / /
41559969292 81453208197 90704113213
Một vi dụ khac:
['rtqejfxpwmggfro', 'viwmdmpedzwvvxalr', 'mvvjmkdcdpcfb', 'ykqehfqbpcjfd', 'iuuujkmdcle', 'nzjbyuvlodahlpozxsc', 'wdjtqoygcgbt', 'aejduciizj', 'gzcllygjekujzcovv', 'naeivrsrfhzzfuirq', 'lwhcjbmcfmrsnwflezxx', 'gjdxphkpfmr', 'nartcxpqqongr', 'pzstcbohbrb', 'ykcvidwmouiuz']
rtqejfxpwmggfro____________________
/ \
mvvjmkdcdpcfb_____________________________ viwmdmpedzwvvxalr_______________
/ \ \
iuuujkmdcle_________ nzjbyuvlodahlpozxsc_ ykqehfqbpcjfd
/ \ / \ /
aejduciizj_____________ lwhcjbmcfmrsnwflezxx naeivrsrfhzzfuirq_ pzstcbohbrb wdjtqoygcgbt_
\ \ \
gzcllygjekujzcovv nartcxpqqongr ykcvidwmouiuz
/
gjdxphkpfmr