Binary Tree Algorithm (in Python)

【实例简介】

**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
```