Tạo bản sao gương của cây nhị phân: đổi chỗ left/right đệ quy, sau đó duyệt BFS so sánh.
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 mirror_copy(self):
mirror = BinaryTree(self.key)
if self.right:
mirror.left = self.right.mirror_copy()
if self.left:
mirror.right = self.left.mirror_copy()
return mirror
def bfs(self):
queue = [self]
while queue:
node = queue.pop(0)
print(node.key, end=' ')
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
# Demo
root = None
while True:
cmd = input("Cmd (insert/mirror/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] == 'mirror':
if root:
print("Tạo mirror...")
mirror = root.mirror_copy()
print("BFS gốc:", end=' ')
root.bfs()
print()
print("BFS mirror:", end=' ')
mirror.bfs()
print()
elif cmd[0] == 'quit':
break
Kết quả
Cmd (insert/mirror/quit): insert 6 at root Cmd (insert/mirror/quit): insert 9 left of 6 Cmd (insert/mirror/quit): insert 4 right of 6 Cmd (insert/mirror/quit): mirror Tạo mirror... BFS gốc: 6 9 4 BFS mirror: 6 4 9 Cmd (insert/mirror/quit): quit
Giải thích
mirror_copyđệ quy: tạo nút mới, gán left = mirror của right gốc, right = mirror của left gốc.- BFS in theo cấp độ để so sánh dễ dàng.
- Cây gốc: 6 (left=9, right=4). Mirror: 6 (left=4, right=9).
- Menu tương tác xây cây và tạo mirror.