二叉树其实直观理解起来还算比较简单，它是一个树结构，也就是层级结构，每一层每一个父节点最多有两个子节点。二叉树用来搜索效果不错，因为只要保证左节点比父节点小，右节点比父节点大，那么搜索下来时间复杂度其实就是很理想的O(logn)。

但是对于一个python新手来说，二叉树也是比较难实现的，因为按理说树结构其实应该是一种“链表”，但是python里面似乎可能好像没有这种结构，Java是有的（有人开始骂python是一门很low的语言了）……所以一开始我理解起来还很困难！这个怎么能把树上的每个节点串起来啊，怎么表示关系啊，然后我去刷stackoverflow，还真的慢慢地理解了它（的基础）。

1. 建立节点

如上文所述，二叉树的结构就是每一个父节点都有不超过两个子节点。那么对于二叉树的每个点建一个类，这个类中规定三个属性：节点自身的值value，节点的左子节点值left，节点的右子节点值right。对于每一个点而言，在初始化的时候都把一个值赋给它自己，同时左右子节点置为空。这个很好理解吧？叶子节点的左右子节点就会一直为空了，但是

代码：

class TreeNode(object):
    def __init__(self,value):
        self.value = value
        self.left = None
        self.right = None

2. 建立搜索树

现在我们有了点，看起来很简单，但是该怎么把树建起来呢？

二叉树建树其实就像上面说的，是一个很简单明确的过程，首先需要一个根节点，然后每一次新的节点过来，就跟根节点比较，比它小就作为左子节点，比它大就作为右子节点，然后依次跟下一层比较，直到自己成为叶子节点停止。

算法的要点是利用递归算法 recursion，说实话靠我自己想可能还是太难太抽象了点。但是如果你要去领会它的意思，做得也就是这件事：

class BinaryTree(object):
    def insert(self,root,value):
        if root is None:
            return value
        if value.value < root.value:
            root.left = self.insert(root.left,value)
        else:
            root.right = self.insert(root.right, value)
        return root

我们定义了一个新的类 二叉树，这个类里面只有一个insert方法，就是插入一个新的数据到已生成的树中。这个方法的记忆点有两块：

1.输入参数：

此处的参数应该是已生成的树节点，和准备加入的新节点，这两者的类型都需要是刚刚定义的带有左右子节点属性的类；

2.递归，采用三个条件判断：

如果当前节点为空就返回新的节点；如果当前节点不为空且比新的节点值大，那么就递归地判断当前节点的左子节点和新节点的关系，直到当前节点为空；比新的节点小就递归地判断当前节点的左子节点和新节点的关系，直到当前节点为空返回。

3. 生成二叉搜索树：

那么下面我们就用一个循环语句来生成一棵二叉搜索树吧。

root = Node(5)
tree = BinaryTree()

for i in [2,11,7,3,9,8,4,6,1]:
    tree.insert(root,Node(i))

现在基本上大功告成了！当你兴奋地敲下run之后，当当当当——

程序运行完，啥也没显示，就完了。

那是因为我们没有把树“遍历”地展示出来，python有一个二叉树库 binarytree，可以用pip安装，允许你打印出树的结构,可以用非常直观的方式来构建二叉树，看看人家的示例：

>>> from binarytree import Node
>>> root = Node(3)
>>> root.left = Node(2)
>>> root.right = Node(7)
>>> root.left.left = Node(4)
>>> root.left.right = Node(1)
>>> print(root)

    __3
   /   \
  2     7
 / \
4   1

4. 二叉树的三种遍历算法及排序

当我们已经有一个二叉树的时候，有哪几种方式来遍历它呢？

这是一个面试常见考点，相信很多小伙伴脑子里已经蹦出了答案：前序遍历，中序遍历，后序遍历

那么哪种遍历方法可以使二叉树输出有序呢？

中序遍历

在说到二叉树遍历的前序，中序和后序的时候，需要牢牢记住，这里的前，中，后的顺序，都是相对于节点本身而言的。所以“前序遍历”实际上的意思是：把遍历我这个父节点先放到前面，然后再左子节点，然后再右子节点，一直要保证这个顺序。中序遍历就是把遍历父节点放在中间去进行，先左子节点，然后再右子节点，子节点的遍历需要注意的是这个过程也是递归的。后序遍历呢，就是先左子节点，然后右子节点，最后再遍历父节点。

所以，自然，由于二叉树本身生成的时候的特性，再遍历的时候如果采用中序，就能够保证整个输出是从小到大有序的了。

所以我们定义三个新的函数来表示这三种遍历方法：

# 前序遍历
def pre_order_print(node):
    # self -- left -- right
    print(node.value,end=' ')
    if node.left:
        pre_order_print(node.left)
    if node.right:
        pre_order_print(node.right)
# 中序遍历     
def mid_order_print(node):
    # left --self -- right
    if node.left:
        mid_order_print(node.left)
    print(node.value,end=' ')
    if node.right:
        mid_order_print(node.right)
# 后序遍历     
def after_order_print(node):
    # left-- right--self
    if node.left:
        after_order_print(node.left)
    if node.right:
        after_order_print(node.right)
    print(node.value, end=' ')

5. 完整的程序

class Node(object):
    def __init__(self,value):
        self.value = value
        self.left = None
        self.right = None

class BinaryTree(object):
    def insert(self,root,value):
        if root is None:
            return value
        if value.value < root.value:
            root.left = self.insert(root.left,value)
        else:
            root.right = self.insert(root.right, value)

        return root

def pre_order_print(node):
    # self -- left -- right
    print(node.value,end=' ')
    if node.left:
        pre_order_print(node.left)
    if node.right:
        pre_order_print(node.right)
        
def mid_order_print(node):
    # mid --self -- right
    if node.left:
        mid_order_print(node.left)
    print(node.value,end=' ')
    if node.right:
        mid_order_print(node.right)

def after_order_print(node):
    # left-- right--self
    if node.left:
        after_order_print(node.left)
    if node.right:
        after_order_print(node.right)
    print(node.value, end=' ')

root = Node(5)

tree = BinaryTree()

for i in [2,11,7,3,9,8,4,6,1]:
    tree.insert(root,Node(i))
mid_order_print(root)

这样输出的结果就是有序的了。