Chương trình tìm tổ tiên thứ K của nút cây trong Python

Giả sử chúng ta có một cây với n nút được đánh số từ 0 đến n-1. Cây được cung cấp bởi một mảng cha, trong đó cha [i] là cha của nút i. Gốc của cây là nút 0. Chúng ta phải tìm tổ tiên thứ k của một nút đã cho, nếu tổ tiên không có mặt thì trả về -1

Vì vậy, nếu đầu vào giống như

thì đầu ra sẽ là 2 vì tổ tiên đầu tiên của nút 6 là 5 và nút thứ hai là 2.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• Định nghĩa một hàm giải quyết (). Điều này sẽ lấy cha, nút, k

• nếu nút giống -1, thì

  • trả về -1

• ngược lại khi k giống 1 thì

  • trả về [nút] cha mẹ

• ngược lại khi (k VÀ k-1) bằng 0 thì

  • trả về giải (cha, giải (cha, nút, thương của k / 2), thương của k / 2)

• nếu không,

  • msb:=2 ^ (số bit của k -1)

  • trả về giải quyết (cha, giải quyết (cha, nút, k-msb), msb)

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau đây để hiểu rõ hơn

def solve(parent, node, k):
   if node == -1:
      return -1
   elif k == 1:
      return parent[node]
   elif not (k & k-1):
      return solve(parent, solve(parent, node, k >> 1), k >> 1)
   else:
      msb = 1 << (k.bit_length()-1)
      return solve(parent, solve(parent, node, k-msb), msb)

parent = [-1,0,0,1,2,2,5,5]
node = 6
k = 2
print(solve(parent, node, k))

Đầu vào

[6,7,9,16,22], 2

Đầu ra

2