Xây dựng cây nhị phân từ Postorder và Inorder bằng Python

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

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

• 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()
print_tree(ob1.buildTree([9,3,15,20,7], [9,15,7,20,3]))

Đầu vào

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

Đầu ra

[9,3,15,20,7]