เมื่อจำเป็นต้องใช้โครงสร้างข้อมูลไบนารีทรีโดยใช้รายการที่เชื่อมโยง วิธีการตั้งค่าโหนดรูท วิธีดำเนินการข้ามลำดับ การแทรกองค์ประกอบทางด้านซ้ายของโหนดราก วิธีการแทรกองค์ประกอบ ทางด้านขวาของรูทโหนด และวิธีการค้นหาค่าถูกกำหนดไว้
ด้านล่างนี้เป็นการสาธิตสำหรับสิ่งเดียวกัน -
ตัวอย่าง
class BinaryTree_structure:
def __init__(self, key=None):
self.key = key
self.left = None
self.right = None
def set_root(self, key):
self.key = key
def in_order_traversal(self):
if self.left is not None:
self.left.in_order_traversal()
print(self.key, end=' ')
if self.right is not None:
self.right.in_order_traversal()
def insert_left(self, new_node):
self.left = new_node
def insert_right(self, new_node):
self.right = new_node
def search_val(self, key):
if self.key == key:
return self
if self.left is not None:
temp = self.left.search_val(key)
if temp is not None:
return temp
if self.right is not None:
temp = self.right.search_val(key)
return temp
return None
btree = 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('quit')
while True:
print('The inorder traversal of binary tree ', end='')
if btree is not None:
btree.in_order_traversal()
print()
do = input('What would you like to do? ').split()
operation = do[0].strip().lower()
if operation == 'insert':
data = int(do[1])
new_node = BinaryTree_structure(data)
sub_op = do[2].strip().lower()
if sub_op == 'at':
btree = new_node
else:
position = do[4].strip().lower()
key = int(position)
ref_node = None
if btree is not None:
ref_node = btree.search_val(key)
if ref_node is None:
print('No such key exists')
continue
if sub_op == 'left':
ref_node.insert_left(new_node)
elif sub_op == 'right':
ref_node.insert_right(new_node)
elif operation == 'quit':
break ผลลัพธ์
Menu (this assumes no duplicate keys) insert <data> at root insert <data> left of <data> insert <data> right of <data> quit The inorder traversal of binary tree What would you like to do? insert 45 at root The inorder traversal of binary tree 45 What would you like to do? insert 78 left of 45 The inorder traversal of binary tree 78 45 What would you like to do? insert 90 right of 45 The inorder traversal of binary tree 78 45 90 What would you like to do? quit
คำอธิบาย
-
สร้างคลาส "BinaryTree_structure" แล้ว
-
มีฟังก์ชัน 'set_root' ที่ช่วยตั้งค่ารูทสำหรับต้นไม้
-
มีการกำหนดวิธีการที่ชื่อ 'in_order_traversal' ซึ่งช่วยในการสำรวจต้นไม้ในลำดับ 'Left->Node->Right'
-
มีการกำหนดวิธีการอื่นที่ชื่อว่า 'insert_left' ซึ่งช่วยเพิ่มองค์ประกอบทางด้านซ้ายของค่าราก
-
มีการกำหนดวิธีการอื่นที่เรียกว่า "insert_right" ซึ่งช่วยเพิ่มองค์ประกอบทางด้านขวาของค่าราก
-
มีการกำหนดวิธีการอื่นที่เรียกว่า 'search_val' ซึ่งช่วยลบค่าออกจากด้านบนของสแต็กและส่งกลับค่าที่ถูกลบ
-
มีสี่ตัวเลือกให้เลือก เช่น 'insert at root', 'insert to left of', 'insert to right of' และ 'quit'
-
ขึ้นอยู่กับอินพุต/ตัวเลือกโดยผู้ใช้ การดำเนินการตามลำดับจะถูกดำเนินการ
-
เอาต์พุตนี้จะแสดงบนคอนโซล
