Binary Tree Inorder Traversal bằng Python

Giả sử chúng ta có một cây nhị phân. Chúng ta phải duyệt qua cây này bằng cách sử dụng lược đồ duyệt inorder mà không sử dụng đệ quy. Vì vậy, nếu cây như

Khi đó đường truyền sẽ là [2,5,7,10,15,20]

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

• Tạo hai res và stack mảng, đặt curr:=root
• Chạy một vòng lặp vô hạn
  • while current không null
    • đẩy curr vào một ngăn xếp và đặt curr:=left of curr
  • khi độ dài của ngăn xếp =0, sau đó trả về res
  • node:=phần tử được bật ra từ ngăn xếp
  • chèn một giá trị của nút vào res
  • curr:=right of curr

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau đây để 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 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 inorderTraversal(self, root):
      res, stack = [], []
      current = root
      while True:
         while current:
            stack.append(current)
            current = current.left
         if len(stack) == 0:
            return res
         node = stack[-1]
         stack.pop(len(stack)-1)
         if node.data != None:
            res.append(node.data)
         current = node.right
      return res
ob1 = Solution()
root = make_tree([10,5,15,2,7,None,20])
print(ob1.inorderTraversal(root))

Đầu vào

[10,5,15,2,7,null,20]

Đầu ra

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