本篇内容是关于数据结构以及算法。

引言

数据结构和算法是什么？是兵法！用于提升程序运行效率，提升性能有神效！并且可以优化。

排序与搜索

冒泡排序 Bubble Sort

交换过程：

假如按照升序，第一次冒泡的时候，从第一个数字开始，和第二个对比，如果是大于，交换位置，否则不变，继续第二个和第三个的对比，直到第n-1个和第n个，第一次冒泡结束，一共对比了n-1次，最右边的为最大的数字（如果是降序则为最小）。排序结束后，一共会有n-1次冒泡。如图：

冒泡演示：

def bubbleSort(alist):
    for passnum in range(len(alist)-1,0,-1):
        for i in range(passnum):
            if alist[i]>alist[i+1]:
                temp = alist[i]
                alist[i] = alist[i+1]
                alist[i+1] = temp

alist = [54,26,93,17,77,31,44,55,20]
bubbleSort(alist)
print(alist)

选择排序 Selection Sort

选择排序改进了冒泡排序，每次通过列表只做一次的交换。一次选择排序寻找一个最大值，并将其放置在正确的位置。

def selectionSort(alist):
        for index in range(len(alist)-1,0,-1):
            positionMax = 0
        for location in range(1,index+1):
            if alist[location]>alist[positionMax]:
            positionMax = location
        temp = alist[index]
        alist[index] = alist[positionMax]
        alist[positionMax] = temp

alist = [54,226,93,17,77,31,44,55,20]
selectionSort(alist)
print(alist)

插入排序

快速排序

二叉树

二叉树遍历

遍历：指对树中的所有的节点进行访问，依次对每一个节点访问一次且仅一次，称为遍历。分为深度优先和广度优先2种：
深度优先：一般用递归。
广度优先：一边用队列。
能用递归实现的算法也能用堆栈实现。

深度遍历

沿着树的深度遍历树的节点，尽可能的搜索树的分支。
分为3种遍历方式：先序遍历，中序遍历，后序遍历。不同之处在于访问节点的顺序不同。

先序遍历
这种方式先访问的是根节点，然后递归使用先序遍历访问左子树，再递归使用先序遍历访问右子树。
即：根节点–>左子树–>右子树
def front(self, root):
```
"""递归实现先序遍历"""
if root == None:
  return
print root.elem
self.front(root.lchild)
self.front(root.rchild)
```
访问时，根节点开始，因为是深度遍历，向下只找寻每一层的左子树节点，一层层往下，直到最后一层的左子树节点；下一个访问最后一层的同一根节点的右子树节点；再向上找寻有分支的根节点并向下找寻，依旧按照先左后右的顺序。
请看最下方的示例。
中序遍历
这种方式，递归使用中序遍历访问左子树，然后，根节点，最后递归使用中序遍历访问右子树。
即：左子树–>根节点–>右子树
def middle(self, root):
```
"""递归实现中序遍历"""
if root == None:
  return
self.middle(root.lchild)
print root.elem
self.middle(root.rchild)
```
访问时，从二叉树的最左边的节点开始，再这一左子树节点的根节点；再这一根节点下的右子树节点；当前根节点遍历完后，再向上找寻根节点，上一层根节点下如果存在任何一个左子树节点（无论是在哪一层上），都先从最底层的左子树节点开始，按照先前的顺序开始。
后序遍历
这种方式，先是递归使用后序变量访问左子树，再右子树，最后根节点。
即:左子树–>右子树–>根节点
def later(self, root):
“””递归实现后续遍历”””
```
if root == None:
    return
self.later(root.lchild)
self.later(root.rchild)
print root.elem
```

广度遍历

使用队列实现，从根节点开始，从上到下从左到右依次遍历真个树的节点。
广度遍历可以查出每一层的宽度以及二叉树的最大宽度。（某次面试就被考到这个问题）
>def level_queue(self, root):
“””利用队列实现树的层次遍历”””
if root == None:
return
myQueue = []
node = root
myQueue.append(node)
while myQueue:
node = myQueue.pop(0)
print node.elem,
if node.lchild != None:
myQueue.append(node.lchild)
if node.rchild != None:
myQueue.append(node.rchild)

示例：