Khi được yêu cầu xây dựng cây nhị phân bằng cách lấy đầu vào bằng cách sử dụng trình duyệt thứ tự hoặc sau, một lớp được xác định, có các phương thức để thiết lập phần tử gốc, thực hiện chuyển ngang cấp độ cao, thực hiện chuyển ngang thứ tự sau. Nó có thể được sử dụng bằng cách tạo một phiên bản của lớp.
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_traversal(self):
if self.left is not None:
self.left.inorder_traversal()
print(self.key, end=' ')
if self.right is not None:
self.right.inorder_traversal()
def post_order_traversal(self):
if self.left is not None:
self.left.post_order_traversal()
if self.right is not None:
self.right.post_order_traversal()
print(self.key, end=' ')
def construct_btree(post_ord, in_ord):
if post_ord == [] or in_ord == []:
return None
key = post_ord[-1]
node = BinaryTree_struct(key)
index = in_ord.index(key)
node.left = construct_btree(post_ord[:index], in_ord[:index])
node.right = construct_btree(post_ord[index:-1], in_ord[index + 1:])
return node
post_ord = input('The input for post-order traversal is : ').split()
post_ord = [int(x) for x in post_ord]
in_ord = input('The input for in-order traversal is : ').split()
in_ord = [int(x) for x in in_ord]
my_instance = construct_btree(post_ord, in_ord)
print('Binary tree has been constructed...')
print('Verification in process..')
print('Post-order traversal is... ', end='')
my_instance.post_order_traversal()
print()
print('In-order traversal is... ', end='')
my_instance.inorder_traversal()
print() Đầu ra
The input for post-order traversal is : 1 2 3 4 5 The input for in-order traversal is : 5 4 3 2 1 Binary tree has been constructed... Verification in process.. Post-order traversal is... 1 2 3 4 5 In-order traversal is... 5 4 3 2 1
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 ‘inorder_traversal’ thực hiện duyệt theo thứ tự, tức là Left → Node → Right.
-
Một phương thức khác có tên là ‘post_order_traversal’ được định nghĩa giúp duyệt qua cây theo thứ tự bài đăng, tức là Left → Right → Node.
-
Phương thức có tên ‘construct_btree’ được định nghĩa, giúp tạo cây nhị phân bằng cách sử dụng các phần tử đã được chỉ định trướ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.
-
Phương thức ‘construct_btree’ được sử dụng để tạo cây nhị phân bằng cách lấy các phần tử đã được chỉ định trước đó.
-
Việc duyệt qua thứ tự bài đăng và duyệt theo thứ tự được thực hiện trên cây này.
-
Đầu ra có liên quan được hiển thị trên bảng điều khiển.