Khi được yêu cầu sắp xếp cây tìm kiếm nhị phân, một lớp sẽ được tạo và các phương thức được định nghĩa bên trong nó để thực hiện các hoạt động như chèn một phần tử và thực hiện duyệt qua inorder.
Dưới đây là một minh chứng về điều tương tự -
Ví dụ
class BinSearchTreeNode:
def __init__(self, key):
self.key = key
self.left = None
self.right = None
self.parent = None
def insert_elem(self, node):
if self.key > node.key:
if self.left is None:
self.left = node
node.parent = self
else:
self.left.insert_elem(node)
elif self.key <= node.key:
if self.right is None:
self.right = node
node.parent = self
else:
self.right.insert_elem(node)
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()
class BinSearchTree:
def __init__(self):
self.root = None
def inorder_traversal(self):
if self.root is not None:
self.root.inorder_traversal()
def add_val(self, key):
new_node = BinSearchTreeNode(key)
if self.root is None:
self.root = new_node
else:
self.root.insert_elem(new_node)
my_instance = BinSearchTree()
my_list = input('Enter the list of numbers... ').split()
my_list = [int(x) for x in my_list]
for x in my_list:
my_instance.add_val(x)
print('Sorted list: ')
print(my_instance.inorder_traversal()) Đầu ra
Enter the list of numbers... 67 54 89 0 11 34 99 Sorted list: 0 11 34 54 67 89 99
Giải thích
-
Lớp 'BinSearchTreeNode' 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’, ‘right’ và ‘cha’ cho ‘None’.
-
Một phương thức khác có tên là ‘insert_elem’ đượ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à ‘inorder_traversal’ được định nghĩa, giúp thực hiện duyệt qua inorder trên cây.
-
Một lớp khác có tên là ‘BinSearchTree’ được xác định.
-
Nó đặt gốc thành ‘Không có.
-
Nó có một phương thức được đặt tên là ‘inorder_traversal’ giúp thực hiện duyệt qua inorder trên cây.
-
Một phương thức khác có tên là ‘add_val’ được định nghĩa để giúp thêm các nút vào cây.
-
Một bản sao của ‘BinSearchTree’ được tạo.
-
Danh sách các số do người dùng lấy.
-
Một cây được tạo ra bằng cách sử dụng cái này.
-
Danh sách được sắp xếp và thực hiện việc duyệt qua inorder.
-
Đầu ra có liên quan được hiển thị trên bảng điều khiển.