Duyệt tiền thứ tự cây nhị phân trong Python

Giả sử chúng ta có một cây nhị phân. Chúng ta phải trả về thứ tự duyệt tiền thứ tự (preorder) của cây đó. Nếu cây như sau:

Thứ tự duyệt tiền thứ tự sẽ là: [3,9,20,15,7]

Để giải quyết, ta thực hiện các bước sau:

• Tạo danh sách rỗng res và st.
• node := root
• while node hoặc st không rỗng
  • while node không null
    • Thêm giá trị node vào res, thêm node vào st và gán node := left của node
  • temp := phần tử cuối của st, và xóa phần tử cuối của st
  • nếu right của temp tồn tại
    • node := right của temp
• return res

Hãy xem 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))

Input

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

Output

[3, 9, 20, 15, 7]