本文的主题是Tree，是算法中应用最广的方法之一。

1. binary tree二叉树

1.1 基本结构

Tree从一个root开始，延伸出枝条，术语通常叫做children。对于binary tree来说每一个node的children有两个。为了保持树状结果的一致性，考虑边界条件——root没有value的tree，设置这样的tree也有两个枝条，两个枝条都是值为None的树状结构。
tree class基本构成如下：

class tree:
    def __init__(self, value = None):
        self.value = value
        #value是每一个节点的值，如果只有一个节点，则这个节点是root
        self.left = None
        self.right = None
        #默认任何tree都有两个children，初始值为None

但是这样的class定义只满足边界条件，还需要增加tree的生长，更新如下：

class tree:
    def __init__(self, value = None):
        self.value = value
        if self.value is None:
            self.left = None
            self.right = None
        else:
            self.left = Tree()
            self.right = Tree()

1.2 应用--expression tree

之前的文章提到过计算机如何实现数学的混合运算，使用的是stack的方法，其核心是如何区分运算的优先级。除了stack前缀后缀的实现方法外，本文的tree也可以实现，因为tree也具有识别优先级的能力，任何一个node和两个children关系最紧密。
例如：3 * (2 + 4)，可以用树状图表示为：

   *
3    +
    2  4

使用上文提到的tree class来实现：

def evaluate(expression_tree):
    if expression_tree.value is None:
        return
    if isinstance(expression_tree.value, int):
        return expression_tree.value
    if expression_tree.value == '+':
        return evaluate(expression_tree.left) + evaluate(expression_tree.right)
    if expression_tree.value == '*':
        return evaluate(expression_tree.left) * evaluate(expression_tree.right)
#recursion的思想是很多算法的base，这里的base condition是value为None和value为一个int，recursion condition是value为运算符

1.3 Tree height

树的高度是解决很多复杂问题的基础，实现方法如下（与之前文章约定一样，为了避免冗余，上文实现的class function不再重复，直接继承）：

class tree:
    def height(self):
        if self.value is None:
            return 0
        #边界条件，如果一个树没有value，默认高度是0
        return max(self.left._height(), self.right._height())
        #非边界条件时，高度等于左右两个分支高度的最大值
    def _height(self):
        if self.value is None:
            return 0
        return 1 + max(self.left._height(), self.right._height())
        #还是使用recursion来解决问题

看起来在求解树高度的两个函数中，大量代码重复，有冗余的嫌疑，但实际上表达的含义截然不同。
在height的函数中处理的是tree为空和非空两种情况的问题，而_height函数中同样的判断代码却是recursion的base condition

1.4 Tree print

为了后续实现复杂功能做铺垫，先要实现数的可视化。之前简单的问题可以在脑中推导实现方案，但是复杂的问题要debug就一定要先能展现每一步的运行功能。
为了美观，每一个节点的两个children应该占据相同的排版空间。

class Tree:
    def print_tree(self):
        self._print_tree(0, self.height())
        #tree的print排版设计显然要与tree height相关，所以传参进入_print_tree实现具体print
    def _print_tree(self, depth, height):
        if self.value is not None:
            self.left._print_tree(depth + 1, height)
            print('    ' * depth,  self.value, sep ='')
            self.right._print_tree(depth + 1, height)
        else:
            print('\n' * (2 ** (height - depth + 1) - 1))

T = Tree(1)
T1 = Tree(0)
T2 = Tree(2)
T3 = Tree(3)
T4 = Tree(4)
T5 = Tree(5)
T6 = Tree(6)
T.left = T1
T.right = T2
T2.left = T3
T2.right = T4
T1.left = T5
T1.right = T6
T.print_tree()
>>>
        5

    0

        6

1

        3

    2

        4

为什么要用水平生长方式输出tree，而不是最容易被人接受的竖直生长方式？
水平生长的方式每一行都只有一个value或者是空行，可以容易的用recursion和print控制输出；而竖直生长的方式，每一行有多个value，不容易用recursion方式直接print出来。

1.5 Binary Search Tree(BST)

binary search tree的目的是为了提高检索效率，基本思路是输入一组乱序数字，第一个数字放在root中，第二个数字如果比第一个数字小则放在left child中，反之。
例如：一组数3，6，4，1，9，2，5

        3
   1          6
      2    4     9
             5

判断是否是BST的实现方法如下：

class Tree:
    def is_bst(self):
        if self.value is None:
            return True
        if self.left.value is not None:
            tree_on_left = self.left
            while tree_on_left.right.value is not None:
                tree_on_left = tree_on_left.right
            #找到左侧分支最右侧的点的值
            if self.value <= tree_on_left.value:
                return False
        if self.right.value is not None:
            tree_on_right = self.right
            while tree_on_right.left.value is not None:
                tree_on_right = tree_on_right.left
            #找到右侧分支最左侧的点的值
            if self.value >= tree_on_right.value:
                return False
        return self.left.is_bst() and self.right.is_bst()

可以判断BST后，下面的问题就是如何形成BST：

class Tree:
    def insert_in_bst(self, value):
        if self.value is None:
            self.value = value
            self.left = Tree()
            self.right = Tree()
            return True
            #如果BST为空，那么生成一个空tree，返回生成成功
        elif self.value is value:
            return False
            #如果插入的value是当前的value，则不需要插入值，返回失败
        if self.value > value:
            return self.left.insert_in_bst(value)
        return self.right.isnert_in_bst(value)
        #前面base condition设置完成后，这里写的是recursion condition，如果插入值小于当前value，则在左侧recursion，反之

1.6 BST delete

相对而言BST delete是Tree中最复杂的功能，基本思路是：
（1）如果删除的节点是leaf，则直接删除；
（2）如果该节点只有一个child，则把child的后续tree挂到当前child上；
（3）如果删除的节点有两个children，这是最复杂的情况。分析如下：要找一个节点来替代被删除的节点，要求这个替代的节点value比所有右侧的节点value都小，比所有左侧的节点value都大。马上联想到任意数组生成BST的过程，符合这样要求的节点是左侧分支最右下节点的value，所以用这个节点替换被删除的节点。然后处理左侧分支最右下节点左侧child的问题，它符合上面说的（2），把左侧的child直接挂在parent的位置即可。