Khi được yêu cầu tìm nút thứ ‘bằng cách sử dụng trình duyệt inorder của cây nhị phân, 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, thêm phần tử vào trái hoặc phải, thực hiện theo thứ tự truyền tải, 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à một 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 inorder_nth(self, n):
return self.inorder_nth_helper_fun(n, [])
def inorder_nth_helper_fun(self, n, in_ord):
if self.left is not None:
temp = self.left.inorder_nth_helper_fun(n, in_ord)
if temp is not None:
return temp
in_ord.append(self)
if n == len(in_ord):
return self
if self.right is not None:
temp = self.right.inorder_nth_helper_fun(n, in_ord)
if temp is not None:
return temp
def insert_t0_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
btree_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('inorder ')
print('quit')
while True:
do = input('What would you like to do? ').split()
operation = do[0].strip().lower()
if operation == 'insert':
data = int(do[1])
new_node = BinaryTree_struct(data)
suboperation = do[2].strip().lower()
if suboperation == 'at':
btree_instance = new_node
else:
position = do[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 suboperation == 'left':
ref_node.insert_t0_left(new_node)
elif suboperation == 'right':
ref_node.insert_to_right(new_node)
elif operation == 'inorder':
if btree_instance is not None:
index = int(do[1].strip().lower())
node = btree_instance.inorder_nth(index)
if node is not None:
print('nth term of inorder traversal: {}'.format(node.key))
else:
print('The index exceeds maximum possible index.')
else:
print('The tree is empty...')
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> inorder 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? inorder 5 The index exceeds maximum possible index. What would you like to do? 6 6
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 để đặt các nút bên trái và bên phải thành 'Không có'.
-
Nó có phương thức ‘set_root’ giúp thiết lập gốc của cây nhị phân.
-
Một phương thức khác có tên là ‘inorder_nth’ thực hiện duyệt inorder bằng cách sử dụng đệ quy.
-
Do đó, nó có một chức năng trợ giúp được xác định cùng với.
-
Một phương thức khác có tên là ‘insert_to_right’ được định nghĩa để giúp thêm phần tử vào phía bên phải của nút gốc.
-
Một phương thức có tên ‘insert_to_left’ được xác định, giúp thêm phần tử vào bên trái của nút gốc.
-
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 đối tượng của lớp ‘BinaryTree_struct’ được tạo.
-
Đầ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.