二叉排序树(BST)

二叉排序树

二叉排序树又称为二叉查找树(Binary Sort Tree or Binary Search Tree, 简称BST)，或者是一颗空树，或者是具有下列性质的二叉树：

1. 若它的左子树不为空，则左子树上所有的节点的值均小于它的根节点的值。
2. 若它的右子树不为空，则右子树上所有的节点的值均大于它的根节点的值。
3. 它的左、右子树也分别为二叉排序树。

如下例所示的二叉排序树：

根据上述定义的二叉排序树结构特点可见它的查找过程：当二叉排序树不为空时，首先将给定值和根节点的关键字比较，若相等，则查找成功，否则将依据给定值和根节点的关键字之间的大小关系，分别在左子树或右子树上继续进行查找。最后可见，二叉排序树的中序遍历结果即为从小到大的排序结果。

二叉排序树实现(python)

对给定的序列list=[51, 12, 34, 5, 54, 89, 25, 11, 45, 67, 31, 22, 99, 79]按顺序生成二叉排序树

二叉树的节点

二叉树的节点分为三个部分：左子树指针域，数据域，右子树指针域。如下图所示：

用python实现如下：

class Node:
    def __init__(self, v):
        """
        the node of tree
        :param v: the value of node
        """
        self.value = v
        self.left = None
        self.right = None

算法描述

生成一个二叉排序树的算法如下：

初始化：生成一个空树$Tree$，即根节点为空：$Tree.root=None$
输入：一个数据$v$
步骤：

1. 判断根节点$Tree.root$是否为空。若是，则生成根节点$Tree.root=Node(v)$，否则执行步骤2。
2. 另当前节点为$NowNode=Tree.root$。
3. 判断$v$与当前节点值$NowNode.value$的大小，如果$v>NowNode.value$，执行步骤4，否则执行步骤5.
4. 判断当前节点的右子树$NowNode.right$是否为空，如果$NowNode.right=None$，则生成新节点$NewNode(v)$，执行步骤6，否则另$NowNode=NowNode.right$，执行步骤3。
5. 判断当前节点的左子树$NowNode.left$是否为空，如果$NowNode.left=None$，则生成新节点$NewNode(v)$，执行步骤6，否则另$NowNode=NowNode.left$，执行步骤3。
6. 结束

算法实现

用python实现如下：

class BST:
    def __init__(self, seq=None):
        """
        :param seq: the optional parameter, to initialize the tree
        """
        self.root = None
        self.insert(seq)

    def insert(self, val_list):
        """
        insert value into the tree
        :param val_list: integer or list, the value waiting for inserting
        :return:
        """
        if isinstance(val_list, list):
            if self.root is None:
                self.root = Node(val_list.pop(0))
            for v in val_list:
                self.__ins(v)
        elif isinstance(val_list, int):
            self.__ins(val_list)

    def __ins(self, v):
        """
        insert a value into the tree
        :param v: interger
        :return:
        """
        new_node = Node(v)
        tmp = self.root
        while tmp:
            if v > tmp.value:
                if tmp.right:
                    tmp = tmp.right
                else:
                    tmp.right = new_node
                    break
            elif v < tmp.value:
                if tmp.left:
                    tmp = tmp.left
                else:
                    tmp.left = new_node
                    break

    def search(self, val):
        """
        find the specific value
        :param val:
        :return:
        """
        tmp = self.root
        while tmp:
            if val == tmp.value:
                print("查找成功^_^")
                break
            elif val > tmp.value:
                if tmp.right:
                    tmp = tmp.right
                else:
                    print("查找失败x_x")
                    break
            elif val < tmp.value:
                if tmp.left:
                    tmp = tmp.left
                else:
                    print("查找失败x_x")
                    break

    def pre_order(self, node):
        """
        preorder traversal
        :param node:
        :return:
        """
        if node is not None:
            print(node.value, end=' ')
            self.pre_order(node.left)
            self.pre_order(node.right)

    def in_order(self, node):
        """
        inorder traversal
        :param node:
        :return:
        """
        if node is not None:
            self.in_order(node.left)
            print(node.value, end=' ')
            self.in_order(node.right)

    def post_order(self, node):
        """
        postorder traversal
        :param node:
        :return:
        """
        if node is not None:
            self.post_order(node.left)
            self.post_order(node.right)
            print(node.value, end=' ')

其中还包括了二叉排序树的遍历算法。其中中序遍历的结果即为排序结果。

运行示例

使用前面的列表list生成二叉排序树。

if __name__ == "__main__":
    li = [51, 12, 34, 5, 54, 89, 25, 11, 45, 67, 31, 22, 99, 79]
    my_tree = BST(li)
    my_tree.in_order(my_tree.root)
    print('')
    my_tree.insert([23, 1])
    my_tree.in_order(my_tree.root)
    print('')
    my_tree.search(23)

输出：

5 11 12 22 25 31 34 45 51 54 67 79 89 99 
1 5 11 12 22 23 25 31 34 45 51 54 67 79 89 99 
查找成功^_^

生成的二叉排序树图示如下：