Traversal đặt hàng trước cây nhị phân bằng Python

Giả sử chúng ta có một cây nhị phân. Chúng tôi phải trả lại trình duyệt đặt hàng trước của cây đó. Vì vậy, nếu cây như -

Sau đó, truyền tải đặt hàng trước sẽ là:[3,9,20,15,7]

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

• tạo danh sách trống được gọi là res và st.
• nút:=root
• trong khi nút hoặc st không trống
  • trong khi nút không rỗng, thì
    • chèn val của nút vào res, chèn nút vào st và đặt nút:=bên trái của nút
  • temp:=phần tử cuối cùng của st và xóa phần tử cuối cùng của st
  • nếu quyền tạm thời có sẵn, thì
    • node:=right of temp
• trả lại res

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):
         temp.left = TreeNode(data)
         break
      else:
         que.append(temp.left)
      if (not temp.right):
         temp.right = TreeNode(data)
         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(object):
   def preorderTraversal(self, root):
      res = []
      st = []
      node = root
      while node or st:
         while node:
            if node.data != None:
               res.append(node.data)
            st.append(node)
            node = node.left
         temp = st[-1]
         st.pop()
         if temp.right:
            node = temp.right
   return res
ob1 = Solution()
head = make_tree([3,9,20,None,None,15,7])
print(ob1.preorderTraversal(head))

Đầu vào

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

Đầu ra

[3, 9, 20, 15, 7]