Khi được yêu cầu xây dựng một cây nhị phân và thực hiện các hoạt động như chèn một phần tử, xóa một phần tử và hiển thị các phần tử của cây, một lớp được định nghĩa với các phương thức trong đó. Một thể hiện của lớp được định nghĩa và nó được sử dụng để truy cập các phần tử và thực hiện các hoạt động.
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, parent=None):
self.key = data
self.children = []
self.parent = parent
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 remove_node(self):
parent = self.parent
index = parent.children.index(self)
parent.children.remove(self)
for child in reversed(self.children):
parent.children.insert(index, child)
child.parent = parent
def bfs(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 (this assumes no duplicate keys)')
print('add <data> at root')
print('add <data> below <data>')
print('remove <data>')
print('display')
print('quit')
while True:
do = input('What would you like to do? ').split()
operation = do[0].strip().lower()
if operation == 'add':
data = int(do[1])
new_node = Tree_struct(data)
suboperation = do[2].strip().lower()
if suboperation == 'at':
my_instance = new_node
elif suboperation == 'below':
position = do[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
new_node.parent = ref_node
ref_node.add_node(new_node)
elif operation == 'remove':
data = int(do[1])
to_remove = my_instance.search_node(data)
if my_instance == to_remove:
if my_instance.children == []:
my_instance = None
else:
leaf = my_instance.children[0]
while leaf.children != []:
leaf = leaf.children[0]
leaf.parent.children.remove_node(leaf)
leaf.parent = None
leaf.children = my_instance.children
my_instance = leaf
else:
to_remove.remove_node()
elif operation == 'display':
if my_instance is not None:
print('Breadth First Search traversal is : ', end='')
my_instance.bfs()
print()
else:
print('The tree is empty')
elif operation == 'quit':
break Đầu ra
MenuMenu (this assumes no duplicate keys) add <data> at root add <data> below <data> remove <data> display quit What would you like to do? add 5 at root What would you like to do? add 6 below 5 What would you like to do? add 8 below 6 What would you like to do? remove 8 What would you like to do? display Breadth First Search traversal is : 5 6 What would you like to 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.
-
Một phương thức khác có tên là ‘set_root’ được xác định để chỉ định gốc của cây.
-
Một phương thức khác có tên là ‘add_node’ được định nghĩa để giúp thêm các nút vào cây.
-
Một phương thức khác có tên là ‘search_node’ được xác định để giúp tìm kiếm một phần tử cụ thể.
-
Phương thức có tên ‘remove_node’ được xác định, phương thức này sẽ xóa các phần tử khỏi cây.
-
Một phương thức khác có tên là ‘bfs’ được xác định, giúp thực hiện 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.