資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究Python程式：基於中序或後序遍歷構建二叉樹
當需要透過輸入中序或後序遍歷來構建二叉樹時，我們會定義一個類，該類包含設定根元素、執行中序遍歷和執行後序遍歷的方法。可以透過建立類的例項來使用它。
下面是相同內容的演示 -
示例
class BinaryTree_struct:
def __init__(self, key=None):
self.key = key
self.left = None
self.right = None
def set_root(self, key):
self.key = key
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()
def post_order_traversal(self):
if self.left is not None:
self.left.post_order_traversal()
if self.right is not None:
self.right.post_order_traversal()
print(self.key, end=' ')
def construct_btree(post_ord, in_ord):
if post_ord == [] or in_ord == []:
return None
key = post_ord[-1]
node = BinaryTree_struct(key)
index = in_ord.index(key)
node.left = construct_btree(post_ord[:index], in_ord[:index])
node.right = construct_btree(post_ord[index:-1], in_ord[index + 1:])
return node
post_ord = input('The input for post-order traversal is : ').split()
post_ord = [int(x) for x in post_ord]
in_ord = input('The input for in-order traversal is : ').split()
in_ord = [int(x) for x in in_ord]
my_instance = construct_btree(post_ord, in_ord)
print('Binary tree has been constructed...')
print('Verification in process..')
print('Post-order traversal is... ', end='')
my_instance.post_order_traversal()
print()
print('In-order traversal is... ', end='')
my_instance.inorder_traversal()
print()輸出
The input for post-order traversal is : 1 2 3 4 5 The input for in-order traversal is : 5 4 3 2 1 Binary tree has been constructed... Verification in process.. Post-order traversal is... 1 2 3 4 5 In-order traversal is... 5 4 3 2 1
解釋
建立具有所需屬性的“BinaryTree_struct”類。
它有一個“init”函式，用於將左右節點設定為“None”。
它有一個“set_root”方法，用於設定二叉樹的根。
另一個名為“inorder_traversal”的方法執行中序遍歷，即左→節點→右。
定義了另一個名為“post_order_traversal”的方法，用於以後序方式遍歷樹，即左→右→節點。
定義了一個名為“construct_btree”的方法，用於使用之前指定的元素構建二叉樹。
定義了一個名為“search_elem”的方法，用於搜尋特定元素。
建立“BinaryTree_struct”類的物件。
使用“construct_btree”方法透過之前指定的元素構建二叉樹。
對該樹執行後序遍歷和中序遍歷。
在控制檯上顯示相關的輸出。
更新於: 2021年4月15日
356 次檢視
廣告