Hướng dẫn python tree traversal iterative - cây trăn lặp đi lặp lại

Cách truy cập các nút trong cây nhị phân - lặp đi lặp lại

Việc viết mã đệ quy rất đơn giản là rất đơn giản. Ngăn xếp được sử dụng nội bộ cho đệ quy. Trong blog này, chúng tôi sử dụng Stack và Hàng đợi để thực hiện các đường truyền cây lặp đi lặp lại.

Thứ tự

Subtree trái → Root → Subtree bên phải

Approach:

• Tạo một ngăn xếp trống và đẩy nút gốc.
• khai báo một biến để theo dõi nút hiện tại
• Chạy trong khi vòng lặp cho đến khi ngăn xếp không trống hoặc nút hiện tại không có
• Chúng tôi tiếp tục thêm nút hiện tại còn lại trong ngăn xếp.
• Khi nút hiện tại trở thành không có & ngăn xếp không trống, chúng tôi bật phần tử từ ngăn xếp và gán nó dưới dạng nút hiện tại.
• Xử lý nút hiện tại và sau đó đặt nút hiện tại thành nút hiện tại bên phải.

def inorder_traversal(root):
    res = []
    if not root:
        return res
    stack = []
    curr_node = root
    while curr_node or stack:
        while curr_node:
            stack.append(curr_node)
            curr_node = curr_node.left
        curr_node = stack.pop();
        res.append(curr_node.val);
        curr_node = curr_node.right;
        return res

Đặt hàng trước

Root → Subtree bên trái → Subtree phải

Approach:

• Tạo một ngăn xếp trống và đẩy nút gốc.
• khai báo một biến để theo dõi nút hiện tại
• Chạy trong khi vòng lặp cho đến khi ngăn xếp không trống hoặc nút hiện tại không có
• Chúng tôi tiếp tục thêm nút hiện tại còn lại trong ngăn xếp.
• Khi nút hiện tại trở thành không có & ngăn xếp không trống, chúng tôi bật phần tử từ ngăn xếp và gán nó dưới dạng nút hiện tại.
• Xử lý nút hiện tại và sau đó đặt nút hiện tại thành nút hiện tại bên phải.

def preorder_traversal(root):
    res = []
    if not root:
        return res
     stack = [root]
    while stack:
        curr_node = stack.pop()
        res.append(curr_node.val)
        if curr_node.right:
            stack.append(curr_node.right)
        if curr_node.left:
            stack.append(curr_node.left)
    return res

Đặt hàng trước

Root → Subtree bên trái → Subtree phải

Approach:

• Chạy trong khi vòng lặp cho đến khi ngăn xếp không trống
• Chúng tôi bật ngăn xếp và gán nút bật lên làm nút hiện tại
• Xử lý nút hiện tại
• Đẩy nút hiện tại bên phải và các nút bên trái từng cái một
• Bưu điện
• Subtree trái → Subtree bên phải → root
• Chúng tôi tạo hai ngăn xếp, một để theo dõi nút hiện tại và một ngăn nữa để theo dõi đúng trẻ em.

def postorder_traversal(root):
    res = []
    if not root:
        return res
    curr_node = root
    stack = []
    right_stack = []
    while stack or curr_node:
        if curr_node:
            if curr_node.right:
                right_stack.append(curr_node.right)
            stack.append(curr_node)
            curr_node = curr_node.left
        else:
            curr_node = stack[-1]
            if right_stack and curr_node.right == right_stack[-1]:
                curr_node = right_stack.pop()
            else:
                res.append(curr_node.val)
                stack.pop()
                curr_node = None
            return res

Chúng tôi chạy vòng lặp trong khi ngăn xếp nút hiện tại không trống hoặc nút hiện tại không phải là không có

Chúng tôi đẩy nút hiện tại ngay trong ngăn xếp trẻ em bên phải

def buildTree(inorder, postorder):
    in_order_idx, post_order_idx = len(inorder)-1, len(postorder)-1
    switch_side = False
    prev = root = TreeNode(postorder[post_order_idx])
    stack = [root]
    post_order_idx -= 1
    while post_order_idx >=0 :
        if stack and inorder[in_order_idx] == stack[-1].val:
            prev = stack.pop()
            in_order_idx -= 1
            switch_side = True
        else:
            node = TreeNode(postorder[post_order_idx])
            if not switch_side:
                prev.right = node
                prev = prev.right
            else:
                prev.left = node
                prev = prev.left
                switch_side = False
            stack.append(node)
            post_order_idx -= 1
    return root

Nút hiện tại được đẩy lên ngăn xếp

Nút hiện tại được đặt thành con trái của nó

Approach:

Nếu đúng đứa trẻ được xử lý, chúng tôi xử lý nút hiện tại

def level_order(root):
    if not root:
        return []
    from collections import deque
    q = deque([(root, 0)])
    level_map = {}
        while q:
        node, level = q.popleft()
        if level not in level_map:
            level_map[level] = [node.val]
        else:
            level_map[level].append(node.val)
        if node.left:
            q.append((node.left, level+1))
        if node.right:
            q.append((node.right, level+1))
    n = max(level_map)    return [level_map[level] for level in range(n+1)]

Nếu nút bên phải không được xử lý, chúng tôi xử lý nút hiện tại và đặt nút hiện tại là không có.

Biểu đồ dưới đây tóm tắt biểu diễn mảng của ba lần trên. Những quan sát này giúp chúng ta tái tạo cây nhị phân cho các đường truyền.

Sử dụng thuộc tính trên, chúng ta có thể xây dựng một cây nếu chúng ta đã được cung cấp thông tin và bưu điện.

def right_view(root):
    if not root:
        return []
    level_map = {}
    from collections import deque
    q = deque([(root, 0)])
    while q:
        node, level = q.popleft()
        if level not in level_map:
            level_map[level] = node.val
        if node.left:
            q.append((node.left, level+1))
        if node.right:
            q.append((node.right, level+1))
    n = max(level_map)    return [level_map[level] for level in range(n+1)]

Lệnh cấp

Root → Tất cả trẻ em → Tất cả trẻ em của cấp độ cuối cùng

def right_view(root):
    if not root:
        return []
    level_map = {}
    from collections import deque
    q = deque([(root, 0)])
    while q:
        node, level = q.popleft()
        level_map[level] = node.val
        if node.left:
            q.append((node.left, level+1))
        if node.right:
            q.append((node.right, level+1))
    n = max(level_map)    return [level_map[level] for level in range(n+1)]

Chúng tôi sử dụng cấu trúc dữ liệu bản đồ để lưu trữ tất cả các nút ở cùng cấp độ. Chúng tôi cũng sử dụng một hàng đợi để xử lý các nút. Chúng tôi bật từ phía bên trái của quá trình hàng đợi các nút và sau đó thêm nút hiện tại trẻ em vào cuối hàng đợi. Trong khi chúng tôi làm như vậy, chúng tôi tăng mức độ của nút.

Các vấn đề đã được giải quyết bằng cách sử dụng Traversal theo thứ tự cấp độ:

Chế độ xem bên trái

Ý tưởng: Chỉ số đầu tiên của danh sách các nút theo thứ tự cấp độ ở mọi cấp độ.

from collections import deque
def top_view(root):
    if not root:
        return []    pos_map = {}
    q = deque([(root, 0)])    while q:
        node, pos = q.popleft()
        if pos not in pos_map:
            pos_map[pos] = node.val
        if node.left:
            q.append((node.left, pos-1))
        if node.right:
            q.append((node.right, pos+1))
            m, n = min(pos_map), max(pos_map)
        return [pos_map[pos] for pos in range(m, n+1)]

Chế độ xem bên phải

Ý tưởng: Chỉ số cuối cùng của danh sách các nút theo thứ tự cấp độ ở mọi cấp độ.

from collections import deque
def top_view(root):
    if not root:
        return []    pos_map = {}
    q = deque([(root, 0)])    while q:
        node, pos = q.popleft()
        pos_map[pos] = node.val
        if node.left:
            q.append((node.left, pos-1))
        if node.right:
            q.append((node.right, pos+1))
            m, n = min(pos_map), max(pos_map)
        return [pos_map[pos] for pos in range(m, n+1)]

Thứ tự hàng đầu

Trong lần đi ngang này, chúng tôi duy trì khoảng cách từ gốc (trái → -1 & phải → +1). Chúng tôi lưu trữ danh sách các nút ở cùng một khoảng cách trong khóa đối tượng bản đồ là khoảng cách.PlainEnglish.io. Sign up for our free weekly newsletter. Follow us on Twitter andLinkedIn. Join our community Discord.