Duyệt DFS pre-order (gốc, trái, phải) trên cây nhị phân, in quá trình vào/ra nút.
Ví dụ
class BinaryTree:
def __init__(self, key):
self.key = key
self.left = None
self.right = None
def insert_left(self, node):
self.left = node
def insert_right(self, node):
self.right = node
def search(self, key):
if self.key == key:
return self
if self.left:
res = self.left.search(key)
if res: return res
if self.right:
return self.right.search(key)
return None
def dfs(self):
print(f"Vào {self.key}...")
if self.left:
self.left.dfs()
print(f"Tại {self.key}...")
if self.right:
self.right.dfs()
print(f"Ra {self.key}...")
# Demo
root = None
while True:
cmd = input("Cmd (insert/dfs/quit): ").split()
if not cmd: continue
if cmd[0] == 'insert':
val = int(cmd[1])
node = BinaryTree(val)
if cmd[2] == 'at':
root = node
else:
parent = root.search(int(cmd[4]))
if parent:
if cmd[2] == 'left':
parent.insert_left(node)
else:
parent.insert_right(node)
elif cmd[0] == 'dfs':
if root:
print("DFS traversal:")
root.dfs()
else:
print("Cây rỗng")
elif cmd[0] == 'quit':
break
Kết quả
Cmd (insert/dfs/quit): insert 5 at root Cmd (insert/dfs/quit): insert 6 left of 5 Cmd (insert/dfs/quit): insert 8 right of 5 Cmd (insert/dfs/quit): dfs DFS traversal: Vào 5... Vào 6... Tại 6... Ra 6... Tại 5... Vào 8... Tại 8... Ra 8... Ra 5... Cmd (insert/dfs/quit): quit
Giải thích
- DFS pre-order: xử lý nút, đệ quy trái, đệ quy phải.
- In log "Vào", "Tại", "Ra" để minh họa stack gọi hàm.
- Cây: 5 (left=6, right=8). Thứ tự: 5, 6, 8.
- Menu tương tác.