Khi bắt buộc phải thực hiện tìm kiếm theo chiều sâu trước tiên trên cây bằng cách sử dụng đệ quy, một lớp sẽ được xác định và các phương thức được định nghĩa trên đó giúp thực hiện tìm kiếm đầu tiên theo chiều rộng.
Dưới đây là một minh chứng cho đ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_at_left(self, new_node):
self.left = new_node
def insert_at_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(key)
if temp is not None:
return temp
if self.right is not None:
temp = self.right.search(key)
return temp
return None
def depth_first_search(self):
print('entering {}...'.format(self.key))
if self.left is not None:
self.left.depth_first_search()
print('at {}...'.format(self.key))
if self.right is not None:
self.right.depth_first_search()
print('leaving {}...'.format(self.key))
btree_instance = None
print('Menu (no duplicate keys)')
print('insert <data> at root')
print('insert <data> left of <data>')
print('insert <data> right of <data>')
print('dfs')
print('quit')
while True:
my_input = input('What would you like to do? ').split()
op = my_input[0].strip().lower()
if op == 'insert':
data = int(my_input[1])
new_node = BinaryTree_struct(data)
sub_op = my_input[2].strip().lower()
if sub_op == 'at':
btree_instance = new_node
else:
position = my_input[4].strip().lower()
key = int(position)
ref_node = None
if btree_instance is not None:
ref_node = btree_instance.search_elem(key)
if ref_node is None:
print('No such key.')
continue
if sub_op == 'left':
ref_node.insert_at_left(new_node)
elif sub_op == 'right':
ref_node.insert_at_right(new_node)
elif op == 'dfs':
print('depth-first search traversal:')
if btree_instance is not None:
btree_instance.depth_first_search()
print()
elif op == 'quit':
break Đầu ra
MenuMenu (no duplicate keys) insert <data> at root insert <data> left of <data> insert <data> right of <data> dfs quit What would you like to do? insert 5 at root What would you like to do? insert 6 left of 5 What would you like to do? insert 8 right of 5 What would you like to do? dfs depth-first search traversal: entering 5... entering 6... at 6... leaving 6... at 5... entering 8... at 8... leaving 8... leaving 5... What would you like to 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ó chức năng ‘init’ được sử dụng để gán các nút ‘left’ và ‘right’ cho ‘None’.
-
Một phương thức khác có tên là ‘set_root’ được định nghĩa để chỉ định gốc của cây.
-
Một phương thức khác có tên là ‘insert_at_left’ được định nghĩa để giúp thêm các nút vào bên trái của cây.
-
Một phương thức khác có tên là ‘insert_at_right’ được định nghĩa để giúp thêm các nút vào bên phải của cây.
-
Một phương pháp khác có tên là ‘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à 'depth_first_search' được xác định, giúp thực hiện tìm kiếm theo độ sâu đầu tiên trên cây nhị phân.
-
Một phiên bản của lớp được tạo và gán cho 'None'.
-
Một menu được đưa ra.
-
Đầ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.