1.樹:

樹:

樹是一種資料結構.

樹是一種可以遞回定義的資料結構.

樹由n個節點組成的集合

n=0時,是空樹

n>0,一個節點作為根節點,其他節點可以分為m個集合,每個集合本身又是一棵樹(這就是重復單元)

節點的度:就是一個節點的子節點有多少個

樹的度:整個樹中最大的節點的度就是樹的度

父節點:在上面緊挨著它的節點就是父節點(A是D的父節點,但是A不是H的父節點)

子節點:一個節點下面緊挨著它的節點就是它的子節點(A下面的B,C,D,E,F,G都是它的子節點)

根節點(上面沒有父節點):A

葉子節點(后面不能再分叉):B,C,H,I,P,Q,K,L,M,N,或者說度為0的節點就叫葉子節點

樹的深度(高度):根到葉子最長的節點個數(就是最多幾層)

子樹:EIJPQ就是個子樹

用樹模擬檔案系統:

class Node:#創建檔案夾,這里暫時沒有創建檔案的功能
    def __init__(self,name,type='dir'):
        self.name=name
        self.type=type  #'dir' or 'file'
        self.children=[]
        self.parent=None
        #鏈式存盤
    def __repr__(self):
        return self.name

class FileSystemTree:
    def __init__(self):
        self.root=Node('/')
        self.now=self.root
    def mkdir(self,name):#創建檔案夾
        #name以/結尾
        if name[-1] != '/':
            name+='/'
        node=Node(name)
        self.now.children.append(node)
        node.parent=self.now

    def ls(self):#展示檔案夾下所有檔案
        return self.now.children

    def cd(self,name):#進入某個檔案夾
        if name[-1] != '/':
            name+='/'
        if name=='../': #回傳上一級目錄了
            self.now=self.now.parent
            return
        for  child in self.now.children:
            if child.name==name:
                self.now=child
                return
        raise  ValueError('invalid dir')

tree =FileSystemTree()
tree.mkdir('var/')
tree.mkdir('usr/')
tree.mkdir('bin/')
print(tree.root.children)#[var/]回傳檔案名

tree.cd('bin/')
tree.mkdir('python/')

tree.cd('../')
print(tree.ls())

二叉樹:

度不超過2的樹(整個樹中每個節點最多有連個孩子節點,分別為左孩子節點和右孩子節點)就是二叉樹

滿二叉樹:

一個二叉樹,如果每一層的節點數都達到最大值,則這個二叉樹就是滿二叉樹.

如圖:

完全二叉樹:

葉子節點只能出現在最下層和次下層,并且最下面一層的節點都集中在該層最左邊的若干位置的二叉樹

如圖:

二叉樹的順序存盤方式:

 節點的索引下標用紅字寫在上面了

看一下父節點(假設是i)的下標與左右孩子結點的關系

所有左節點的下標都是2i+1(可以試i=0,1,2,3得到的索引全是左下標)

所有右節點的下標都是2i+2

只要知道父節點就可以算出左和右的子節點

知道到左右節點的索引后都可以直接減一再底板除(//)來得到父節點的索引(底板除得到小數后向下取整,不會四舍五入)

二叉樹的鏈式存盤方式:

將二叉樹的節點定義為一個物件,節點之間通過類似鏈表的鏈接方式來連接

如圖:

 代碼如下:

class BiTreeNode:
    def __init__(self,data):
        self.data=data
        self.lchild=None #左孩子
        self.rchild=None #右孩子

a=BiTreeNode('A')
b=BiTreeNode('B')
c=BiTreeNode('C')
d=BiTreeNode('D')
e=BiTreeNode('E')
f=BiTreeNode('F')
g=BiTreeNode('G')

e.lchild=a
e.rchild=g
a.rchild=c
c.lchild=b
c.rchild=d
g.rchild=f

root=e
print(root.lchild.rchild.data)
#輸出:C

鏈式存盤的遍歷

共四種遍歷

注意:

　　這四種遍歷分類:

　　深度優先:

　　　　　　①前序遍歷

　　　　　　②中序遍歷

　　　　　　③后序遍歷

　　廣度優先:

　　　　　　①層次遍歷

①前序遍歷:

先父節點,再左子樹,再走右子樹,保證每一層都是'父左右'這樣的結構

def pre_order(root):#前序遍歷,先父節點,再左子樹,再走右子樹,保證每一層都是'父左右'這樣的結構
    if root :
        print(root.data,end=',')
        pre_order(root.lchild)
        pre_order(root.rchild)

pre_order(root)
#輸出:E,A,C,B,D,G,F,

②中序遍歷:

父節點在中間,左邊是左子樹遞回的,右邊是右子樹遞回的,保證每一層都是'左父右'這樣的結構

def in_order(root):#中序遍歷,父節點在中間,左邊是左子樹遞回的,右邊是右子樹遞回的,保證每一層都是'左父右'這樣的結構(有點像快排,找中位數,中位數就是父節點)
    if  root:
        in_order(root.lchild)
        print(root.data,end=',')
        in_order(root.rchild)

in_order(root)
#輸出:A,B,C,D,E,G,F,

③后序遍歷:

先左子樹,后右子樹,最后是父節點,保證每一層都是'左右父'這樣的結構

def post_order(root):  #后序遍歷,先左子樹,后右子樹,最后是父節點,保證每一層都是'左右父'這樣的結構
    if root:
        post_order(root.lchild)
        post_order(root.rchild)
        print(root.data,end=',')

post_order(root)
# 輸出:B,D,C,A,F,G,E,

注意:以上三種序列,至少給兩個,才能唯一確定一種樹,否則只給一種順序,會有多種樹的結構

④層次遍歷:

(利用佇列),多叉樹也適用

 按照從跟到葉子節點，每一層節點都是從左到右出來的，

from collections import deque

def level_order(root):
    queue=deque()
    queue.append(root)
    while len(queue)>0:#只要隊不為空
        node=queue.popleft()#出隊
        print(node.data,end=',')
        if node.lchild:
            queue.append(node.lchild)
        if node.rchild:
            queue.append(node.rchild)

level_order(root)
#E,A,G,C,F,B,D,

二叉搜索樹： 

一個二叉樹,滿足:假設x是二叉樹的一個節點,y是x的左子樹的一個節點,z是x的右子樹的一個節點,那么一定有y.key<=x.key和z.key>=x.key

class BST:
    def __init__(self,li=None):#傳個串列進來
        self.root=None
        if li:#傳個串列進來,串列是非空，就把串列內容都插入二叉搜索樹中
            for val in li:
                self.insert_no_rec(val)
    #插入 寫法一：  遞回寫法
    def insert(self,node,val):#插入操作:node是要插入的二叉樹的根節點,val是要插入的節點的值
        if not node:#節點不存在,就新創建一個節點
            node =BiTreeNode(val)
        elif val < node.data: #如果節點存在,就看傳進來時從根節點向下一個一個的比較大小,如果val比較小,就一直往左走
            node.lchild=self.insert(node.lchild,val)
            node.lchild.parent=node
        elif val>node.data:#如果val值比較大,就一直往右走
            node.rchild=self.insert(node.rchild,val)
            node.rchild.parent=node
        return node
    #插入 寫法二：  非遞回寫法,速度比較快
    def insert_no_rec(self,val):
        p=self.root
        if not p:#如果是個空樹
            self.root=BiTreeNode(val)
            return
        while True: #如果不是空樹
            if val <p.data:#如果val小于這個節點的值,就往左孩子上插
                if p.lchild:#如果左孩子存在
                    p=p.lchild#原來和val比大小的節點就移動到他左孩子上,讓左孩子和val比大小
                else:#如果做孩子不存在
                    p.lchild=BiTreeNode(val)#就直接把val實體化出個物件,放到左孩子的位置上
                    p.lchild.parent=p
                    return
            elif val>p.data:#如果val大于比較的這個節點的值,那就讓val和他的右孩子比大小
                if p.rchild:
                    p=p.rchild
                else:
                    p.rchild=BiTreeNode(val)
                    p.rchild.parent=p
                    return
            else:#val和根節點的值相同,就不動了
                return

    # 查詢 寫法一:遞回版本
    def query(self,node,val):
        if not node:
            return None
        if node.data<val:
            return self.query(node.rchild,val)
        elif node.data>val:
            return self.query(node.lchild, val)
        else:
            return node
    # 查詢 寫法二:非遞回版本
    def query_no_rec(self,val):
        p=self.root
        while p:
            if p.data<val:
                p=p.rchild
            elif p.data>val:
                p=p.lchild
            else:
                return p
        return None

    # 三種遍歷:
    def pre_order(self,root):#前序遍歷
        if root :
            print(root.data,end=',')
            self.pre_order(root.lchild)
            self.pre_order(root.rchild)
    def in_order(self,root):#中序遍歷,中序出來的結果一定是從小到大排好序的
        if  root:
            self.in_order(root.lchild)
            print(root.data,end=',')
            self.in_order(root.rchild)
    def post_order(self,root): #后序遍歷
        if root:
            self.post_order(root.lchild)
            self.post_order(root.rchild)
            print(root.data,end=',')

#插入測驗
tree=BST([1,3,10,0,9,6,4,2,8,7,5])

tree.pre_order(tree.root)
#1,0,3,2,10,9,6,4,5,8,7,
print('')
tree.in_order(tree.root)#而中序出來的一定是按從小到大排好序的(左父右)
#0,1,2,3,4,5,6,7,8,9,10,
print('')
tree.post_order(tree.root)
#0,2,5,4,7,8,6,9,10,3,1,

#查詢測驗
import  random
li=list(range(0,500,2))#全是偶數
random.shuffle(li)
tree=BST(li)
print(tree.query_no_rec(3))#3是偶數不存在的這個二叉樹中
#None
print(tree.query_no_rec(4))
#<__main__.BiTreeNode object at 0x038EC510>
print(tree.query_no_rec(4).data)
#4

2.堆:

一種特殊的完全二叉樹結構

大根堆:

一棵完全二叉樹,滿足任一節點都比孩子節點大

小根堆:

一棵完全二叉樹,滿足任一節點都比其孩子節點小

堆的向下調整:

堆整體不是個跟堆,但是左子樹是個大根堆或小根堆,右子樹是個大根堆或者小根堆(左右要保持一致都是大根堆或者都是小根堆)

這時可以通過向下調整使得整個跟堆變成一個大根堆或者小根堆

如圖,左右都是大根堆,但是整體不是大根堆,此時要把2向下調整

調整后:整體是個大根堆

堆排序:

時間復雜度:O(nlogn)

推算:

　　sift是logn,這個函式每次運行時走的是樹的高度,每次都折半,不是左就是右,所以是logn

　　heap_sort是n或n/2,里面又套了sift,所以就是nlogn

步驟:

1.建立堆
2.得到堆頂元素,為最大元素
3.去掉堆頂,將堆最后一個元素(葉子結點最右邊的元素,上圖中3就是最后一個元素)放到堆頂,此時可以通過一次調整(向下調整)重新使堆有序
4.堆頂元素為第二大元素
5.重復步驟3,直到堆為空

代碼: 

步驟:先建大根堆,再從下到上回圈每個父節點(自下而上就不怕你向下取回圈,因為之前的都已經回圈過了,最大的數字一定在上面),造出大根堆,

最后取根節點值與最后一個索引位置交換,再用sift方法從頭到尾n-2..直到0,一個一個地與根節點值進行交換,交換后的最后面的索引的值就是當前串列的最大值(排序就一點一點的按照串列的順序來了).

# 堆排序(沒用遞回)
#第一步:調整三個節點:父節點和左右子節點,使其成為大根堆,如果while能一直向下回圈,那么這次操作就是一次向下回圈
def sift(li, low, high):
    """
    :param li: 串列
    :param low: 堆的根節點位置
    :param high: 堆的最后一個元素的位置,high是最后一個數字的索引,超了high就不存在了
    :return:
    """
    i = low # i最開始指向根節點,根節點數字的索引
    j = 2 * i + 1 # j開始是左孩子,j是i的左孩子的索引
    tmp = li[low] # 把堆頂存起來
    while j <= high: # 只要j位置有數
        #如果右孩子節點存在,就和左孩子節點比較大小,把大的值放到l[j]中
        if j + 1 <= high and li[j+1] > li[j]: # 如果右孩子有并且右孩子比左孩子大,j + 1 <= high保證右孩子不超索引范圍
            j = j + 1  # j指向右孩子
        #如果子節點中最大值大于父節點的值,那就將父節點的值改成最大的子節點的值,此時i指的是父節點的索引,l[j]是三個節點中的最大值
        if li[j] > tmp: #子節點找到了最大的li[j],他要和根節點(如果不在頂層就是父節點了)的數字比大小,大的放在根節點
            li[i] = li[j]
            i = j           # 往下看一層,相當于i+=1,i向下走了一層,j也就向下走一層,找到了下一層的左孩子
            j = 2 * i + 1
        #如果前面兩個if都不成立,那么父節點(tmp)的值就是三個節點中最大的了
        else:       # tmp更大，把tmp放到i的位置上
            li[i] = tmp     # 把tmp放到某一級領導位置上
            break
    #如果j超過了索引范圍,那么此時i就指到了葉子節點(也就是最后一行了),那么就證明tmp是最小的,就把tmp放到最后一行空著的的葉子節點(li[i])即可
    else:#此時j>high,而i到了最后一行了,就把tmp放到最后一行的子葉了
        li[i] = tmp  # 把tmp放到葉子節點上


#建堆+出串列
def heap_sort(li):
    n = len(li)
    # 回圈所有父節點建堆(重點:倒序回圈父節點,從最下面的父節點開始回圈)
    for i in range((n-2)//2, -1, -1):
        #先從最后一個節點的父節點開始回圈,
        # 最后一個節點假設是i,它的父節點就是(i-1)//2這是固定的演算法，不管是左子節點還是右子節點,
        # 現在最后一個數字索引是n-1,那么他的父節點就是（n-2）//2
        # i表示建堆的時候調整的部分的根的下標,每次i都是一個父節點,調整的是他的子樹(只包含自己的兩個子節點)
        #這里是從(n-2)//2遍歷到0(顧頭不顧尾),倒序(-1)
        sift(li, i, n-1)
        #這里n-1一直指代這個堆的最后一個葉子節點,
        # 其實他應該變化,每次都應該指該子樹的右子節點,
        # 但是這個不容易求,n-1肯定比其他子樹的右子節點大,用它限制肯定會多算幾步,但是一定不會錯

    # 建堆完成了(是按照堆的順序排的數字)
    print('跟堆建成:',li)#現在出來的串列是按照堆的順序拿出來的,還要最后排一下序

    #按照串列的順序排序()
    for i in range(n-1, -1, -1): #這里可以改寫成(n-1,0,-1),顧頭不顧尾,所以0這一次不會繼續回圈了,到1就結束了,到最后一個元素0索引時,下一步自己和自己交換就沒意思了,所以我個人認為可以吧-1換成0
        # i 每次取值都是指向當前堆的最后一個元素
        #從n-1遍歷到0,每次步長是-1,就相當于是串列從最右端每次都向最左端挪一位
        li[0], li[i] = li[i], li[0]
        sift(li, 0, i - 1)
        #i-1是新的high,i指的是最后一個數字,他現在放的是根節點那個最大數字,
        # 回圈一次就相當于最大值找到了,再回圈一次就又找了個第二大的


li = [i for i in range(100)]
import random
random.shuffle(li)
print('手動建的亂序表:',li)

heap_sort(li)
print('排序后的結果:',li)

sift的操作就是自上而下把每三個節點(父節點,左右子節點)都組成大根堆

注意:如果你不確定你這個堆整體是大根堆,你從根節點開始,用sift方法最后得到的不一定是大根堆,因為最大的數字不一定在最上面三個節點里面出現.

python中有對排列模塊heapq:

import heapq #q表示queue佇列的意思  實作優先佇列(優先小的先出或者大的先出)
import random
li = list(range(100))
random.shuffle(li)
print(li)#新建的亂序串列
heapq.heapify(li) #建堆,這里python模塊默認建的是小根堆
n=len(li)
lst=[]
for i in range(n):
    # print(heapq.heappop(li), end=' ')#小根堆,每次都彈出最小的
    lst.append(heapq.heappop(li))
print(lst)

堆排序的topk問題:

topk問題:串列有n個數字,從大到小排序,我取前k大的數字

應用場景:微博熱搜問題,不需要存資料庫,因為很多,而且時間間隔不長,經常會更換.

解決思路:

　　①先排序(快排),后切片 時間復雜度(最大):O(nlogn+k) 當k<n時k可以省略.O(nlogn)

　　②冒泡/選擇/插入,排序后再切片, 時間復雜度(第二大): O(kn)

　　③堆排序, 時間復雜度(最小):O(nlogk)當k為128時,logk=7,很小的,k越大,這里面堆排序復雜度就相對越小

實作步驟(堆排序思路):

　　①取串列前k個元素,并建立一個小根堆,堆頂就是串列中第k大的數字

　　②從k往后依次遍歷原來的串列,取出一個數字就和堆頂的數字比大小,如果堆頂的數字較大,那回圈繼續往下走,不做任何操作,如果你從原串列取的數字大于堆頂的數字,那就將他替換堆頂的數字,并對這k個元素組成的堆進行調整,使之成為一個新的小根堆.

　　③當你從k+1直到遍歷完原串列,,你得到了一個小根堆,這個小根堆就是前k大的數字,你再像堆排序最后出數那樣倒序彈出堆頂的數字(因為現在是小根堆,堆頂數字是這里面最小的)

代碼:

def sift(li, low, high):
    i = low
    j = 2 * i + 1
    tmp = li[low]
    while j <= high:
        if j + 1 <= high and li[j+1] < li[j]:#注意這里要建小根堆,使大的數字都在下面
            j = j + 1
        if li[j] < tmp: #注意這里要建小根堆,使大的數字都在下面
            li[i] = li[j]
            i = j
            j = 2 * i + 1
        else:
            break
    li[i] = tmp


def topk(li, k):
    heap = li[0:k]
    # 1.建堆
    for i in range((k-2)//2, -1, -1):
        sift(heap, i, k-1)
    # 2.遍歷原串列k以外的元素(k到n-1)注:k以外的第一個元素的索引是k,最終得到的小根堆只包含前k大的數字
    for i in range(k, len(li)):
        if li[i] > heap[0]:
            heap[0] = li[i]
            sift(heap, 0, k-1)

    # 3.出數(前k大的數字已經拿好了都在heap里面了,都在小根堆上,現在是要排序了)
    for i in range(k-1, -1, -1): #這里可以改寫成(k-1,0,-1),因為最后一次是heap[0]和自己交換,沒意義,所以就到1時就結束了(range顧頭不顧尾)
        heap[0], heap[i] = heap[i], heap[0]
        sift(heap, 0, i - 1)

    return heap#你要的數字已經存到了heap里面了

import random
li = list(range(200))
random.shuffle(li)

print(topk(li, 10))#我取前10個大的數字

標籤：Python

上一篇：tornado服務器作業原理

下一篇：Pytorch tensor的復制函式torch.repeat_interleave()