Khi được yêu cầu triển khai cấu trúc dữ liệu cây nhị phân sử dụng danh sách được liên kết, phương pháp đặt nút gốc, phương thức thực hiện duyệt theo thứ tự, chèn phần tử vào bên trái nút gốc, phương pháp chèn phần tử vào bên phải của nút gốc và một phương pháp để tìm kiếm các giá trị được xác định.
Dưới đây là một minh chứng cho điều tương tự -
Ví dụ
class BinaryTree_structure:
def __init__(self, key=None):
self.key = key
self.left = None
self.right = None
def set_root(self, key):
self.key = key
def in_order_traversal(self):
if self.left is not None:
self.left.in_order_traversal()
print(self.key, end=' ')
if self.right is not None:
self.right.in_order_traversal()
def insert_left(self, new_node):
self.left = new_node
def insert_right(self, new_node):
self.right = new_node
def search_val(self, key):
if self.key == key:
return self
if self.left is not None:
temp = self.left.search_val(key)
if temp is not None:
return temp
if self.right is not None:
temp = self.right.search_val(key)
return temp
return None
btree = 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('quit')
while True:
print('The inorder traversal of binary tree ', end='')
if btree is not None:
btree.in_order_traversal()
print()
do = input('What would you like to do? ').split()
operation = do[0].strip().lower()
if operation == 'insert':
data = int(do[1])
new_node = BinaryTree_structure(data)
sub_op = do[2].strip().lower()
if sub_op == 'at':
btree = new_node
else:
position = do[4].strip().lower()
key = int(position)
ref_node = None
if btree is not None:
ref_node = btree.search_val(key)
if ref_node is None:
print('No such key exists')
continue
if sub_op == 'left':
ref_node.insert_left(new_node)
elif sub_op == 'right':
ref_node.insert_right(new_node)
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> quit The inorder traversal of binary tree What would you like to do? insert 45 at root The inorder traversal of binary tree 45 What would you like to do? insert 78 left of 45 The inorder traversal of binary tree 78 45 What would you like to do? insert 90 right of 45 The inorder traversal of binary tree 78 45 90 What would you like to do? quit
Giải thích
-
Lớp 'BinaryTree_osystem' được tạo.
-
Nó có chức năng ‘set_root’ giúp đặt giá trị gốc cho Cây.
-
Một phương thức có tên ‘in_order_traversal’ được xác định, giúp duyệt qua cây theo thứ tự ‘Left-> Node-> Right’.
-
Một phương thức khác có tên là ‘insert_left’ được định nghĩa, giúp thêm một phần tử vào bên trái giá trị theroot.
-
Một phương thức khác có tên là ‘insert_right’ được xác định, giúp thêm một phần tử vào bên phải giá trị gốc.
-
Một phương thức khác có tên là ‘search_val’ được xác định, giúp xóa một giá trị khỏi đầu ngăn xếp và trả về giá trị đã xóa.
-
Bốn tùy chọn được đưa ra, chẳng hạn như "chèn tại gốc", "chèn vào bên trái của", "chèn vào bên phải của" và "thoát".
-
Dựa trên đầu vào / lựa chọn của người dùng, các hoạt động tương ứng được thực hiện.
-
Đầu ra này được hiển thị trên bảng điều khiển.