Chương trình Python DFS post-order traversal

Duyệt cây theo post-order (con trước, cha sau) dùng đệ quy.

Ví dụ

class TreeNode:
    def __init__(self, key):
        self.key = key
        self.children = []

    def add_child(self, node):
        self.children.append(node)

    def search(self, key):
        if self.key == key:
            return self
        for child in self.children:
            res = child.search(key)
            if res: return res
        return None

    def postorder(self):
        for child in self.children:
            child.postorder()
        print(self.key, end=' ')

root = None
while True:
    cmd = input("Cmd (add/dfs/quit): ").split()
    if not cmd: continue
    if cmd[0] == 'add':
        val = int(cmd[1])
        node = TreeNode(val)
        if cmd[2] == 'at':
            root = node
        else:
            parent = root.search(int(cmd[3]))
            if parent:
                parent.add_child(node)
    elif cmd[0] == 'dfs':
        if root:
            print("Post-order:", end=' ')
            root.postorder()
            print()
        else:
            print("Cây rỗng")
    elif cmd[0] == 'quit':
        break

Kết quả

Cmd (add/dfs/quit): add 5 at root
Cmd (add/dfs/quit): add 9 below 5
Cmd (add/dfs/quit): add 2 below 9
Cmd (add/dfs/quit): dfs
Post-order: 2 9 5
Cmd (add/dfs/quit): quit

Giải thích

• Post-order: duyệt tất cả con trước, rồi mới xử lý nút hiện tại.
• Đệ quy tự nhiên: for child in children: child.postorder() rồi print(key).
• Cây demo: 5 -> 9 -> 2. Post-order: 2, 9, 5.
• Menu tương tác xây cây.