二叉查找🌲python版

# coding: utf-8
"""
array to bst
"""


class BSTNode(object):
    """BST 维护的节点结构"""
    def __init__(self, key, lnode=None, rnode=None):
        self.key = key       # 节点值
        self.left = lnode    # 左节点
        self.right = rnode   # 右节点


def array_to_bst(a, start, end):
    """
    from array to bst
    中序构造
    """
    middle = start + (end - start)/2
    broot = BSTNode(a[middle])
    if start != middle:
        lroot = array_to_bst(a, start, middle-1)
        broot.left = lroot
    else: broot.left = None
    if middle != end:
        rroot = array_to_bst(a, middle+1, end)
        broot.right = rroot
    else: broot.right = None
    return broot


class BSTree(object):

    def __init__(self, root):
        self.root = root      # 根节点
        self.show_array = []  # bst to array

    def order(self, root):
        """
        根据BST的根节点进行前序遍历
        """
        if root != None:
            self.show_array.append(root.key)    # 添加根节点
            self.order(root.left)               # 遍历左节点
            self.order(root.right)              # 遍历右节点
        return self.show_array

    def show(self, root):
        """
        输出BST的树结构
        """
        pass

    def __repr__(self):
        return "<BST %r>" % self.order(self.root)


if __name__ == '__main__':
    array = [12, 14, 16, 18, 20, 34, 56, 78, 100]
    print array
    bst = BSTree(array_to_bst(array, 0, 8))
    print bst