Khi được yêu cầu tạo bản sao nhân bản của cây và hiển thị nó bằng cách sử dụng tìm kiếm đầu tiên theo chiều rộng, một lớp cây nhị phân được tạo với các phương thức đặt phần tử gốc, chèn phần tử sang trái, chèn phần tử sang phải, tìm kiếm một phần tử cụ thể, và thực hiện duyệt đơn hàng đăng, v.v. Một thể hiện của lớp được tạo và nó có thể được sử dụng để truy cập các phương thức.
Dưới đây là minh chứng về điều tương tự -
Ví dụ
class BinaryTree_struct:
def __init__(self, key=None):
self.key = key
self.left = None
self.right = None
def set_root(self, key):
self.key = key
def insert_to_left(self, new_node):
self.left = new_node
def insert_to_right(self, new_node):
self.right = new_node
def search_elem(self, key):
if self.key == key:
return self
if self.left is not None:
temp = self.left.search_elem(key)
if temp is not None:
return temp
if self.right is not None:
temp = self.right.search_elem(key)
return temp
return None
def copy_mirror(self):
mirror = BinaryTree_struct(self.key)
if self.right is not None:
mirror.left = self.right.copy_mirror()
if self.left is not None:
mirror.right = self.left.copy_mirror()
return mirror
def bfs(self):
queue = [self]
while queue != []:
popped = queue.pop(0)
if popped.left is not None:
queue.append(popped.left)
if popped.right is not None:
queue.append(popped.right)
print(popped.key, end=' ')
my_instance = None
print('Menu (this assumes no duplicate keys)')
print('insert <data> at root')
print('insert <data> left of <data>')
print('insert <data> right of <data>')
print('mirror')
print('quit')
while True:
my_input = input('What operation would you do ? ').split()
operation = my_input[0].strip().lower()
if operation == 'insert':
data = int(my_input[1])
new_node = BinaryTree_struct(data)
suboperation = my_input[2].strip().lower()
if suboperation == 'at':
my_instance = new_node
else:
position = my_input[4].strip().lower()
key = int(position)
ref_node = None
if my_instance is not None:
ref_node = my_instance.search_elem(key)
if ref_node is None:
print('No such key exists..')
continue
if suboperation == 'left':
ref_node.insert_to_left(new_node)
elif suboperation == 'right':
ref_node.insert_to_right(new_node)
elif operation == 'mirror':
if my_instance is not None:
print('Creating a mirror copy...')
mirror = my_instance.copy_mirror()
print('The breadth first search traversal of original tree is : ')
my_instance.bfs()
print()
print('The breadth first traversal of mirror is : ')
mirror.bfs()
print()
elif operation == 'quit':
break Đầu ra
MenuMenu (this assumes no duplicate keys) insert <data> at root insert <data> left of <data> insert <data> right of <data> mirror quit What operation would you do ? insert 6 at root What operation would you do ? insert 9 left of 6 What operation would you do ? insert 4 right of 6 What operation would you do ? mirror Creating a mirror copy... The breadth first search traversal of original tree is : 6 9 4 The breadth first traversal of mirror is : 6 4 9 What operation would you do ?quit Use quit() or Ctrl-D (i.e. EOF) to exit
Giải thích
-
Lớp 'BinaryTree_struct' với các thuộc tính bắt buộc được tạo.
-
Nó có một chức năng ‘init’ được sử dụng để gán các nút bên trái và bên phải cho “Không có”.
-
Phương thức ‘set_root’ được xác định để giúp gán một nút gốc cho một giá trị.
-
Nó có phương thức ‘insert_to_left’ giúp thêm các phần tử vào nút bên trái của cây.
-
Nó có phương thức ‘insert_to_right’ giúp thêm các phần tử vào các nút bên phải của cây.
-
Nó có phương thức ‘bfs’ giúp thực hiện chuyển tải tìm kiếm đầu tiên theo chiều rộng trên cây.
-
Phương thức có tên ‘search_elem’ được xác định, giúp tìm kiếm một phần tử cụ thể.
-
Nó có phương thức ‘copy_mirror’ giúp tạo một bản sao của cây nhị phân.
-
Một phiên bản được tạo và gán cho 'Không có gì'.
-
Đầu vào của người dùng được sử dụng cho thao tác cần được thực hiện.
-
Tùy thuộc vào lựa chọn của người dùng, hoạt động được thực hiện.
-
Đầu ra có liên quan được hiển thị trên bảng điều khiển.