Giả sử chúng ta có Cây tìm kiếm nhị phân (BST), chúng ta phải tìm trung vị của nó. Chúng ta biết đối với số nút chẵn, trung vị =((n / nút thứ 2 + (n + 1) / nút thứ 2) / 2 Đối với số nút lẻ, trung vị =(n + 1) / nút thứ 2.
Vì vậy, nếu đầu vào giống như
thì đầu ra sẽ là 7
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
-
nếu gốc giống như Không thì
-
trả về 0
-
-
node_count:=số lượng nút trong cây
-
count_curr:=0
-
hiện tại:=root
-
trong khi hiện tại không phải là null, thực hiện
-
nếu current.left null, thì
-
count_curr:=count_curr + 1
-
nếu node_count mod 2 không phải là 0 và count_curr giống với (node_count + 1) / 2 thì
-
trả lại dữ liệu trước đó
-
-
ngược lại khi node_count mod 2 bằng 0 và count_curr giống với (node_count / 2) +1 thì
-
return (before.data + current.data) / 2
-
-
trước:=hiện tại
-
current:=current.right
-
-
nếu không,
-
trước:=current.left
-
trong khi trước đó.right không phải là null và trước đó.right không giống như hiện tại, thực hiện
-
trước:=before.right
-
-
nếu before.right là null thì
-
before.right:=current
-
current:=current.left
-
-
nếu không,
-
before.right:=Không có
-
trước:=trước đó
-
count_curr:=count_curr + 1
-
nếu node_count mod 2 không phải là 0 và count_curr giống với (node_count + 1) / 2 thì
-
trả về dữ liệu current.data
-
-
ngược lại khi node_count mod 2 bằng 0 và count_curr giống như (node_count / 2) + 1 thì
-
return (before.data + current.data) / 2
-
-
trước:=hiện tại
-
current:=current.right
-
-
-
Ví dụ
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
class TreeNode: def __init__(self, data): self.data = data self.left = None self.right = None def number_of_nodes(root): node_count = 0 if (root == None): return node_count current = root while (current != None): if (current.left == None): node_count+=1 current = current.right else: previous = current.left while (previous.right != None and previous.right != current): previous = previous.right if(previous.right == None): previous.right = current current = current.left else: previous.right = None node_count += 1 current = current.right return node_count def calculate_median(root): if (root == None): return 0 node_count = number_of_nodes(root) count_curr = 0 current = root while (current != None): if (current.left == None): count_curr += 1 if (node_count % 2 != 0 and count_curr == (node_count + 1)//2): return previous.data elif (node_count % 2 == 0 and count_curr == (node_count//2)+1): return (previous.data + current.data)//2 previous = current current = current.right else: previous = current.left while (previous.right != None and previous.right != current): previous = previous.right if (previous.right == None): previous.right = current current = current.left else: previous.right = None previous = previous count_curr+= 1 if (node_count % 2 != 0 and count_curr == (node_count + 1) // 2 ): return current.data elif (node_count%2 == 0 and count_curr == (node_count // 2) + 1): return (previous.data+current.data)//2 previous = current current = current.right root = TreeNode(7) root.left = TreeNode(4) root.right = TreeNode(9) root.left.left = TreeNode(2) root.left.right = TreeNode(5) root.right.left = TreeNode(8) root.right.right = TreeNode(10) print(calculate_median(root))
Đầu vào
root = TreeNode(7) root.left = TreeNode(4) root.right = TreeNode(9) root.left.left = TreeNode(2) root.left.right = TreeNode(5) root.right.left = TreeNode(8) root.right.right = TreeNode(10)
Đầu ra
7