摘要：什么是數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)的組織結(jié)構(gòu)方式一組數(shù)據(jù)如何存儲(chǔ)，基本數(shù)據(jù)類型，，的封裝算法與數(shù)據(jù)結(jié)構(gòu)的區(qū)別數(shù)據(jù)結(jié)構(gòu)只是靜態(tài)的描述了數(shù)據(jù)元素之間的關(guān)系。高效的程序需要在數(shù)據(jù)結(jié)構(gòu)的基礎(chǔ)上設(shè)計(jì)和選擇算法。

什么是數(shù)據(jù)結(jié)構(gòu)和算法：兵法，計(jì)算的方法。
算法是獨(dú)立存在的一種解決問題的方法和思想。

算法的特征：

輸入：算法具有0個(gè)或多個(gè)輸入

輸出：算法至少有1個(gè)或多個(gè)輸出

有窮性：算法在有限的步驟之后會(huì)自動(dòng)結(jié)束而不會(huì)無限循環(huán)，并且每一個(gè)步驟可以在可接受的時(shí)間內(nèi)完成

確定性：算法中的每一步都有確定的含義，不會(huì)出現(xiàn)二義性

可行性：算法的每一步都是可行的，也就是說每一步都能執(zhí)行有限的次數(shù)完成

時(shí)間復(fù)雜度和大O表示法

算法的優(yōu)劣： 實(shí)現(xiàn)算法程序的執(zhí)行時(shí)間可以反應(yīng)出算法的效率

時(shí)間復(fù)雜度：步驟的執(zhí)行速度(基本執(zhí)行數(shù)量總和) + 程序運(yùn)行環(huán)境（包括硬件和操作系統(tǒng)）

假設(shè)存在函數(shù)g，使得算法A處理規(guī)模為n的問題示例所用時(shí)間為T(n)=O(g(n))，則稱O(g(n))為算法A的漸近時(shí)間復(fù)雜度，簡稱時(shí)間復(fù)雜度，記為T(n)
T: time
三個(gè)1000次for循環(huán):
T = 1000 * 1000 * 1000 * 2 -> T(n) = n ^ 3 * 2 -> g(n) = n ^ 3, T(n) = k * g(n) -> T(n) = O(g(n))

“大O記法”：對于單調(diào)的整數(shù)函數(shù)f，如果存在一個(gè)整數(shù)函數(shù)g和實(shí)常數(shù)c>0，使得對于充分大的n總有f(n) <= c*g(n)，就說函數(shù)g是f的一個(gè)漸近函數(shù)（忽略常數(shù)），記為f(n)=O(g(n))。
也就是說，在趨向無窮的極限意義下，函數(shù)f的增長速度受到函數(shù)g的約束，亦即函數(shù)f與函數(shù)g的特征相似。

最壞時(shí)間復(fù)雜度

算法完成工作最少需要多少基本操作，即最優(yōu)時(shí)間復(fù)雜度

算法完成工作最多需要多少基本操作，即最壞時(shí)間復(fù)雜度

算法完成工作平均需要多少基本操作，即平均時(shí)間復(fù)雜度

最優(yōu)時(shí)間復(fù)雜度，其價(jià)值不大。
最壞時(shí)間復(fù)雜度，提供了一種保證，（只要關(guān)注，最壞時(shí)間復(fù)雜度）
平均時(shí)間復(fù)雜度，是對算法的一個(gè)全面評價(jià)。

時(shí)間復(fù)雜度的幾條基本計(jì)算規(guī)則

基本步驟，即只有常數(shù)項(xiàng)，認(rèn)為其時(shí)間復(fù)雜度為O(1)

順序結(jié)構(gòu)，時(shí)間復(fù)雜度按加法進(jìn)行計(jì)算

循環(huán)結(jié)構(gòu)，時(shí)間復(fù)雜度按乘法進(jìn)行計(jì)算

分支結(jié)構(gòu)，時(shí)間復(fù)雜度取最大值（if 或者 else 哪個(gè)步數(shù)最多）

判斷一個(gè)算法的效率時(shí)，往往只需要關(guān)注操作數(shù)量的最高次項(xiàng)，其它次要項(xiàng)和常數(shù)項(xiàng)可以忽略

在沒有特殊說明時(shí)，所分析的算法的時(shí)間復(fù)雜度都是指最壞時(shí)間復(fù)雜度

計(jì)算方式：

# for a in range(0, n):
#     for b in range(0, n):
#         c = 1000 - a - b
#         if a ** 2 + b ** 2 == c **2:
#             print("a, b, c為：%d"%(a, b, c))


# T(1000) = 1000 * 1000 * (1 + 1)
# T(n) = n * n * (1 + max(1, 0))
#  = n ^ 2 * 2
#  = O(n ^ 2)

常見時(shí)間復(fù)雜度與大小關(guān)系

Note: 經(jīng)常將log2n（以2為底的對數(shù)）簡寫成logn

所消耗的時(shí)間從小到大:
O(1) < O(logn) < O(n) < O(nlogn) < O(n2) < O(n3) < O(2n) < O(n!) < O(n^n)

Note：函數(shù)是步驟和執(zhí)行結(jié)構(gòu)的綜合

Python內(nèi)置類型性能

timeit模塊作用：測試一小段Python代碼代碼的執(zhí)行速度

class timeit.Timer(stmt="pass", setup="pass", timer=)
Timer是測量小段代碼執(zhí)行速度的類。
stmt參數(shù)是要測試的代碼語句（statment）；
setup參數(shù)是運(yùn)行代碼時(shí)需要的設(shè)置；
timer參數(shù)是一個(gè)定時(shí)器函數(shù)，與平臺(tái)有關(guān)。

#coding=utf-8

from timeit import Timer


def test1():
    li = []
    for i in range(10000):
        li.append(i)

def test2():
    li = []
    for i in range(10000):
        li += [i]

def test3():
    li = [i for i in range(10000)]

def test4():
    li = list(range(10000))

timer1 = Timer("test1()", "from __main__ import test1")
print("append: ",timer1.timeit(1000)) # 測算次數(shù), 返回值測算時(shí)間

timer2 = Timer("test2()", "from __main__ import test2")
print("+: ",timer1.timeit(1000))

timer3 = Timer("test3()", "from __main__ import test3")
print("[]: ",timer1.timeit(1000))

timer4 = Timer("test4()", "from __main__ import test4")
print("list: ",timer1.timeit(1000))

list內(nèi)置操作的時(shí)間復(fù)雜度:

n: 列表長度
k: 范圍

主要：

index[] -> O(1)
append -> O(1)
pop(i) -> O(n)
insert(i, item) -> O(n)
contains(in) -> O(n)

dict內(nèi)置操作的時(shí)間復(fù)雜度:

數(shù)據(jù)結(jié)構(gòu)引入

算法關(guān)注在解決問題的步驟和思想上面。

什么是數(shù)據(jù)結(jié)構(gòu)：數(shù)據(jù)的組織結(jié)構(gòu)方式,（一組數(shù)據(jù)如何存儲(chǔ)），基本數(shù)據(jù)類型（int， float，char）的封裝

算法與數(shù)據(jù)結(jié)構(gòu)的區(qū)別：
數(shù)據(jù)結(jié)構(gòu)只是靜態(tài)的描述了數(shù)據(jù)元素之間的關(guān)系。
高效的程序需要在數(shù)據(jù)結(jié)構(gòu)的基礎(chǔ)上設(shè)計(jì)和選擇算法。

程序 = 數(shù)據(jù)結(jié)構(gòu) + 算法

總結(jié)：算法是為了解決實(shí)際問題而設(shè)計(jì)的，數(shù)據(jù)結(jié)構(gòu)是算法需要處理的問題載體

最常用的數(shù)據(jù)運(yùn)算有五種:

插入

刪除

修改

查找

排序

內(nèi)存

32位機(jī)器：一個(gè)int, 占四個(gè)字節(jié)。

變量表示起始地址位置

內(nèi)存的基本信息：

單位：字節(jié)， 1byte == 8bit

連續(xù)的存儲(chǔ)空間

一個(gè)字節(jié)表示一個(gè)地址單元

類型本質(zhì)

任何變量，函數(shù)原則上都是一塊塊大小各異的內(nèi)存，而類型則是和系統(tǒng)對這塊內(nèi)存含義的約定（固定內(nèi)存塊大小的別名）

決定在內(nèi)存中占多少個(gè)單元

基本順序表與元素外圍順序表

順序表的基本布局：

數(shù)據(jù)元素本身連續(xù)存儲(chǔ)，每個(gè)元素所占的存儲(chǔ)單元大小固定相同，元素的下標(biāo)是其邏輯地址，而元素存儲(chǔ)的物理地址（實(shí)際內(nèi)存地址）可以通過存儲(chǔ)區(qū)的起始地址Loc (e0)加上邏輯地址（第i個(gè)元素）與存儲(chǔ)單元大小（c）的乘積計(jì)算而得

所以，訪問指定元素時(shí)無需從頭遍歷，通過計(jì)算便可獲得對應(yīng)地址，其時(shí)間復(fù)雜度為O(1)

下標(biāo)：地址單元的偏移量，才會(huì)規(guī)定為從0開始。

順序表的元素外置基本布局：

元素外置在內(nèi)存中存儲(chǔ)地址，地址字節(jié)是相同的（可以使用順序表），而非變化的字節(jié)。

順序表的一體式結(jié)構(gòu)與分離式結(jié)構(gòu)

順序表 = 數(shù)據(jù)區(qū)(元素集合) + 表頭信息(容量 + 元素個(gè)數(shù))

容量: 在最初始的時(shí)候，就要預(yù)估當(dāng)前規(guī)模，一次性向操作系統(tǒng)申請內(nèi)存地址 （最大存儲(chǔ)多少）
元素個(gè)數(shù)：當(dāng)前存儲(chǔ)多少

順序表的基本實(shí)現(xiàn)方式（表頭和數(shù)據(jù)區(qū)如何組合在一起）：

一體式結(jié)構(gòu)：
優(yōu)點(diǎn): 一次性申請， 整體性強(qiáng)，易于管理。
缺點(diǎn)：元素存儲(chǔ)區(qū)就固定。當(dāng)數(shù)據(jù)存儲(chǔ)不下的時(shí)候，需要整體替換重新向操作系統(tǒng)申請

分離式結(jié)構(gòu)：
優(yōu)點(diǎn)：元素存儲(chǔ)區(qū)不固定。
缺點(diǎn)：分二次申請，不易管理

最大區(qū)別：分離式其實(shí)位置（表頭）的地址不變，而一體式，需要整體替換（表頭和數(shù)據(jù)區(qū)）都需要重新申請。

順序表數(shù)據(jù)區(qū)替換與擴(kuò)充

重新擴(kuò)充的兩種策略：

每次擴(kuò)充增加固定數(shù)目的存儲(chǔ)位置，如每次擴(kuò)充增加10個(gè)元素位置，這種策略可稱為線性增長。
特點(diǎn)：節(jié)省空間，但是擴(kuò)充操作頻繁，操作次數(shù)多。

每次擴(kuò)充容量加倍，如每次擴(kuò)充增加一倍存儲(chǔ)空間。
特點(diǎn)：減少了擴(kuò)充操作的執(zhí)行次數(shù)，但可能會(huì)浪費(fèi)空間資源。以空間換時(shí)間，推薦的方式。

順序表的操作

添加元素:

尾端加入元素，時(shí)間復(fù)雜度為O(1)
保序的元素加入，時(shí)間復(fù)雜度為O(n)

刪除元素:

刪除表尾元素，時(shí)間復(fù)雜度為O(1)
保序的元素刪除，時(shí)間復(fù)雜度為O(n)

Python中的list和tuple兩種類型采用了順序表的實(shí)現(xiàn)技術(shù).
list就是一種采用分離式技術(shù)實(shí)現(xiàn)的動(dòng)態(tài)順序表

list實(shí)現(xiàn)采用了如下的策略：在建立空表（或者很小的表）時(shí)，系統(tǒng)分配一塊能容納8個(gè)元素的存儲(chǔ)區(qū)；在執(zhí)行插入操作（insert或append）時(shí)，如果元素存儲(chǔ)區(qū)滿就換一塊4倍大的存儲(chǔ)區(qū)。但如果此時(shí)的表已經(jīng)很大（目前的閥值為50000），則改變策略，采用加一倍的方法。引入這種改變策略的方式，是為了避免出現(xiàn)過多空閑的存儲(chǔ)位置。

為什么需要鏈表

順序表缺點(diǎn)：

需要預(yù)先知道數(shù)據(jù)大小來申請存儲(chǔ)空間

進(jìn)行擴(kuò)充時(shí)需要進(jìn)行數(shù)據(jù)的搬遷

靈活性低

手拉手的方式（線串）去存儲(chǔ)，而非通過元素外置的方式去存儲(chǔ)，元素外置需要預(yù)先知道數(shù)據(jù)大小。

線性表：
一維空間的一條線去組織數(shù)據(jù)，呈線性狀態(tài)。

順序表：將元素順序地存放在一塊連續(xù)的存儲(chǔ)區(qū)里，元素間的順序關(guān)系由它們的存儲(chǔ)順序自然表示。

鏈表：將元素存放在通過鏈接構(gòu)造起來的一系列存儲(chǔ)塊中。

原本的數(shù)據(jù)區(qū)，不單單僅僅存儲(chǔ)數(shù)據(jù)，而會(huì)增加一個(gè)下一個(gè)的單元地址

單鏈表的ADT模型

頭節(jié)點(diǎn)：開始存儲(chǔ)的變量
尾節(jié)點(diǎn)：往后就是空指針

變量p指向鏈表的頭節(jié)點(diǎn)（首節(jié)點(diǎn)）的位置，從p出發(fā)能找到表中的任意節(jié)點(diǎn)。

單鏈表的操作:

is_empty() 鏈表是否為空
length() 鏈表長度
travel() 遍歷整個(gè)鏈表
add(item) 鏈表頭部添加元素
append(item) 鏈表尾部添加元素
insert(pos, item) 指定位置添加元素
remove(item) 刪除節(jié)點(diǎn)
search(item) 查找節(jié)點(diǎn)是否存在

Python中變量標(biāo)識(shí)的本質(zhì): 存儲(chǔ)地址，引用指向到一個(gè)實(shí)際數(shù)據(jù)

單鏈表的實(shí)現(xiàn)

# coding=utf-8
# single_link_list

class Node(object):
    """節(jié)點(diǎn)"""
    def __init__(self, elem):
        self.elem = elem
        self.next = None

# node = Node(100) # 保存  elem, next

class SingleLinkList(object):
    """單鏈表"""
    def __init__(self, node=None):
        self.__head = node # 頭節(jié)點(diǎn)
    def is_empty(self):
        """鏈表是否為空"""
        return self.__head == None

    def length(self):
        """鏈表長度"""
        # 游標(biāo), 指針
        # cur游標(biāo)，用來移動(dòng)遍歷節(jié)點(diǎn)
        cur = self.__head
        # count記錄數(shù)量
        count = 0
        while cur != None: # cur.next == None
            count += 1
            cur = cur.next
        return count

    def travel(self):
        """遍歷整個(gè)鏈表"""
        cur = self.__head
        while cur != None:
            print(cur.elem, end=" ")
            cur = cur.next

    def add(self, item):
        """鏈表頭部添加元素，頭插法"""
        node = Node(item)
        node.next = self.__head # 保證鏈表中的所有關(guān)系不打斷
        self.__head = node

    def append(self, item):
        """鏈表尾部添加元素，尾插法"""
        # item 數(shù)據(jù)元素
        node = Node(item)
        if self.is_empty():
            self.__head = node
        else:     
            cur = self.__head
            while cur.next != None: # 從頭往后走，然后最后掛載一個(gè)新的游標(biāo)
                cur = cur.next
            cur.next = node

    def insert(self, pos, item):
        """指定位置添加元素
            :param pos 從0開始
        """
        if pos < 0:
            self.add(item)
        elif pos > self.length() - 1:
            self.append(item)
        else:
            # pre用來指向指定位置pos的前一個(gè)位置pos-1，初始從頭節(jié)點(diǎn)開始移動(dòng)到指定位置
            pre = self.__head # pre, prior
            count = 0
            while count < pos - 1:
                count += 1
                pre = pre.next
            # 當(dāng)循環(huán)退出后，pre指向pos-1的位置
            node = Node(item)
            # 先將新節(jié)點(diǎn)node的next指向插入位置的節(jié)點(diǎn)
            node.next = pre.next
            # 將插入位置的前一個(gè)節(jié)點(diǎn)的next指向新節(jié)點(diǎn)
            pre.next = node
    def remove(self, item):
        """刪除節(jié)點(diǎn)"""
        # pre 與 cur 二個(gè)游標(biāo)，需要隔開移動(dòng)
        cur = self.__head
        pre = None
        while cur != None:
            if cur.elem == item:
                # 如果第一個(gè)就是刪除的節(jié)點(diǎn)
                if cur == self.__head:
                # 判斷子節(jié)點(diǎn)是否是頭節(jié)點(diǎn)
                    self.__head = cur.next # 將頭指針指向頭節(jié)點(diǎn)的后一個(gè)節(jié)點(diǎn)
                else:
                    # 將刪除位置前一個(gè)節(jié)點(diǎn)的next指向刪除位置的后一個(gè)節(jié)點(diǎn)
                    pre.next = cur.next
                break
            else:
                # 繼續(xù)按鏈表后移節(jié)點(diǎn)
                pre = cur
                cur = cur.next
    def search(self, item):
        """查找節(jié)點(diǎn)是否存在"""
        cur = self.__head
        while cur != None:
            if cur.elem == item:
                return True
            else:
                cur = cur.next
        return False

if __name__ == "__main__":
    sll = SingleLinkList()
    print("is_empty", sll.is_empty())
    print("length", sll.length())
    sll.append(100)
    print("is_empty", sll.is_empty())
    print("length", sll.length())

    sll.append(22)
    sll.add(7)
    sll.append(20)
    sll.insert(2, 777)

    sll.travel()
    sll.remove(7)
    sll.travel()

insert示意圖:

remove示意圖：

后繼結(jié)點(diǎn)：當(dāng)前節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)

單鏈表與順序表的對比

鏈表失去了順序表隨機(jī)讀取的優(yōu)點(diǎn)，同時(shí)鏈表由于增加了節(jié)點(diǎn)的指針域，空間開銷比較大，但對存儲(chǔ)空間的使用要相對靈活。

鏈表與順序表的各種操作復(fù)雜度：

鏈表不能一次性找到位置，都需要通過循環(huán)來找到該位置；而順序表則直接找到位置。

數(shù)據(jù)包含：數(shù)據(jù)區(qū) + 前驅(qū)結(jié)點(diǎn) + 后繼結(jié)點(diǎn)

# coding=utf-8
# double_link_list

class Node(object):
    """節(jié)點(diǎn)"""
    def __init__(self, elem):
        self.elem = elem
        self.next = None
        self.prev = None

class DoubleLinkList(object):
    """雙鏈表"""
    def __init__(self, node=None):
        self.__head = node
    def is_empty(self):
        return self.__head is None

    def length(self):
        count = 0
        cur = self.__head
        while cur != None:
            count += 1
            cur = cur.next
        return count
    def travel(self):
        cur = self.__head
        while cur != None:
            print(cur.elem, end=" ")
            cur = cur.next
        print("")
    def add(self, item):
        node = Node(item)
        node.next = self.__head
        self.__head = node
        node.next.prev = node

    def append(self, item):
        node = Node(item)
        cur = self.__head

        if self.is_empty():
            self.__head = node
        else:    
            while cur.next != None:
                cur = cur.next
            cur.next = node
            node.prev = cur 

    def insert(self, pos, item):
        if pos <= 0:
            self.add(item)
        elif pos > (self.length() - 1):
            self.append(item)
        else:
            cur = self.__head
            count = 0
            while count < pos:
                count += 1
                cur = cur.next
            # 當(dāng)循環(huán)退出的時(shí)候，cur指針指向的就是pos的位置
            node = Node(item)
            # 將node的prev指向cur
            node.next = cur
            #  將node的next指向cur的下一個(gè)節(jié)點(diǎn)
            node.prev = cur.prev # 當(dāng)前節(jié)點(diǎn)的上一個(gè)，指向到插入節(jié)點(diǎn)的前指針
            # 將cur的下一個(gè)節(jié)點(diǎn)的prev指向node
            cur.prev.next = node
            # 將cur的next指向node
            cur.prev = node

    def remove(self, item):
        cur = self.__head
        while cur != None:
            if cur.elem == item:
                if cur == self.__head:
                    self.__head = cur.next
                    if cur.next: # 判斷雙鏈表是否之后一個(gè)節(jié)點(diǎn)
                        cur.next.prve = None
                else:
                    # 將cur的前一個(gè)節(jié)點(diǎn)的next指向cur的后一個(gè)節(jié)點(diǎn)
                    cur.prev.next = cur.next
                    if cur.next:
                        # 將cur的后一個(gè)節(jié)點(diǎn)的prev指向cur的前一個(gè)節(jié)點(diǎn)
                        cur.next.prev = cur.prev
                break
            else:
                cur = cur.next

    def search(self, item):
        cur = self.__head
        while cur != None:
            if cur.elem == item:
                return True
            else:
                cur = cur.next
        return False

if __name__ == "__main__":
    dll = DoubleLinkList()

    print("is_empty", dll.is_empty())
    print("length", dll.length())
    dll.append(100)
    print("is_empty", dll.is_empty())
    print("length", dll.length())

    dll.append(22)
    dll.add(7)
    dll.append(20)
    dll.insert(2, 777)

    dll.travel()
    dll.remove(7)
    dll.travel()

# coding=utf-8
# single_cycle_link_list

class Node(object):
    """節(jié)點(diǎn)"""
    def __init__(self, node):
        self.elem = node
        self.next = None

class SingleCycleLinkList(object):
    """單鏈表"""
    def __init__(self, node=None):
        self.__head = node # 頭節(jié)點(diǎn)
        if node:
            node.next = node

    def is_empty(self):
        """鏈表是否為空"""
        return self.__head == None

    def length(self):
        """鏈表長度"""
        if self.is_empty():
            return 0
        cur = self.__head
        # count記錄數(shù)量
        count = 1 # count從1開始
        while cur.next != self.__head: # cur.next == None
            count += 1
            cur = cur.next
        return count

    def travel(self):
        """遍歷整個(gè)鏈表"""
        if self.is_empty():
            return
        cur = self.__head
        while cur.next != self.__head:
            cur = cur.next
            print(cur.elem, end=" ")
        # print(cur.elem, "-------")
        # print("")

    def add(self, item):
        """鏈表頭部添加元素，頭插法"""
        node = Node(item)
        if self.is_empty():
            # 如果為空，指向節(jié)點(diǎn)，然后節(jié)點(diǎn)的指針指向自己
            self.__head = node
            node.next = node
        else:
            cur = self.__head
            # 指針先移動(dòng)到尾端
            while cur.next != self.__head:
                cur = cur.next
            # 退出循環(huán)，cur指向尾節(jié)點(diǎn)
            # 改變指針指向
            node.next = self.__head
            self.__head = node
            # cur.next = node
            cur.next = node

    def append(self, item):
        """鏈表尾部添加元素，尾插法"""
        node = Node(item)
        if self.is_empty():
            self.__head = node
            node.next = node
        else:
            cur = self.__head
            while cur.next != self.__head:
                cur = cur.next
            node.next = self.__head
            cur.next = node

    def insert(self, pos, item):
        """指定位置添加元素
            :param pos 從0開始
        """
        if pos < 0:
            self.add(item)
        elif pos > (self.length() - 1):
            self.append(item)
        else:
            pre = self.__head
            count = 0
            while count < (pos - 1):
                count += 1
                pre = pre.next
            node = Node(item)
            node.next = pre.next
            pre.next = node

    def remove(self, item):
        """刪除節(jié)點(diǎn)"""
        """
            1. 頭節(jié)點(diǎn)
            2. 尾節(jié)點(diǎn)
            3. 中間節(jié)點(diǎn)
            4. 只存在一個(gè)節(jié)點(diǎn)
            5. 空鏈表
            6. 首節(jié)點(diǎn)就是刪除的節(jié)點(diǎn)
        """
        if self.is_empty():
            return
        cur = self.__head
        pre = None
        while cur.next != self.__head:
            if cur.elem == item:
                if cur == self.__head:
                    # 頭節(jié)點(diǎn)的情況
                    # 找到尾節(jié)點(diǎn)
                    rear = self.__head
                    # 為了順利把尾節(jié)點(diǎn)的指針指向到頭節(jié)點(diǎn)，先把指針便利到尾部
                    while rear.next != self.__head:
                        rear = rear.next
                    self.__head = cur.next
                    rear.next = self.__head
                else:
                    # 中間節(jié)點(diǎn)
                    pre.next = cur.next
                return
            else:
                # 兩個(gè)游標(biāo)順次往鏈表后邊移動(dòng)
                pre = cur
                cur = cur.next
        # 尾部情況
        # 退出循環(huán)，cur指向尾節(jié)點(diǎn)
        if cur.elem == item:
            if self.__head == cur:
                # 只有一個(gè)節(jié)點(diǎn)
                self.__head = None
            else:
                pre.next = cur.next

    def search(self, item):
        """查找節(jié)點(diǎn)是否存在"""
        if self.is_empty():
            return False
        cur = self.__head
        while cur.next != self.__head:
            if cur.elem == item:
                return True
            else:
                cur = cur.next
        # 退出循環(huán)，cur指向尾節(jié)點(diǎn)        
        if cur.elem == item:
            return True
        return False

if __name__ == "__main__":
    scll = SingleCycleLinkList()
    print("is_empty", scll.is_empty())
    print("length", scll.length())

    scll.append(100)
    print("is_empty", scll.is_empty())
    print("length", scll.length())

    scll.append(22)
    scll.add(7)
    scll.append(20)
    scll.insert(2, 777)

    scll.travel()
    scll.remove(7)
    scll.travel()

線性表：順序表（連續(xù)存放），鏈表（離散存放）。存儲(chǔ)線性的數(shù)據(jù)。 --> 解決數(shù)據(jù)怎么存放的問題

棧與隊(duì)列基礎(chǔ)

棧：容器，可以利用線性表的特性，來實(shí)現(xiàn)數(shù)據(jù)的操作。

由于棧數(shù)據(jù)結(jié)構(gòu)只允許在一端進(jìn)行操作，因而按照后進(jìn)先出（LIFO, Last In First Out）的原理運(yùn)作。

棧的實(shí)現(xiàn)

在python的list是順序表，借助list來實(shí)現(xiàn)棧.

棧頂：棧的頭部
棧低：棧的底部

#coding=utf-8


class Stack(object):
    """棧"""
    def __init__(self):
        self.__list = []

    def push(self, item):
        """添加一個(gè)新的元素item到棧頂"""
        self.__list.append(item)
        # 確定是尾部還是頭部插入數(shù)據(jù)
        # 選擇在尾部添加，而非頭部插入，順序表對于尾部操作的時(shí)間復(fù)雜度是O(1)
        # self.__list.insert(0, item)
    def pop(self):
        """彈出棧頂元素"""
        return self.__list.pop()
        # self.__list.pop(0)

    def size(self):
        """返回棧的元素個(gè)數(shù)"""
        return len(self.__list)

    def is_empty(self):
        """判斷棧是否為空"""
        # "", 0, {}, [], ()
        return self.__list == []

    def peek(self):
        """返回棧頂元素"""
        if self.__list:
            return self.__list[-1]
        else:
            return None

if __name__ == "__main__":
    stack = Stack()

    stack.push(11)
    stack.push(1000)
    print(stack.size(), "stack.size()")
    print(stack.pop(), "stack.pop()")

隊(duì)列（queue）是只允許在一端進(jìn)行插入操作，而在另一端進(jìn)行刪除操作的線性表。
隊(duì)列不允許在中間部位進(jìn)行操作。

可以在tree中使用.

隊(duì)列

隊(duì)列頭：取的那一端，叫做隊(duì)頭
隊(duì)列尾：添加隊(duì)一端，叫做隊(duì)尾

隊(duì)列

#coding=utf-8


class Queue(object):
    def __init__(self):
        self.__list = []

    def enqueue(self, item):
        """往隊(duì)列中添加一個(gè)item元素"""
        self.__list.append(item) # 尾部插入
        # self.__list.insert(0, item) # 頭部插入

    def dequeue(self):
        """從隊(duì)列頭部刪除一個(gè)元素"""
        return self.__list.pop(0) # 尾部刪除
        # return self.__list.pop() # 頭部刪除

    def is_empty(self):
        """判斷一個(gè)隊(duì)列是否為空"""
        return not self.__list

    def size(self):
        """返回隊(duì)列的大小"""
        return len(self.__list)

if __name__ == "__main__":

    queue = Queue()
    queue.enqueue(10)
    queue.enqueue(13)

    print(queue.size())
    print(queue.dequeue())

雙端隊(duì)列

兩端都可以出隊(duì)列，也都可以入隊(duì)列。

#coding=utf-8

class Dqueue(object):
    """雙端隊(duì)列"""
    def __init__(self):
        self.__list = []

    def add_front(self, item):
        """添加一個(gè)新的元素item到棧頂"""
        self.__list.insert(0, item) # 頭部添加

    def add_rear(self, item):
        self.__list.append(item) # 尾部添加

    def pop_fornt(self):
        return self.__list.pop(0)
    
    def pop_rear(self):
        return self.__list.pop()

    def size(self):
        """返回棧的元素個(gè)數(shù)"""
        return len(self.__list)

    def is_empty(self):
        """判斷棧是否為空"""
        # "", 0, {}, [], ()
        return self.__list == []

if __name__ == "__main__":
    dq = Dqueue()

    dq.add_front(11)
    dq.add_front(100)
    dq.add_rear(1000)
    print(dq.size(), "dq.size()")
    print(dq.pop_fornt(), "dq.pop_fornt()")

排序算法：是一種能將一串?dāng)?shù)據(jù)依照特定順序進(jìn)行排列的一種算法。

排序算法的穩(wěn)定性

穩(wěn)定排序算法會(huì)讓原本有相等鍵值的記錄維持相對次序。也就是如果一個(gè)排序算法是穩(wěn)定的，當(dāng)有兩個(gè)相等鍵值的紀(jì)錄R和S，且在原本的列表中R出現(xiàn)在S之前，在排序過的列表中R也將會(huì)是在S之前。（特指排序條件相等的兩個(gè)元素，排序后的順序是否和排序前一致。有時(shí)候需要按照多個(gè)條件排序）

如果排序算法是穩(wěn)定的，可以先按照第一個(gè)條件排序后再按照其它條件排序，則結(jié)果就是想要的。若果是不穩(wěn)定的排序，需要額外的步驟保證結(jié)果的正確性。

冒泡排序

比較相鄰的元素。如果第一個(gè)比第二個(gè)大（升序），就交換它們兩個(gè)。

對每一對相鄰元素作同樣的工作，從開始第一對到結(jié)尾的最后一對。這步做完后，最后的元素會(huì)是最大的數(shù)。

針對所有的元素重復(fù)以上的步驟，除了最后一個(gè)。

持續(xù)每次對越來越少的元素重復(fù)上面的步驟，直到?jīng)]有任何一對數(shù)字需要比較。

#condig-utf8

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]:
                # 位置調(diào)換
                alist[i], alist[i+1] = alist[i+1], alist[i]
                count += 1
        if 0 == count: # 常量 ，變量
            return

    # i 0 ~ n-2  range(0, n-1) j=0
    # i 1 ~ n-3  range(0, n-1-1) j=1
    # i 2 ~ n-4  range(0, n-1-1-1) j=2
    # j=n i range(0, n-1-j)

if __name__ == "__main__":
    li = [54, 26, 93, 17, 77, 34]
    bubble_sort(li)
    print(li)

時(shí)間復(fù)雜度：

最優(yōu)時(shí)間復(fù)雜度：O(n) （表示遍歷一次發(fā)現(xiàn)沒有任何可以交換的元素，排序結(jié)束。）

最壞時(shí)間復(fù)雜度：O(n^2)

穩(wěn)定性：穩(wěn)定

選擇排序

從未排序的列表中選擇一個(gè)最小的排到前面去

# alist = [12, 34, 3453, 456, 4, 45, 2, 5, 100]
#           0   1   2    3    4   5  6  7  8

# min = 0
# min = 6
# alist[0], alist[6] = alist[6], alist[0]



# alist = [2,     34, 3453, 456, 4, 45, 12, 5, 100]
#           0      1    2    3   4  5    6  7   8

# min = 1
# min = 4
# alist[1], alist[4] = alist[4], alist[1]

# 從未排序的列表中選擇一個(gè)最小的排到前面去


# 選擇排序，看未排序的后邊部分

# 插入排序，把未排序的序列放在，已經(jīng)排序的序列那一個(gè)位置中。

# 比較的位置
# j = 0
# min = 0 + 1

# j = 1
# min = 1 + 1

alist = [12, 34, 3453, 456, 4, 45, 2, 5, 100]

def select_sort(alist):
  """選擇排序"""
  n = len(alist)

  for j in range(0, n-1): # 產(chǎn)生n-2, 這邊需要寫n-1, 及 (0 ~ n-2)
    min_index = j
    for i in range(j+1, n): # 需要到 (n-1) 的位置  時(shí)間復(fù)雜度：1-n, 2-n, 3-n
    # 分為左右兩邊，完成的序列 和 未完成的序列
      if alist[min_index] > alist[i]:
        min_index = i
    alist[j], alist[min_index] = alist[min_index], alist[j]


print(alist)
select_sort(alist)
print(alist)

時(shí)間復(fù)雜度：

最優(yōu)時(shí)間復(fù)雜度：O(n^2)

最壞時(shí)間復(fù)雜度：O(n^2)

穩(wěn)定性：不穩(wěn)定（考慮升序每次選擇最大的情況）

相同數(shù)據(jù)中，排列之后的位置一樣，具有穩(wěn)定性。

插入排序

#coding=utf-8

li = [54, 26, 93, 17, 77, 34]

# 后續(xù)的無需序列，與前面的有序序列中的最后一個(gè)元素比較

def insert_sort(alist):
    n = len(alist)
    # 從右邊的無序序列中取出多少個(gè)元素執(zhí)行這個(gè)的過程
    for j in range(0, n):
        i = j
        # 執(zhí)行從右邊的無序序列中取出第一個(gè)元素，即i位置的元素，然后將其插入到前面正確的位置中
        while i > 0: 
            if alist[i] < alist[i-1]:
                alist[i], alist[i-1] = alist[i-1], alist[i]
                i -= 1
            else:
                break

print(li)
insert_sort(li)
print(li)

時(shí)間復(fù)雜度：

最優(yōu)時(shí)間復(fù)雜度：O(n) （升序排列，序列已經(jīng)處于升序狀態(tài)）

最壞時(shí)間復(fù)雜度：O(n^2)

穩(wěn)定性：穩(wěn)定

希爾排序

插入排序的改進(jìn)版本

#coding=utf-8
alist = [12, 34, 3453, 456, 4, 45, 2, 5, 100]

def shell_sort(alist):
    """希爾排序"""
    n = len(alist) # n = 9
    gap = n // 2 # n = 4

    # i = 1
    # i = gap
    # gap變化到0之前，插入算法執(zhí)行到次數(shù)
    while gap > 0: # 可以等于0
        # 希爾算法 與普通的 插入算法的區(qū)別就是 gap 步長
        for j in range(gap, n): # 一次性循環(huán)全部處理完成
            # 控制子序列中的所有元素
            # j = [gap, gap+1, gap+2, gap+3, ... , n-1]
            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 # 縮短gap步長


print(alist)
shell_sort(alist)
print(alist)

時(shí)間復(fù)雜度：

最優(yōu)時(shí)間復(fù)雜度：根據(jù)步長序列的不同而不同

最壞時(shí)間復(fù)雜度：O(n^2)

穩(wěn)定性：不穩(wěn)定

快速排序

一個(gè)數(shù)字，在序列的那個(gè)位置。按照當(dāng)前的數(shù)字，每次分開兩部分。

步驟：

從數(shù)列中挑出一個(gè)元素，稱為"基準(zhǔn)"（pivot），

重新排序數(shù)列，所有元素比基準(zhǔn)值小的擺放在基準(zhǔn)前面，所有元素比基準(zhǔn)值大的擺在基準(zhǔn)的后面（相同的數(shù)可以到任一邊）。在這個(gè)分區(qū)結(jié)束之后，該基準(zhǔn)就處于數(shù)列的中間位置。這個(gè)稱為分區(qū)（partition）操作。

遞歸地（recursive）把小于基準(zhǔn)值元素的子數(shù)列和大于基準(zhǔn)值元素的子數(shù)列排序。

核心代碼:
取第一個(gè)位置保存中間值(middle_value), 第一個(gè)位置是空位置，就該high的位置來判斷了，當(dāng)合適就換位置，并且移動(dòng)對方的指針（low），當(dāng)不合適移動(dòng)當(dāng)前指針(high)。

middle_value = 10

low = 0
high = len(list)

if alist[high] < middle_value:
    alist[low] = alist[high]
    low += 1
elif alist[high] > middle_value:
    high -= 1
    
if alist[low] < middle_value:
    alist[high] = alist[low]
    hight -= 1
elif alist[low] > middle_value:
    low += 1
    
if low == high:    
    alist[low] = middle_value            

#conding=utf-8

def quick_sort(alist, first, last):
    """快速排序"""
    if first >= last:
        return

    # mid_value = alist[0] # 中間值
    mid_value = alist[first] # 中間值
    # n = len(alist)
    # 左右游標(biāo)
    # low = 0
    low = first
    # high = n-1
    high = last

    while low < high:
        # high 游標(biāo) 左移動(dòng)
        while low < high and alist[high] >= mid_value:
            high -= 1
        alist[low] = alist[high]
        # low += 1

        # low 游標(biāo) 右移動(dòng)
        while low < high and alist[low] < mid_value:
            low += 1
        alist[high] = alist[low]
        # high -= 1

        # 等于的情況放到其中一邊去處理
        # 為了保證二個(gè)指針不錯(cuò)過，注釋 【low += 1】和 【high -= 1】

    # 退出循環(huán)的時(shí)候，low == high
    alist[low] = mid_value # 中間值賦值到該位置

    # 遞歸
    # 對low左邊的列表執(zhí)行快速排序
    quick_sort(alist, first, low-1)
    # 對low右邊的列表執(zhí)行快速排序
    quick_sort(alist, low+1, last)

if __name__ == "__main__":
    li = [54, 26, 93, 17, 77, 34]
    print(li)
    quick_sort(li, 0, len(li)-1)
    print(li)

時(shí)間復(fù)雜度：

最優(yōu)時(shí)間復(fù)雜度：O(nlogn): 2*2*2... = n, n個(gè)元素對2取對數(shù)。 log2(n)以2為底的對數(shù)

最壞時(shí)間復(fù)雜度：O(n^2)

穩(wěn)定性：不穩(wěn)定

時(shí)間復(fù)雜度不好從代碼中分析，通過畫圖中理解每次循環(huán)中操作。橫向和縱向來區(qū)分判斷。

歸并排序

先把序列從頭開始往下拆，直到只有一個(gè)元素。緊接著開始，二個(gè)部分合并到一起，然后再次合并，直到完成序列合并。

需要使用到遞歸。

#coding=utf-8

def merge_sort(alist):
  """歸并排序"""

  """
    分裂
  """
  n = len(alist)
  if n <= 1:
    return alist
  mid = n // 2
  # left, right 采用歸并排序后形成的有序的新的列表
  left_li = merge_sort(alist[:mid]) # 傳新的列表
  right_li = merge_sort(alist[mid:])

  """
    合并
  """
  # 將兩個(gè)有序的子序列合并為一個(gè)新的整體
  # merge(left, right)
  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:] # 加上剩下數(shù)據(jù)
  result += right_li[right_pointer:]
  return result

alist = [1, 23, 34, 6,2, 12, 12, 1, 2]
print(alist)
new_alist = merge_sort(alist) # 返回新的列表
print(new_alist)

時(shí)間復(fù)雜度：

最優(yōu)時(shí)間復(fù)雜度：O(nlogn), 2*2*2... = n, n個(gè)元素對2取對數(shù)。 log2(n)以2為底的對數(shù)

最壞時(shí)間復(fù)雜度：O(nlogn)

穩(wěn)定性：穩(wěn)定

搜索：在一個(gè)項(xiàng)目集合中找到特定項(xiàng)目的算法過程。
搜索結(jié)果：通常的答案是真或假,因?yàn)樵擁?xiàng)目是否存在。

常見搜索方法：順序查找，二分法查找，二叉樹查找，哈希查找

二分查找

二分查找，需要定位到索引，也就是說，只能作用到順序表上，而且是排序過后的，有序順序表中。

非遞歸實(shí)現(xiàn)
需要關(guān)注：頭和尾的下標(biāo)，來計(jì)算二分位置的下標(biāo)。（原因在原有的列表上去找）
指明查找的范圍，需要二個(gè)指針來控制前后移動(dòng)

def binary_search_2(alist, item):
  """二分查找"""
  n = len(alist)
  first = 0
  last = n - 1
  while first <= last: # 中間最小之后一個(gè)值，需要包含等于
    mid = (first + last) // 2
    if alist[mid] == item:
      return True
    elif item < alist[mid]:
      last = mid - 1
    else:
      first = mid + 1
  return False

遞歸實(shí)現(xiàn)

def binary_search(alist, item):
  """二分查找"""
  n = len(alist)
  if n > 0:
    mid = n//2 # 新的列表

    if alist[mid] == item:
      return True
    elif item < alist[mid]:
      return binary_search(alist[:mid], item)
    else:
      return binary_search(alist[mid+1:], item)
  return False

時(shí)間復(fù)雜度：

最優(yōu)時(shí)間復(fù)雜度：O(1)

最壞時(shí)間復(fù)雜度：O(logn)

用來模擬具有樹狀結(jié)構(gòu)性質(zhì)的數(shù)據(jù)集合，它是由n(n>=1)個(gè)有限節(jié)點(diǎn)組成一個(gè)具有層次關(guān)系的集合。

二叉樹是二維空間上的表現(xiàn)，圖是三維空間上的表現(xiàn)。

特點(diǎn)：

每個(gè)節(jié)點(diǎn)有零個(gè)或多個(gè)子節(jié)點(diǎn)（每個(gè)節(jié)點(diǎn)都會(huì)有數(shù)據(jù)區(qū)和鏈接區(qū)）

沒有父節(jié)點(diǎn)的節(jié)點(diǎn)稱為根節(jié)點(diǎn)

每一個(gè)非根節(jié)點(diǎn)有且只有一個(gè)父節(jié)點(diǎn)

除了根節(jié)點(diǎn)外，每個(gè)子節(jié)點(diǎn)可以分為多個(gè)不相交的子樹(每個(gè)節(jié)點(diǎn)只有一個(gè)父級)

樹的術(shù)語

節(jié)點(diǎn)的度：一個(gè)節(jié)點(diǎn)含有的子樹的個(gè)數(shù)稱為該節(jié)點(diǎn)的度（有幾個(gè)下級，幾個(gè)下級子節(jié)點(diǎn)）

樹的度：一棵樹中，最大的節(jié)點(diǎn)的度稱為樹的度；

葉節(jié)點(diǎn)或終端節(jié)點(diǎn)：度為零的節(jié)點(diǎn)；

父親節(jié)點(diǎn)或父節(jié)點(diǎn)：若一個(gè)節(jié)點(diǎn)含有子節(jié)點(diǎn)，則這個(gè)節(jié)點(diǎn)稱為其子節(jié)點(diǎn)的父節(jié)點(diǎn)；

孩子節(jié)點(diǎn)或子節(jié)點(diǎn)：一個(gè)節(jié)點(diǎn)含有的子樹的根節(jié)點(diǎn)稱為該節(jié)點(diǎn)的子節(jié)點(diǎn)；

兄弟節(jié)點(diǎn)：具有相同父節(jié)點(diǎn)的節(jié)點(diǎn)互稱為兄弟節(jié)點(diǎn)；

節(jié)點(diǎn)的層次：從根開始定義起，根為第1層，根的子節(jié)點(diǎn)為第2層，以此類推；

樹的高度或深度：樹中節(jié)點(diǎn)的最大層次；

堂兄弟節(jié)點(diǎn)：父節(jié)點(diǎn)在同一層的節(jié)點(diǎn)互為堂兄弟；

節(jié)點(diǎn)的祖先：從根到該節(jié)點(diǎn)所經(jīng)分支上的所有節(jié)點(diǎn)；

子孫：以某節(jié)點(diǎn)為根的子樹中任一節(jié)點(diǎn)都稱為該節(jié)點(diǎn)的子孫。

森林：由m（m>=0）棵互不相交的樹的集合稱為森林；

樹的種類

無序樹：樹中任意節(jié)點(diǎn)的子節(jié)點(diǎn)之間沒有順序關(guān)系，這種樹稱為無序樹，也稱為自由樹；

有序樹：樹中任意節(jié)點(diǎn)的子節(jié)點(diǎn)之間有順序關(guān)系（樹的節(jié)點(diǎn)直接有某種特殊的意義在），這種樹稱為有序樹；

二叉樹：每個(gè)節(jié)點(diǎn)最多含有兩個(gè)子樹的樹稱為二叉樹（節(jié)點(diǎn)的度最高到2）

完全二叉樹：對于一顆二叉樹，假設(shè)其深度為d(d>1)。除了第d層外，其它各層的節(jié)點(diǎn)數(shù)目均已達(dá)最大值，且第d層所有節(jié)點(diǎn)從左向右連續(xù)地緊密排列，這樣的二叉樹被稱為完全二叉樹，其中滿二叉樹的定義是所有葉節(jié)點(diǎn)都在最底層的完全二叉樹

平衡二叉樹（AVL樹）：當(dāng)且僅當(dāng)任何節(jié)點(diǎn)的兩棵子樹的高度差不大于1的二叉樹

排序二叉樹（二叉查找樹（英語：Binary Search Tree），也稱二叉搜索樹、有序二叉樹）

霍夫曼樹（用于信息編碼）：帶權(quán)路徑最短的二叉樹稱為哈夫曼樹或最優(yōu)二叉樹

B樹：一種對讀寫操作進(jìn)行優(yōu)化的自平衡的二叉查找樹，能夠保持?jǐn)?shù)據(jù)有序，擁有多余兩個(gè)子樹

樹的存儲(chǔ)與表示

雖然樹是二維的，但是可以用一維的順序表存儲(chǔ)起來。

順序存儲(chǔ)：將數(shù)據(jù)結(jié)構(gòu)存儲(chǔ)在固定的數(shù)組中，然在遍歷速度上有一定的優(yōu)勢，但因所占空間比較大，是非主流二叉樹。二叉樹通常以鏈?zhǔn)酱鎯?chǔ)。(把連續(xù)的空間和樹上的節(jié)點(diǎn)做對應(yīng)關(guān)系。按照節(jié)點(diǎn)的層次來存儲(chǔ)數(shù)據(jù))

鏈?zhǔn)酱鎯?chǔ)：缺陷，指針域指針個(gè)數(shù)不定

由于對節(jié)點(diǎn)的個(gè)數(shù)無法掌握，常見樹的存儲(chǔ)表示都轉(zhuǎn)換成二叉樹進(jìn)行處理，子節(jié)點(diǎn)個(gè)數(shù)最多為2

最常用的樹的存儲(chǔ)，是鏈?zhǔn)酱鎯?chǔ)，多存儲(chǔ)后記鏈接區(qū)。

常見應(yīng)用場景

xml，html等，那么編寫這些東西的解析器的時(shí)候，不可避免用到樹

路由協(xié)議就是使用了樹的算法

mysql數(shù)據(jù)庫索引

文件系統(tǒng)的目錄結(jié)構(gòu)

所以很多經(jīng)典的AI算法其實(shí)都是樹搜索，此外機(jī)器學(xué)習(xí)中的decision tree也是樹結(jié)構(gòu)

二叉樹介紹

每個(gè)節(jié)點(diǎn)最多有兩個(gè)子樹的樹結(jié)構(gòu)。(最大的度只能是2)
通常子樹被稱作“左子樹”（left subtree）和“右子樹”（right subtree）

二叉樹的數(shù)學(xué)上的一些性質(zhì)(特性)

在二叉樹的第i層上至多有2^(i-1)個(gè)結(jié)點(diǎn)（i>0）

深度為k的二叉樹至多有2^k - 1個(gè)結(jié)點(diǎn)（k>0）

對于任意一棵二叉樹，如果其葉結(jié)點(diǎn)數(shù)為N0（度數(shù)為0），而度數(shù)為2的結(jié)點(diǎn)總數(shù)為N2，則N0=N2+1;

具有n個(gè)結(jié)點(diǎn)的完全二叉樹的深度必為 log2(n+1)(和特性2在數(shù)學(xué)上是相反的)

對完全二叉樹，若從上至下、從左至右編號(hào)，則編號(hào)為i 的結(jié)點(diǎn)，其左孩子編號(hào)必為2i，其右孩子編號(hào)必為2i＋1；其雙親的編號(hào)必為i/2（i＝1 時(shí)為根,除外）

二叉樹的實(shí)現(xiàn)

添加的方式：二叉樹的廣度優(yōu)先遍歷（廣度層次遍歷），通過隊(duì)列，取出頭的元素，判斷是否有左子節(jié)點(diǎn)與右子節(jié)點(diǎn)，如果都有往隊(duì)列中添加，如果沒有，掛載到節(jié)點(diǎn)上。

深度遍歷：

先序遍歷（從最小的三個(gè)節(jié)點(diǎn)二叉樹的先根節(jié)點(diǎn)遍歷，左子節(jié)點(diǎn)，右子節(jié)點(diǎn)的遍歷）-> 根，左，右

中序遍歷（把根放到中間，就是左子節(jié)點(diǎn)，根，右子節(jié)點(diǎn)的順序遍歷）-> 左，根，右

后序遍歷（把根放到最后一個(gè)上面，左子節(jié)點(diǎn)，右子節(jié)點(diǎn)的順序遍歷）-> 左，右，根

無論把根放到那個(gè)位置上，子節(jié)點(diǎn)都是先左邊后右邊

#coding=utf-8

class Node(object):
    """節(jié)點(diǎn)類"""
    def __init__(self, item):
        self.elem = item
        self.lchild = None
        self.rchild = None

class Tree(object):
    """二叉樹"""
    def __init__(self):
        self.root = None        

    # 插入 （廣度優(yōu)先遍歷）
    def add (self, item):
        node = Node(item)
        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.elem, end=" ")
            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): # 中序，先序，后序，根節(jié)點(diǎn)都在變化，為了調(diào)用自身，而且是調(diào)用不同的子樹，所以根節(jié)點(diǎn)作為參數(shù)傳入
        """先序遍歷"""
        if node is None:
            return
        print(node.elem, end=" ") # 根
        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.postorder(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()
    print(" ")
    tree.preorder(tree.root)
    print(" ")
    tree.inorder(tree.root)
    print(" ")
    tree.postorder(tree.root)
    print(" ")

層次遍歷： 0 1 2 3 4 5 6 7 8 9
先序遍歷： 0 1 3 7 8 4 9 2 5 6
中序遍歷： 7 3 8 1 9 4 0 5 2 6
后序遍歷： 7 8 3 9 4 1 5 6 2 0

給出遍歷結(jié)果，然后確定一顆二叉樹。給其中二個(gè)種遍歷結(jié)果，就可以寫出二叉樹（先序和中序，或者，中序和后序），一定需要一個(gè)中序，不然，左右子樹無法分開。