嘿，亲！知识可是无价之宝呢，但咱这精心整理的资料也耗费了不少心血呀。小小地破费一下，绝对物超所值哦！如有下载和支付问题，请联系我们QQ(微信同号)：813200300
本次赞助数额为： 3 元微信扫码支付：3 元
请留下您的邮箱，我们将在2小时内将文件发到您的邮箱
**Binary Tree Algorithm (in Python)**
简易二叉树算法，包含可视化打印，附三类顺序表达和额外查找方法。
最后一部分代码用以根据两种 data orders (inorder & preorder) 识别并创建Binary tree object.
```python
class BinaryTree:
def __init__(self, rootElement):
self.key = rootElement
self.left = None
self.right = None
def getLeft(self):
return self.left
def getRight(self):
return self.right
def getKey(self):
return self.key
def setKey(self, key):
self.key = key
def setLeft(self, left):
self.left = left
def setRight(self, right):
self.right = right
def insertLeft(self, newNode):
if self.left == None:
self.left = BinaryTree(newNode)
else:
t = BinaryTree(newNode)
t.left = self.left
self.left = t
def insertRight(self, newNode):
if self.right == None:
self.right = BinaryTree(newNode)
else:
t = BinaryTree(newNode)
t.right = self.right
self.right = t
def _strHelper(self):
"""Returns list of strings, total width of the tree, position of the middle node and the height"""
if self.getLeft() == None and self.getRight() == None:
row = '%s' % self.key
width = len(row)
middle = width // 2
height = 1
return [row], width, middle, height
keyStr = '%s' % self.key
keyStrLength = len(keyStr)
if self.getLeft() != None and self.getRight() == None:
leftRows, leftWidth, leftMiddle, leftHeight = self.getLeft()._strHelper()
firstRow = (leftMiddle 1) * ' ' (leftWidth - leftMiddle - 1) * '_' keyStr
secondRow = leftMiddle * ' ' '/' (leftWidth - leftMiddle - 1 keyStrLength) * ' '
shiftedRows = [row keyStrLength * ' ' for row in leftRows]
return [firstRow, secondRow] shiftedRows, leftWidth keyStrLength, leftWidth keyStrLength // 2, leftHeight 2
elif self.getLeft() == None and self.getRight() != None:
rightRows, rightWidth, rightMiddle, rightHeight = self.getRight()._strHelper()
firstRow = keyStr rightMiddle * '_' (rightWidth - rightMiddle) * ' '
secondRow = (keyStrLength rightMiddle) * ' ' '\\' (rightWidth - rightMiddle - 1) * ' '
shiftedRows = [keyStrLength * ' ' row for row in rightRows]
return [firstRow, secondRow] shiftedRows, rightWidth keyStrLength,keyStrLength // 2, rightHeight 2,
else:
leftRows, leftWidth, leftMiddle, leftHeight = self.getLeft()._strHelper()
rightRows, rightWidth, rightMiddle, rightHeight = self.getRight()._strHelper()
firstRow = (leftMiddle 1) * ' ' (leftWidth - leftMiddle - 1) * '_' keyStr rightMiddle * '_' (rightWidth - rightMiddle) * ' '
secondRow = leftMiddle * ' ' '/' (leftWidth - leftMiddle - 1 keyStrLength rightMiddle) * ' ' '\\' (rightWidth - rightMiddle - 1) * ' '
# append a few rows to fill in the blanks in the bottom, so that left and right lists are of the length
if leftHeight < rightHeight:
leftRows = [leftWidth * ' '] * (rightHeight - leftHeight)
else:
rightRows = [rightWidth * ' '] * (leftHeight - rightHeight)
pairedRows = zip(leftRows, rightRows)
rows = [firstRow, secondRow] [i keyStrLength * ' ' j for i, j in pairedRows]
return rows, leftWidth rightWidth keyStrLength, leftWidth keyStrLength // 2, max(leftHeight, rightHeight) 2
def __str__(self):
rows, _, _, _ = self._strHelper()
result = ''
for row in rows:
result = row "\n"
return result
# Data Orders:
def preorder(tree):
"""
print the value of a tree in a Preorder manner
Parameters:
- tree (a BinaryTree object)
Returns: None
"""
if tree is not None:
print(tree.getKey())
preorder(tree.getLeft())
preorder(tree.getRight())
def inorder(tree):
"""
print the value of a tree in an Inorder manner
Parameters:
- tree (a BinaryTree object)
Returns: None
"""
if tree is not None:
inorder(tree.getLeft())
print(tree.getKey())
inorder(tree.getRight())
def postorder(tree):
"""
print the value of a tree in a postorder manner
Parameters:
- tree (a BinaryTree object)
Returns: None
"""
if tree is not None:
postorder(tree.getLeft())
postorder(tree.getRight())
print(tree.getKey())
# Extra Operations:
def findMinKey(tree):
"""
find the minimum element in the tree
Parameters:
- tree (a BinaryTree object)
Returns: None if tree is None, otherwise a number
"""
if tree is not None:
value_key = tree.getKey()
Min = value_key
if tree.getLeft() is not None:
value_Left = findMinKey(tree.getLeft())
if value_Left < Min:
Min = value_Left
if tree.getRight() is not None:
value_right = findMinKey(tree.getRight())
if value_right < Min:
Min = value_right
return Min
def findMaxKey(tree):
"""
find the maximum element in the tree
Parameters:
- tree (a BinaryTree object)
Returns: None if tree is None, otherwise a number
"""
if tree is not None:
value_key = tree.getKey()
Max = value_key
if tree.getLeft() is not None:
value_Left = findMaxKey(tree.getLeft())
if value_Left > Max:
Max = value_Left
if tree.getRight() is not None:
value_right = findMaxKey(tree.getRight())
if value_right > Max:
Max = value_right
return Max
# Building Trees based on inorder and preorder sequences:
def buildTree(inOrder, preOrder):
"""
Build a binary tree based on given Inorder and PreOrder traversals
Parameters:
- inOrder,preOrder (list of numbers)
Returns: a BinaryTree object
"""
if len(preOrder) > 0:
rootValue = preOrder[0]
tree = BinaryTree(rootValue)
index = inOrder.index(rootValue)
inOrder_left = inOrder[:index]
inOrder_right = inOrder[index 1:]
partialLength = len(inOrder_left)
preOrder_left = preOrder[1:partialLength 1]
preOrder_right = preOrder[partialLength 1:]
tree.left = buildTree(inOrder_left, preOrder_left)
tree.right = buildTree(inOrder_right, preOrder_right)
return tree
else:
return None
```