今天我们要介绍的是一种特殊的二叉树——二叉搜索树，同时我们也会讲到一种排序算法——二叉树排序算法。这两者之间有什么联系呢，我们一起来看一下吧。
开始之前呢，我们先来介绍一下如何创建一颗二叉搜索树。
假设我们有这样一些数据：[9,5,2,1,4,2,1,41,22,11,35,24,11,10,4,23,9,45,2,35,12,35,16,27,56,31,73]
我们就用这些数据来创建二叉排序树。
首先，我们将第一个数据9作为二叉排序树的根节点，
然后我们拿到第二个数据5，现在我们要进行判断，如果5比9小，那么就将5插入到节点9的左子树；如果5比9大的话，就把5插入到9的右子树。经过判断，我们将5插入到9的右左子树，因为9的左节点为空，所以我们直接将5作为9的左节点。
接下来判断第三个数据2，我们同样先将2和9进行判断，将2插入到9的左子树，但是9的左节点不为空，所以我们再将2与9的左节点5进行判断。2比5小，并且5的左节点为空，所以将2作为5的左节点。
以此类推，我们就可以画出一颗二叉搜索树，感兴趣的同学不妨亲自画一下。
那二叉树排序有是怎么回事呢？
我们回过头来看我们刚刚创建好的二叉树，前面我们已经介绍过了二叉树的前序、中序、后序遍历。我们不妨来尝试一下二叉搜索树的三序遍历。
如果对二叉树进行三序遍历的话，你就会发现，二叉搜索的中序遍历结果恰好就是从小到大排列的。
那我们就明白了，创建二叉搜索树并进行中序遍历就可以实现排序。
接下来照例我们用代码实现二叉搜索树和二叉树排序：
#-*- coding: utf-8 -*- class BinaryTree: def __init__(self, data): self.left = None self.right = None if type(data) == list: self.data = data[0] for d in data[1:]: self.insert(d) else: self.data = data def insert(self, data): bt = self while True: if data <= bt.data: if bt.left == None: bt.left = BinaryTree(data) break else: bt = bt.left else: if bt.right == None: bt.right = BinaryTree(data) break else: bt = bt.right def mid_order(self): result = [] stack = [] node = self while node or stack: while node: stack.append(node) node = node.left node = stack.pop() result.append(node.data) node = node.right return result上面呢，我们定义了一个二叉树类，并实现了节点的插入和中序遍历方法。在它的构造方法中，如果输入的参数是一个列表，那么我们就根据列表创建二叉搜索树，如果是一个值那么就之创建一个根节点。
下面我们就来创建一下二叉搜索树：
data = [9,5,2,1,4,2,1,41,22,11,35,24,11,10,4,23,9,45,2,35,12,35,16,27,56,31,73] bt = BinaryTree(data) mid = bt.mid_order() print(mid)执行一下，输出的结果是这样的
[1, 1, 2, 2, 2, 4, 4, 5, 9, 9, 10, 11, 11, 12, 16, 22, 23, 24, 27, 31, 35, 35, 35, 41, 45, 56, 73]你学会了吗？