Xây dựng chuỗi từ cây nhị phân bằng Python

Giả sử chúng ta có một cây nhị phân, chúng ta phải tạo một chuỗi bao gồm dấu ngoặc đơn và các số nguyên từ cây nhị phân với cách đặt hàng trước. Một nút rỗng sẽ được biểu diễn bằng cặp dấu ngoặc đơn "()". Và chúng ta cần bỏ qua tất cả các cặp dấu ngoặc trống không ảnh hưởng đến mối quan hệ ánh xạ theo một đối một giữa chuỗi và cây nhị phân ban đầu.

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

thì đầu ra sẽ là 5 (6 () (8)) (7)

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

• ans:=chuỗi trống
• Xác định một hàm pot (). Điều này sẽ lấy nút, s
• nếu là null, thì
  • trả về chuỗi trống
• nếu bên trái hoặc bên phải của nút là rỗng, thì
  • trả về node.data
• ss:=node.data
• nếu node.left không phải là null, thì
  • ss:=ss concatenate '(' concatenate pot (node.left, blank string) concatenate ')'
• nếu không,
  • ss:=ss concatenate '()'
• nếu node.right không phải là null, thì
  • ss:=ss concatenate '(' concatenate pot (node.right, blank string) concatenate ')'
• trả lại ss
• Từ phương thức chính, hãy làm như sau -
• return pot (t, chuỗi trống)

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

Ví dụ

class TreeNode:
   def __init__(self, data, left = None, right = None):
      self.data = data
      self.left = left
      self.right = right
def insert(temp,data):
      que = []
      que.append(temp)
      while (len(que)):
         temp = que[0]
         que.pop(0)
         if (not temp.left):
            if data is not None:
               temp.left = TreeNode(data)
            else:
               temp.left = TreeNode(0)
            break
         else:
            que.append(temp.left)
         if (not temp.right):
            if data is not None:
               temp.right = TreeNode(data)
            else:
               temp.right = TreeNode(0)
            break
         else:
            que.append(temp.right)
def make_tree(elements):
   Tree = TreeNode(elements[0])
   for element in elements[1:]:
      insert(Tree, element)
   return Tree
class Solution:
   def tree2str(self, t: TreeNode):
      ans = ''
      def pot(node, s):
         if node == None or node.data == 0:
            return ''
         if node.left == node.right == None:
            return str(node.data)
         ss = str(node.data)
         if node.left != None:
            ss = ss + '(' + pot(node.left, '') + ')'
         else:
            ss = ss + '()'
         if node.right != None:
            ss = ss + '(' + pot(node.right, '') + ')'
         return ss
      return pot(t, '')
ob = Solution()
root = make_tree([5,6,7,None,8])
print(ob.tree2str(root))

Đầu vào

[5,6,7,None,8]

Đầu ra

5(6()(8))(7)