資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學Python程式：查詢二叉搜尋樹中的最小和最大元素
當需要查詢二叉搜尋樹中的最小和最大元素時，會建立一個二叉樹類，並定義向樹中新增元素和搜尋特定節點的方法。建立一個類的例項，並與這些方法一起使用。
下面是相同的演示 -
示例
class BST_Node:
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 search_node(self, key):
if self.key > key:
if self.left is not None:
return self.left.search_node(key)
else:
return None
elif self.key < key:
if self.right is not None:
return self.right.search_node(key)
else:
return None
return self
class BSTree:
def __init__(self):
self.root = None
def add_elem(self, key):
new_node = BST_Node(key)
if self.root is None:
self.root = new_node
else:
self.root.insert_elem(new_node)
def search_node(self, key):
if self.root is not None:
return self.root.search_node(key)
def get_smallest_elem(self):
if self.root is not None:
current = self.root
while current.left is not None:
current = current.left
return current.key
def get_largest_elem(self):
if self.root is not None:
current = self.root
while current.right is not None:
current = current.right
return current.key
my_instance = BSTree()
print('Menu (Assume no duplicate keys)')
print('add ')
print('smallest')
print('largest')
print('quit')
while True:
my_input = input('What operation would you perform ? ').split()
operation = my_input[0].strip().lower()
if operation == 'add':
key = int(my_input[1])
my_instance.add_elem(key)
if operation == 'smallest':
smallest = my_instance.get_smallest_elem()
print('The smallest element is : {}'.format(smallest))
if operation == 'largest':
largest = my_instance.get_largest_elem()
print('The largest element is : {}'.format(largest))
elif operation == 'quit':
break輸出
Menu (Assume no duplicate keys) add <key> smallest largest quit What operation would you perform ? add 5 What operation would you perform ? add 8 What operation would you perform ? add 11 What operation would you perform ? add 0 What operation would you perform ? add 3 What operation would you perform ? smallest The smallest element is : 0 What operation would you perform ? largest The largest element is : 11 What operation would you perform ? quit’
解釋
建立具有所需屬性的“BST_Node”類。
它有一個“init”函式，用於將左、右和父節點設定為“None”。
它有一個“insert_element”方法，可以幫助將元素插入到二叉樹中。
另一個名為“search_node”的方法，用於在樹中搜索特定節點。
定義另一個名為“BSTree”的類，其中根節點設定為“None”。
定義了一個名為“add_elem”的方法，用於向樹中新增元素。
還有一個名為“search_node”的方法，可以幫助在樹中搜索特定節點。
定義另一個名為“get_smallest_node”的方法，可以幫助獲取樹中最小的節點。
定義另一個名為“get_largest_node”的方法，可以幫助獲取樹中最大的節點。
建立“BSTree”類的物件。
根據使用者選擇的運算，執行該運算。
更新於：2021年4月15日
300 次瀏覽
廣告