Chương trình tạo danh sách liên kết với cây tìm kiếm nhị phân bằng Python

Giả sử chúng ta có một nút danh sách liên kết đã được sắp xếp có kích thước n, chúng ta phải tạo một cây tìm kiếm nhị phân bằng cách Lấy giá trị của tầng k =của (n / 2) đặt nó làm gốc. Sau đó, xây dựng đệ quy cây con bên trái bằng cách sử dụng danh sách liên kết bên trái của nút thứ k. Và cấu trúc đệ quy cây con bên phải bằng cách sử dụng danh sách liên kết bên phải của nút thứ k.

Vì vậy, nếu đầu vào là [2,4,5,7,10,15], thì đầu ra sẽ là

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

• Xác định một phương thức giải quyết (), điều này sẽ sử dụng nút

• nếu nút là null, thì

  • trả về null

• nếu nút tiếp theo là null, thì

  • trả về một nút cây mới với giá trị của nút

• chậm:=nút, nhanh:=nút

• trước:=Không có

• trong khi nhanh và tiếp theo của nhanh không phải là rỗng, thực hiện

  • trước:=chậm

  • chậm:=tiếp theo của chậm

  • fast:=next of next of fast

• tiếp theo của trước:=Không có

• root:=một nút cây mới có giá trị chậm

• bên trái của thư mục gốc:=giải quyết (nút)

• quyền gốc:=giải quyết (tiếp theo của chậm)

• trả về thư mục gốc

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

Ví dụ

class ListNode:
   def __init__(self, data, next = None):
      self.val = data
      self.next = next
class TreeNode:
   def __init__(self, data, left = None, right = None):
      self.data = data
      self.left = left
      self.right = right

def make_list(elements):
   head = ListNode(elements[0])
   for element in elements[1:]:
      ptr = head
      while ptr.next:
         ptr = ptr.next
      ptr.next = ListNode(element)
return head

def print_tree(root):
   if root is not None:
      print_tree(root.left)
      print(root.data, end = ', ')
      print_tree(root.right)

class Solution:
   def solve(self, node):
      if not node:
         return None
      if not node.next:
         return TreeNode(node.val)
      slow = fast = node
      prev = None
      while fast and fast.next:
         prev = slow
         slow = slow.next
         fast = fast.next.next
      prev.next = None
      root = TreeNode(slow.val)
      root.left = self.solve(node)
      root.right = self.solve(slow.next)

      return root

ob = Solution()
head = make_list([2,4,5,7,10,15])
root = ob.solve(head)
print_tree(root)

Đầu vào

[2,4,5,7,10,15]

Đầu ra

2, 4, 5, 7, 10, 15,