二叉树~查找算法~排序算法

二叉树

　　二叉树是一种树形结构，其中包含一个根节点和左右叶子节点，一个根节点下面只能有两个叶子节点（所谓二叉）

　　二叉树分为 普通二叉树和排序二叉树

　　一个二叉树中又包含多个子树，子树又分为完整的子树和非完整的子树，每个子树的根节点可以作为另一个子树的叶子节点，每个叶子节点又可以作为另一个子树的根节点

构建一个二叉树

class Node:
    #构建节点
    def __init__(self,item):
        self.item = item
        self.right = None
        self.left = None
        
class Tree:
    #构建二叉树
    def __init__(self):
        self.root = None
        
    #给二叉树添加节点
    def insert(self,item):
        node = Node(item)
        if self.root == None:
            self.root = node
            return
        cur = self.root
        queue = [cur]
        while True:
            leaf = queue.pop(0)
            if leaf.left == None:
                leaf.left = node
                return
            else:
                queue.append(leaf)
                
            if leaf .right == None:
                leaf.right = node
                return
            else:
                queue.append(leaf)

二叉树的遍历

广度遍历（横向）

    #广度遍历
    def travel(self):
        cur = self.root
        queue = [cur]
        while queue:
            leaf = queue.pop(0)
            print(leaf.item)
            if leaf.left:
                queue.append(leaf.left)
            if leaf.right:
                queue.append(leaf.right)

深度遍历（纵向） 注意：纵向遍历一定是作用于每个子树当中

前序遍历：根左右

def forward(self,root):
        if root == None:
            return
        print(root.item)
        self.forward(root.left)
        self.forward(root.right)

中序遍历：左根右 中序遍历排序二叉树时得到的结果肯定是有序的

    def middle(self,root):
        if root == None:
            return
        self.middle(root.left)
        print(root.item)
        self.middle(root.right)

后续遍历：左右根

    def back(self,root):
        if root == None:
            return
        self.back(root.left)
        self.back(root.right)
        print(root.item)

排序二叉树

　　排序二叉树即左叶子节点都要小于根节点，右叶子节点都要大于根节点，

构建一个排序二叉树

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

class SortTree:
    def __init__(self):
        self.root = None
        
    def insert(self,item):
        node = Node(item)
        if self.root == None:
            self.root = node
            return
        cur = self.root
        while True:
            #新节点插入到根节点的左侧
            if node.item < cur.item:
                if cur.left == None:
                    cur.left = node
                    return
                else:
                    cur = cur.left
            #新节点插入到根节点的右侧
            if node.item > cur.item:
                if cur.right == None:
                    cur.right = node
                    return
                else:
                    cur = cur.right

冒泡排序

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

选择排序

#选择排序
def sort(alist):
    for j in range(0,len(alist)-1):
        max_index = j
        for i in range(0,len(alist)-1-j):
            if alist[i] < alist[i+1]:
                max_index = i+1
        alist[-(j+1)],alist[max_index] = alist[max_index],alist[-(j+1)]
    return alist

插入排序

　　插入排序把数列分成有序和无序数列两个部分，其核心是将无序数列中的每个元素插入到有序数列的正确位置，起始有序数列元素个数为1,。

#插入排序
def sort(alist):
    #i可既能表示元素的下标，也可以表示有序数列的个数
    for i in range(1,len(alist)):
        while i > 0:
            if alist[i] < alist[i-1]:
                alist[i],alist[i-1] = alist[i-1],alist[i]
                i -= 1
            else:
                break
            
    return alist

希尔排序

　　希尔排序可以看成是按照增量（数列长度//2）分组进行插入排序

　　插入排序也可以看成是增量为1的希尔排序

#希尔排序
def sort(alist):
    gap = len(alist)//2
    while gap > 0:
        for i in range(gap,len(alist)):
            while i > 0:
                if alist[i] < alist[i-gap]:
                    alist[i],alist[i-gap] = alist[i-gap],alist[i]
                    i -= 1
                else:
                    break
        gap = gap // 2
    return alist

快速排序

　　简单的说一下快速排序，快速排序就是找一个基准值，将数列中的数据每循环一遍后达到的效果为基准值左侧的都是比基准值小的数值，基准值右侧的都是比基准值大的数值，然后再利用迭代对基准值左右两侧的数列分别进行快速排序，最后得到一个有序数列。

#快速排序
def sort(alist,start,end):
    
    low = start
    high = end
    if low > high:
        return alist
    
    mid = alist[start]
    print(mid)
    
    while low < high:
        while low < high:
            if alist[high] < mid:
                alist[low] = alist[high]
                break
            else:
                high = high -1
        while low < high:
            if alist[low] > mid:
                alist[high] = alist[low]
                break
            else:
                low = low + 1
    if low == high:
        alist[high] = mid
    #对左侧数列进行排序
    sort(alist,start,low-1)
    #对右侧数列进行排序
    sort(alist,high+1,end)
    
    return alist