Khi được yêu cầu hiển thị các nút của cây bằng cách sử dụng truyền tải tìm kiếm đầu tiên theo chiều rộng, một lớp sẽ được tạo và nó chứa các phương thức để đặt nút gốc, thêm các phần tử vào cây, tìm kiếm một phần tử cụ thể, thực hiện 'bfs' ( tìm kiếm đầu tiên theo chiều rộng) và như vậy. Một phiên bản của lớp có thể được tạo để truy cập và sử dụng các phương thức này.
Dưới đây là một minh chứng về điều tương tự -
Ví dụ
class Tree_struct:
def __init__(self, data=None):
self.key = data
self.children = []
def set_root(self, data):
self.key = data
def add_node(self, node):
self.children.append(node)
def search_node(self, key):
if self.key == key:
return self
for child in self.children:
temp = child.search_node(key)
if temp is not None:
return temp
return None
def bfs_operation(self):
queue = [self]
while queue != []:
popped = queue.pop(0)
for child in popped.children:
queue.append(child)
print(popped.key, end=' ')
my_instance = None
print('Menu (assume no duplicate keys)')
print('add <data> at root')
print('add <data> below <data>')
print('bfs')
print('quit')
while True:
my_input = input('What operation would you do ? ').split()
operation = my_input[0].strip().lower()
if operation == 'add':
data = int(my_input[1])
new_node = Tree_struct(data)
suboperation = my_input[2].strip().lower()
if suboperation == 'at':
my_instance = new_node
elif suboperation == 'below':
position = my_input[3].strip().lower()
key = int(position)
ref_node = None
if my_instance is not None:
ref_node = my_instance.search_node(key)
if ref_node is None:
print('No such key')
continue
ref_node.add_node(new_node)
elif operation == 'bfs':
if my_instance is None:
print('The tree is empty')
else:
print('Breadth First Search traversal is : ', end='')
my_instance.bfs_operation()
print()
elif operation == 'quit':
break Đầu ra
MenuMenu (assume no duplicate keys) add <data> at root add <data> below <data> bfs quit What operation would you do ? add 6 at root What operation would you do ? add 4 below 6 What operation would you do ? add 9 below 4 What operation would you do ? bfs Breadth First Search traversal is : 6 4 9 What operation would you do ? quit
Giải thích
-
Lớp 'Tree_struct' với các thuộc tính bắt buộc được tạo.
-
Nó có chức năng ‘init’ được sử dụng để tạo danh sách trống.
-
Phương thức ‘set_root’ được xác định để giúp đặt giá trị gốc của cây nhị phân.
-
Nó có một phương thức ‘add_node’ giúp thêm các phần tử vào 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ể.
-
Một phương thức có tên là ‘bfs_operation’ được xác định, 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.
-
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.