Đâ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
Làm thế nào để bạn in một cây nhị phân theo thứ tự được sắp xếp?
Bạn bắt đầu đi qua từ gốc, sau đó đi đến nút bên trái, sau đó bạn lại đi đến nút bên trái cho đến khi bạn đến một nút lá.Tại thời điểm đó, bạn in giá trị của nút hoặc đánh dấu nó khi truy cập và di chuyển sang cây con bên phải.Tiếp tục cùng một thuật toán cho đến khi tất cả các nút của cây nhị phân được truy cập.
Làm thế nào để bạn sắp xếp một cây nhị phân trong Python?
Chương trình Python để sắp xếp bằng cây tìm kiếm nhị phân..
Tạo một lớp bstnode với phím biến thể, trái, phải và cha mẹ ..
Xác định các phương thức chèn và inorder trong bstnode ..
Phương thức Chèn lấy một nút làm đối số và chèn nút đó trong BST với đối tượng BSTNode là gốc ..