数据结构之二叉搜索树

二叉搜索树是一棵二叉树，且满足如下性质：设x是二叉树的一个节点，如果y是x左子树的一个节点，那么y.key<=x.key; 如果y是x右子树的一个节点，那么y.key>=x.key。

代码示例

class BiTreeNode():
    def __init__(self, data):
        self.data = data
        self.lchild = None
        self.rchild = None
        self.parent = None

class BST():
    def __init__(self, lst=None):
        if len(lst) > 0:
            self.root = BiTreeNode(lst[0])
            node = self.root
        for v in lst[1:]:
            node = self.insert(node, v)
    
    def insert(self, node, val):
        if not node:
            node = BiTreeNode(val)
            return node
        if node.data > val:
            node.lchild = self.insert(node.lchild, val)
            node.lchild.parent = node
        else:
            node.rchild = self.insert(node.rchild, val)
            node.rchild.parent = node
        return node

    def in_order(self, node):
        if node:
            self.in_order(node.lchild)
            print(node.data, end=',')
            self.in_order(node.rchild)

t = BST([1,5,3,4,2])

t.in_order(t.root)