day12 数据结构+算法

二叉树

class Node():
    def __init__(self,item):
        self.item = item
        self.left = None
        self.right = None
class Tree():
    def __init__(self):
        self.root = None
    def addNode(self,item):
        node = Node(item)
        if self.root == None:#如果树中没有节点,把第一个的节点给root
            self.root = node 
            return 
        cur = self.root #不改变root节点.赋值
        while 1 :
            q = [cur]  # 将节点加到列表中,然后在pop出来,左右为空,添加节点,不为空,添加到列表中继续判断
#  要赋值,否则每次都要pop,pop太多值了,一次.
#             if q.pop(0).left == None :#如果左节点没有
#                 q.pop(0).left = node #给左节点赋值
#                 return #退出函数
#             else:....
 
            n = pop(0)
            if n.left == None :#如果左节点没有
                n.left = node #给左节点赋值
                return #退出函数
            else:
                q.append(n.left)#如果左节点有,加到列表中判断
            if n.right == None :
                n.right = node 
                return 
            else:
                q.append(n.right)

广度排序

前序 (根左右)

写出一个来,然后套到别的树

有序的深度排序

中序

class SortTree():
    def __init__(self):
        self.root = None 
    def midTravel(self,root):
        if root = None 
            return 
        # 左根右
        self.midTravel(root.left) # 递归, 循环直到return 
        print(root.item)
        self.midTravel(root.right)

    def insertNode(self,item):
        node = Node(item)
        cur = self.root 
        # 数为空
        if self.root == None:
            self.root = node 
            return 
        # 树为非空 
        while True: 
            if cur.left > node.item :
                cur.left = node 
                break 
            else:
                cur = cur.left 
                
            if cur.right > node.item :
                cur.right = node 
                break 
            else:
                cur = cur.right
        
        

单链表写出之后,双链表也可以,循环列表

排序二叉树

写出来,写树的高度,什么都可以了.

深度排序:

中序有用, 也没有排序, 自动排序

排序算法

二分查找

• 有序列表对于我们的实现搜索是很有用的。在顺序查找中，当我们与第一个元素进行比较时，如果第一个元素不是我们要查找的，则最多还有 n-1 个元素需要进行比较。 二分查找则是从中间元素开始，而不是按顺序查找列表。 如果该元素是我们正在寻找的元素，我们就完成了查找。 如果它不是，我们可以使用列表的有序性质来消除剩余元素的一半。如果我们正在查找的元素大于中间元素，就可以消除中间元素以及比中间元素小的一半元素。如果该元素在列表中，肯定在大的那半部分。然后我们可以用大的半部分重复该过程，继续从中间元素开始，将其与我们正在寻找的内容进行比较。

low = 0 
high = len() -1 
mid = (low+high)//2
while  low <= high:
​   if items[mid]>item : low = ...
​   if < : high = ...
​   else : find = T
return find 


# 基于有序  减半  速度

def search(alist,item):
    find = False
    low = 0
    high = len(alist)-1
    
    while low <= high:
        mid = (low+high) // 2 #中心位置的元素下标（切割点）
        if alist[mid] < item:
            low = mid + 1
        elif alist[mid] > item:
            high = mid - 1
        else:#alist[mid] == item
            find = True
            break
        
    return find
alist = [1,2]
print(search(alist,22))        

冒泡排序

• 1.将原始列表中的最大值找出且放置在列表最右侧(将元素两两比较，将数值大的数逐步向后移动)
• 2.重复执行步骤1

#将原始列表中的最大值找出且放置在列表最右侧(将元素两两比较，将数值大的数逐步向后移动)
def sort(alist):
    for i in range(len(alist)-1):
        if alist[i] > alist[i+1]:
            alist[i],alist[i+1] = alist[i+1],alist[i]
    return alist
        

def sort(alist):
    for j in range(len(alist)-1):
        #交换
        for i in range(len(alist)-1-j):
            if alist[i] > alist[i+1]:
                alist[i],alist[i+1] = alist[i+1],alist[i]
            
            
    return alist

alist = [3,6,1,4,8,2]
print(sort(alist))

----->[1, 2, 3, 4, 6, 8]

选择排序

将最大值一次找出, 放在列表最右

#将列表中的最大值的下标找到
def sort(alist):
    max_index = 0 #最大值的下标
    for i in range(1,len(alist)):
        if alist[max_index] < alist[i]:
            max_index = i
    print(max_index)

#将列表中的最大值一次找出，放置在列表最右侧
def sort(alist):
    max_index = 0 #最大值的下标
    for i in range(1,len(alist)):
        if alist[max_index] < alist[i]:
            max_index = i
    alist[max_index],alist[len(alist)-1] = alist[len(alist)-1],alist[max_index]
    
    return alist

def sort(alist):
    for j in range(len(alist),1,-1):
        max_index = 0 #最大值的下标
        for i in range(1,j):  #len(alist)  == > j
            if alist[max_index] < alist[i]:
                max_index = i
        alist[max_index],alist[j-1] = alist[j-1],alist[max_index]
    
    return alist

alist = [3,6,1,4,8,2]
sort(alist)

---->[1, 2, 3, 4, 6, 8]

相比来说,交换的次数少了, 在第一循环内部, 第二循环外部

排序二叉树

class SortTree():
    def __init__(self):
        self.root = None
        
    def midTravel(self,root):
        if root == None:
            return
        #左根右
        self.midTravel(root.left)
        print(root.item)
        self.midTravel(root.right)
        
    def insertNode(self,item):
        node = Node(item)
        cur = self.root
        #树为空
        if self.root == None:
            self.root = node
            return
        #树为非空
        while True:
            if cur.item > node.item:
                if cur.left == None:
                    cur.left = node
                    break
                else:
                    cur = cur.left
            else:
                if cur.right == None:
                    cur.right = node
                    break
                else:
                    cur = cur.right
        

t = SortTree()
t.insertNode(3)
t.insertNode(8)
t.insertNode(3)
t.insertNode(1)
t.insertNode(1)

t.midTravel(t.root)

---->

1
1
3
3
8

快排

def sort(alist,start,end):
    low = start
    high = end

    
    #结束递归的条件
    if low > high:
        return
    mid = alist[low]
    
    while low < high:
        while low < high:
            if alist[high] > mid:
                high -= 1
            else:
                alist[low] = alist[high]
                break
        while low < high:
            if alist[low] < mid:
                low += 1
            else:
                alist[high] = alist[low]
                break
                
#         if low == high:
    alist[low] = mid
    
    sort(alist,low+1,end) #将基准右侧的子列表进行递归操作
    sort(alist,start,high-1)
    return alist