插入排序：通过构建有序序列，对于未排序数据，在已排序序列职工从后向前扫描，找到相应位置并插入。
插入排序在实现上，在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。

def insert_sort(alist):
    # 插入排序
    n = len(alist)
    for j in range(1, n):
        i = j
        while i > 0:
            if alist[i] < alist[i-1]:
                alist[i], alist[i-1] = alist[i-1], alist[i]
                i -= 1
            else:
                break

二分查找又称折半查找：首先假设表中元素是按升序排列，将表中间位置记录的关键字与查找关键字比较，
如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个字表，如果中间位置记录的关键字
大于查找关键字，则进一步查找前一字表，否则进一步查找后一子表。重复上述过程，知道找到满足条件的
记录，使查找成功，或直到字表不存在为止，此时查找不成功。

def binaty_search(alist, item):
    # 二分查找 递归
    n = len(alist)
    if n > 0:
        mid = n//2
        if alist[mid] == item:
            return
        elif item < alist[mid]:
            return binaty_search(alist[:mid], item)
        else:
            return binaty_search(alist[mid+1: ], item)
    return False

def binaty_search_2(alist, item):
    # 二分查找，非递归
    n = len(alist)
    first = 0
    last = n-1
    while first <= last:
        mid = (first + last)//2
        if alist[mid] == item:
            return True
        elif item < alist[mid]:
            last = mid -1
        else:
            first = mid + 1

    return False

归并排序：采用分治法，思想先递归分解数组，再合并数组。将数组分解最小之后，然后合并两个有序数组，
基本思路是比较两个数组的最前面的数，谁小就先取谁，取了后相应指针往后移一位。然后再比较，直至一个数组为空，
最后把另外一个数组的剩余部分复制过来即可。

def merge_sort(alist):
    # 归并排序
    n = len(alist)
    if n <= 1:
        return alist
    mid = n // 2
    left_li = merge_sort(alist[:mid])
    right_li = merge_sort(alist[mid: ])

    # 将两个有序的子序列合并为一个新的整体
    left_pointer, right_pointer = 0, 0
    result = []
    while left_pointer < len(left_li) and right_pointer < len(right_li):
        if left_li[left_pointer] < right_li[right_pointer]:
            result.append(left_li[left_pointer])
            left_pointer += 1
        else:
            result.append(right_li[right_pointer])
            right_pointer += 1
    result += left_li[left_pointer:]
    result += right_li[right_pointer:]
    return result

快速排序，又称划分交换排序，通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，
然后再按此方法对这两部分数据进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

步骤为：
1.从数列中挑出一个元素，称为“基准”；
2.重新排序数列，所有元素比基准值小的摆放在基准值前，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。
  在这个分区结束之后，该基准就处于数列的中间位置。这个称为分区操作。
3.递归地把小于基准值元素的子数列和大于基准值元素的子数列排序。

def quick_sort(alist, first, last):
    # 快速排序
    mid_value = alist[first]
    low = first
    high = last
    while low < high:
        # high左移
        while low < high and alist[high] >= mid_value:
            high -= 1
        alist[low] = alist[high]

        while low < high and alist[low] < mid_value:
            low += 1
        alist[high] = alist[low]
    alist[low] = mid_value
    quick_sort(alist, first, low-1)
    quick_sort(alist, low+1, last)

冒泡排序：
1.比较相邻的元素，如果第一个比第二个大（升序），就交换他们两个。
2.对每一对相邻元素作同样的工作，从开始第一对到结尾最后一对。这步做完后，最后的元素会是最大的数。
3.针对所有的元素重复以上步骤，除了最后一个。
4.持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

def bubble_sort(alist):
    # 冒泡排序
    n = len(alist)
    for j in range(n-1):
        count = 0
        for i in range(0, n-1-j):
            if alist[i] > alist[i+1]:
                alist[i], alist[i+1] = alist[i+1], alist[i]
                count += 1
        if count == 0:
            return

希尔排序又称缩小增量排序，是一种非稳定排序算法。希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序。
随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。

def shell_sort(alist):
    # 希尔排序
    n = len(alist)
    gap = n // 2
    while gap > 0:
        # 希尔排序与普通的插入排序算法的区别就是gap步长
        for j in range(gap, n):
            i = j
            while i > 0:
                if alist[i] < alist[i-gap]:
                    alist[i], alist[i-gap] = alist[i-gap], alist[i]
                    i -= gap
                else:
                    break
        gap //= 2

选择排序：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，
然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

def select_sort(alist):
    # 选择排序
    n = len(alist)
    for j in range(n-1):
        min_index = j
        for i in range(j+1, n):
            if alist[min_index] > alist[i]:
                min_index = i
        alist[j], alist[min_index] = alist[min_index], alist[j]

树的特点：
1.每个节点有零个或多个子节点；
2.没有父节点的节点称为根节点；
3.每一个非根节点有且只有一个父节点；
4.除根节点外，每个子节点可以分为多个不相交的子树

节点的度：一个节点含有的子树的个数称为该节点的度。
树的度：一棵树中，最大的节点的度称为树的度。
叶节点或者终端节点：度为零的节点。
父节点：若一个节点含有子节点，则这个节点称为其子节点的父节点。
孩子节点或者子节点：一个节点含有的子树的根节点称为该节点的子节点。
节点的层次：从根节点定义起，根为第一层，根的子节点为第二层，一次类推。
树的高度或者深度：树中节点的最大层次。
堂兄弟节点：父节点在同一层的节点互为堂兄弟。
节点的祖先：从根节点到该节点所经分支上的所有节点。
子孙：以某节点为根的子树中任一节点都称为该节点的子孙。
森林：有m(m>=0)棵互不相交的树的集合称为森林。

树的种类：
无序树：树中任意节点的子节点之间没有顺序关系，这种树称为无序树，也称自由树。
有序树：树中任意节点的子节点之间有顺序关系。
    二叉树：每个节点最多含有两个子树的树称为二叉树：
        完全二叉树：对于一棵二叉树，假设其深度为d(d>1),除第d层外，其它各层（1~d-1）的节点数
                   目均已达到最大值，且第d层所有节点从左到右连续紧密排列。
        满二叉树：除了叶子节点外，每个结点都有一个左右子树且所有叶子节点都在最底层的完全二叉树。
        平衡二叉树：当且仅当任何节点的两棵子树的高度差不大于1的二叉树。
        排序二叉树：也称二叉搜索树、有序二叉树。
    霍夫曼树（用于信息编码）：带权路径最短的二叉树，也称哈夫曼树、最优二叉树。
    B树：一种对于读写操作进行优化的自平衡的二叉查找树，能够保存数据有序，拥有多余两个子树。

二叉树的性质：
1.在二叉树的第i层上至多有2^(i-1)个节点(i>0)。
2.深度为k的二叉树至多有2^k-1个节点(k>0)。
3.对于任意一棵二叉树，如果其叶节点数为N0，度数为2的结点总数为N2，则N0=N2+1。
4.具有n个结点的完全二叉树的深度必为log2(n+1)。
5.对完全二叉树，若从上至下、从左至右编号，则编号为i的节点，其左孩子编号为2i,
  其右孩子编号必为2i+1；其双亲的编号必为i/2(i=1为根)

class Node(object):
    """节点类"""
    def __init__(self,elem=-1, lchild=None, rchild=None):
        self.elem = elem
        self.lchild = lchild
        self.rchild = rchild


class Tree(object):
    """树类"""
    def __init__(self, root=None):
        self.root = root

    def add(self,elem):
        # 为树添加节点
        node = Node(elem)
        #如果树是空的，则对根节点赋值
        if self.root is None:
            self.root = node
            return
        queue = [self.root]
        while queue:
            cur_node = queue.pop(0)
            if cur_node.lchild is None:
                cur_node.lchild = node
                return
            else:
                queue.append(cur_node.lchild)
                if cur_node.rchild is None:
                    cur_node.rchild = node
                    return
                else:
                    queue.append(cur_node.rchild)

    def breadth_travel(self):
        # 广度遍历
        if self.root is None:
            return
        queue = [self.root]
        while queue:
            cur_node = queue.pop(0)
            print(cur_node)
            if cur_node.lchild is not None:
                queue.append(cur_node.lchild)
            if cur_node.rchild is not None:
                queue.append(cur_node.rchild)

    # 任意给出两种遍历（其中一种必须是中序遍历），就能确定一棵树
    def preorder(self, node):
        # 先序遍历,递归思维
        if node is None:
            return
        print(node.elem)
        self.preorder(node.lchild)
        self.preorder(node.rchild)

    def inorder(self, node):
        # 中序遍历
        if node is None:
            return
        self.inorder(node.lchild)
        print(node.elem, end=" ")
        self.inorder(node.rchild)

    def postorder(self, node):
        # 后序遍历
        if node is None:
            return
        self.preorder(node.lchild)
        self.postorder(node.rchild)
        print(node.elem, end=" ")


if __name__ == "__main__":
    tree = Tree()
    tree.add(0)
    tree.add(1)
    tree.add(2)
    tree.add(3)
    tree.add(4)
    tree.add(5)
    tree.add(6)
    tree.add(7)
    tree.add(8)
    tree.add(9)
    tree.breadth_travel()
    tree.preorder(tree.root)