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
- while current không null
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]