Khi cần tạo danh sách liên kết kép từ cây bậc ba, lớp ‘Node’ cần được tạo. Trong lớp này, có hai thuộc tính, dữ liệu có trong nút và quyền truy cập vào nút tiếp theo của danh sách được liên kết.
Một lớp ‘linked_list’ khác cần được tạo sẽ có chức năng khởi tạo và phần đầu của nút sẽ được khởi tạo thành ‘Không có’.
Trong một danh sách được liên kết kép, các nút có các con trỏ. Nút hiện tại sẽ có một con trỏ đến nút tiếp theo cũng như nút trước đó. Giá trị cuối cùng trong danh sách sẽ có giá trị ‘NULL’ trong con trỏ tiếp theo. Nó có thể được đi ngang theo cả hai hướng.
Người dùng xác định nhiều phương thức để chuyển đổi danh sách liên kết kép đã cho thành cây bậc ba và in các giá trị nút.
Dưới đây là một minh chứng cho điều tương tự -
Ví dụ
Nútclass Node:
def __init__(self, my_data):
self.right = None
self.data = my_data
self.left = None
self.mid = None
class ternary_tree_to_list:
def __init__(self):
self.root = None
self.head = None
self.tail = None
def convert_ternary_tree_to_list(self, node_val):
if node_val is None:
return
left = node_val.left;
mid = node_val.mid;
right = node_val.right;
if (self.head == None) :
self.head = self.tail = node_val
node_val.middle = None
self.head.left = None
self.head.right = None
else:
self.tail.right = node_val
node_val.left = self.tail
node_val.mid = None
self.tail = node_val
self.tail.right = None
self.convert_ternary_tree_to_list(left)
self.convert_ternary_tree_to_list(mid)
self.convert_ternary_tree_to_list(right)
def print_it(self):
curr = self.head
if (self.head == None):
print("The list is empty")
return
print("The nodes are :")
while curr != None:
print(curr.data)
curr = curr.right
my_instance = ternary_tree_to_list()
print("Elements are being added to the list")
my_instance.root = Node(10)
my_instance.root.left = Node(14)
my_instance.root.mid = Node(24)
my_instance.root.right = Node(17)
my_instance.root.left.left = Node(22)
my_instance.root.left.mid = Node(23)
my_instance.root.mid.left = Node(24)
my_instance.root.mid.mid = Node(28)
my_instance.root.mid.right = Node(30)
my_instance.root.right.left = Node(45)
my_instance.root.right.mid = Node(50)
my_instance.root.right.right = Node(80)
my_instance.convert_ternary_tree_to_list(my_instance.root)
my_instance.print_it() Đầu ra
Elements are being added to the list The nodes are : 10 14 22 23 24 24 28 30 17 45 50 80
Giải thích
- Lớp 'Node' đã được tạo.
- Một lớp khác với các thuộc tính bắt buộc được tạo.
- Một phương thức khác có tên 'convert_ternary_tree_to_list' được xác định, được sử dụng để chuyển đổi danh sách được liên kết kép đã cho thành cây bậc ba.
- Một phương thức khác có tên là 'print_it' được xác định, phương thức này sẽ hiển thị các nút của danh sách liên kết vòng tròn.
- Một đối tượng của lớp ‘ternary_tree_to_list’ được tạo và các phương thức được gọi trên nó để chuyển đổi danh sách được liên kết kép thành cây bậc ba.
- Một phương thức 'init' được xác định, rằng các nút gốc, đầu và cuối của danh sách được liên kết kép thành Không.
- Phương thức 'convert_ternary_tree_to_list' được gọi.
- Nó lặp lại qua danh sách được liên kết kép và chuyển nó thành cây bậc ba.
- Điều này được hiển thị trên bảng điều khiển bằng phương thức "print_it".