Xây dựng Cây tìm kiếm nhị phân từ thứ tự bưu điện đã cho bằng Python

Giả sử chúng ta có trình tự duyệt thứ tự của cây tìm kiếm nhị phân. Chúng ta phải tạo cây từ các chuỗi này. Vì vậy, nếu các trình tự sắp xếp sau là [9,15,7,20,3], thì cây sẽ là -

Để tạo một cây, chúng ta cũng cần trình duyệt inorder, nhưng đối với cây tìm kiếm nhị phân, trình duyệt inorder sẽ ở dạng được sắp xếp.

Hãy để chúng tôi xem các bước -

• Inorder =danh sách được sắp xếp của việc truyền đơn đặt hàng.

• Xác định phương thức build_tree (), điều này sẽ mất inorder, postorder -

• Nếu danh sách inorder không trống -

  • root:=tạo một nút cây với giá trị cuối cùng của postorder, sau đó xóa phần tử đó

  • ind:=chỉ mục của dữ liệu gốc trong danh sách inorder

  • quyền của root:=build_tree (inorder từ index ind đến end, postorder)

  • left of root:=build_tree (inorder từ 0 đến index ind - 1, postorder)

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

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, left = None, right = None):
      self.data = data
      self.left = left
      self.right = right
def print_tree(root):
   if root is not None:
      print_tree(root.left)
      print(root.data, end = ', ')
      print_tree(root.right)
class Solution(object):
   def buildTree(self, inorder, postorder):
      if inorder:
         root = TreeNode(postorder.pop())
         ind = inorder.index(root.data)
         root.right = self.buildTree(inorder[ind+1:],postorder)
         root.left = self.buildTree(inorder[:ind],postorder)
         return root
ob1 = Solution()
postorder = [3,9,20,15,7]
inorder = list(sorted([3,9,20,15,7]))
print_tree(ob1.buildTree(inorder, postorder))

Đầu vào

[9,3,15,20,7]
[9,15,7,20,3]

Đầu ra

[3,7,9,15,20]