Khi cần triển khai cây nhị thức (binomial tree) trong Python, dùng phương pháp hướng đối tượng. Định nghĩa class, thuộc tính. Định nghĩa hàm trong class thực hiện thao tác. Tạo instance, dùng hàm thực hiện phép toán.
Minh họa:
Ví dụ
class binomial_tree:
def __init__(self, key):
self.key = key
self.children = []
self.order = 0
def add_at_end(self, t):
self.children.append(t)
self.order += 1
my_tree = []
print('Menu')
print('create ')
print('combine ')
print('exit')
while True:
option = input('Bạn muốn làm gì? ').split()
operation = option[0].strip().lower()
if operation == 'create':
key = int(option[1])
b_tree = binomial_tree(key)
my_tree.append(b_tree)
print('Đã tạo cây nhị thức.')
elif operation == 'combine':
index_1 = int(option[1])
index_2 = int(option[2])
if my_tree[index_1].order == my_tree[index_2].order:
my_tree[index_1].add_at_end(my_tree[index_2])
del my_tree[index_2]
print('Đã gộp cây nhị thức.')
else:
print('Cần cùng order để gộp.')
elif operation == 'exit':
print("Thoát")
break
print('{:>8}{:>12}{:>8}'.format('Index', 'Root key', 'Order'))
for index, t in enumerate(my_tree):
print('{:8d}{:12d}{:8d}'.format(index, t.key, t.order))
Đầu ra
Menu createcombine exit Bạn muốn làm gì? create 7 Đã tạo cây nhị thức. Index Root key Order 0 7 0 Bạn muốn làm gì? create 11 Đã tạo cây nhị thức. Index Root key Order 0 7 0 1 11 0 Bạn muốn làm gì? create 4 Đã tạo cây nhị thức. Index Root key Order 0 7 0 1 11 0 2 4 0 Bạn muốn làm gì? combine 0 1 Đã gộp cây nhị thức. Index Root key Order 0 7 1 1 4 0 Bạn muốn làm gì? exit Thoát
Giải thích
- Định nghĩa class 'binomial_tree'.
- Có phương thức thêm phần tử vào cuối cây.
- Tạo list rỗng.
- Người dùng chọn tùy chọn.
- Nếu chọn tạo key, tạo instance class, tạo cây nhị thức.
- Tính index, root value, order.
- Nếu gộp index, chọn tùy chọn khác, nhập index cần gộp.
- Gộp dữ liệu, hiển thị.