1. 數(shù)據(jù)結(jié)構(gòu)

1.1 數(shù)據(jù)結(jié)構(gòu)概述

1.1.1 數(shù)據(jù)結(jié)構(gòu)描述

【1】概述
    1.1) 在工作中残炮，我們?yōu)榱私鉀Q問題颤殴，需要將數(shù)據(jù)保存下來傀蚌，然后根據(jù)數(shù)據(jù)存儲方式設(shè)計算法進(jìn)行處理铅忿，根據(jù)數(shù)據(jù)的存儲方式我們使用不同的算法處理，而我們現(xiàn)在需要考慮算法解決問題的效率問題谎亩，所以需要考慮數(shù)據(jù)究竟如何保存予借，這就是數(shù)據(jù)結(jié)構(gòu)
  
【2】概念
    2.1) 數(shù)據(jù)是一個抽象的概念，將其進(jìn)行分類后得到程序設(shè)計語言中的基本類型昌跌，如：list仰禀、tuple等。數(shù)據(jù)元素之間不是獨立的蚕愤，存在特定的關(guān)系答恶，這些關(guān)系便是結(jié)構(gòu)。數(shù)據(jù)結(jié)構(gòu)指數(shù)據(jù)對象中數(shù)據(jù)元素之間的關(guān)系
    2.2) Python提供了很多現(xiàn)成的數(shù)據(jù)結(jié)構(gòu)類型萍诱，如列表悬嗓、元組、字典等裕坊，無須我們自己去定義包竹，而Python沒有定義的，就需要我們自己去定義實現(xiàn)這些數(shù)據(jù)的組織方式籍凝，稱為Python擴(kuò)展數(shù)據(jù)結(jié)構(gòu)周瞎，如：棧、隊列等

【3】為什么學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)
   在真正的項目開發(fā)中饵蒂，大部分時間都是從數(shù)據(jù)庫取數(shù)據(jù) -> 數(shù)據(jù)操作和結(jié)構(gòu)化 -> 返回給前端声诸，在數(shù)據(jù)操作過程中需要合理地抽象，組織苹享、處理數(shù)據(jù)双絮，如果選用了錯誤的數(shù)據(jù)結(jié)構(gòu)，就會造成代碼運行低效

1.1.2 數(shù)據(jù)結(jié)構(gòu)分類

【1】線性結(jié)構(gòu) : n個數(shù)據(jù)元素的有序集合
    1.2) 順序表 : 將數(shù)據(jù)結(jié)構(gòu)中各元素按照其邏輯順序存放于存儲器一片連續(xù)的存儲空間中
    1.3) 鏈表   : 將數(shù)據(jù)結(jié)構(gòu)中各元素分布到存儲器的不同點得问，用記錄下一個結(jié)點位置的方式建立它們之間的聯(lián)系
    1.4) 棧 : 后進(jìn)先出
    1.5) 隊列 : 先進(jìn)先出
    
【2】非線性結(jié)構(gòu)
    2.1) 樹形結(jié)構(gòu)
    2.2) 圖狀結(jié)構(gòu)

1.2 抽象數(shù)據(jù)類型

【1】定義
    抽象數(shù)據(jù)類型是指一個數(shù)學(xué)模型以及定義在此數(shù)學(xué)模型上的一組操作囤攀，及把數(shù)據(jù)類型和數(shù)據(jù)類型上的運算捆在一起進(jìn)行封裝。引入抽象數(shù)據(jù)類型的目的是把數(shù)據(jù)類型的表示和數(shù)據(jù)類型上的運算的實現(xiàn)與這些數(shù)據(jù)類型和運算在程序中的引用隔開宫纬，使他們相互獨立

【2】描述
    把原有的基本數(shù)據(jù)和這個數(shù)據(jù)所支持的操作放到一起焚挠，形成一個整體

【3】最常用的數(shù)據(jù)運算
    3.1) 插入
    3.2) 刪除
    3.3) 修改
    3.4) 查找
    3.5) 排序

1.3 順序表

3.1 順序表的基本形式

【1】特點 : 內(nèi)存連續(xù)
【2】分類
    2.1) 基本形式: 數(shù)據(jù)元素本身連續(xù)存儲,每個元素所占存儲單元大小固定相同
    2.2) 元素外置: 數(shù)據(jù)元素不連續(xù)存儲，地址單元連續(xù)存儲

1.4 鏈表

1.4.1 定義

【1】特點:
    1.1) 內(nèi)存不連續(xù)的漓骚，而是一個個串起來的蝌衔，需要每個鏈表的節(jié)點保存一個指向下一個節(jié)點的指針
  
【2】和順序表的對比
    2.1) 順序表的構(gòu)建需要預(yù)先知道數(shù)據(jù)大小來申請連續(xù)的存儲空間，而在進(jìn)行擴(kuò)充時又需要進(jìn)行數(shù)據(jù)的搬遷蝌蹂，使用起來不靈活噩斟，而鏈表結(jié)構(gòu)可以充分利用計算機(jī)的內(nèi)存空間，實現(xiàn)靈活的內(nèi)存動態(tài)管理

示例 - 強(qiáng)化理解

將線性表L=(a0,a1,……,an-1)中各元素分布在存儲器的不同存儲塊孤个，稱為結(jié)點剃允，每個結(jié)點（尾節(jié)點除外）中都持有一個指向下一個節(jié)點的引用，這樣所得到的存儲結(jié)構(gòu)為鏈表結(jié)構(gòu)

1.4.2 單鏈表代碼實現(xiàn)

"""
python實現(xiàn)單鏈表
"""
class Node:
    """節(jié)點類:生成節(jié)點的超級工廠"""
    def __init__(self, value):
        self.value = value
        self.next = None

class SingleLinkList:
    """單鏈表類:數(shù)學(xué)模型"""
    def __init__(self):
        """初始化一個空鏈表:頭節(jié)點為None的鏈表為空鏈表"""
        self.head = None

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

    def travel(self):
        """遍歷整個鏈表"""
        cur = self.head
        while cur:
            print(cur.value, end=' ')
            cur = cur.next
        # 打印空行
        print()

    def append(self, item):
        """在鏈表尾部添加一個節(jié)點"""
        node = Node(item)
        # 情況1: 空鏈表情況
        if self.is_empty():
            self.head = node
            return
        # 情況2: 非空鏈表情況
        cur = self.head
        while cur.next:
            cur = cur.next
        # while循環(huán)結(jié)束后,cur指向尾節(jié)點的位置
        cur.next = node
        node.next = None

    def add(self, item):
        """在鏈表頭部添加一個節(jié)點"""
        node = Node(item)
        node.next = self.head
        self.head = node

    def remove(self, item):
        """刪除鏈表中的某個節(jié)點"""
        # 定義兩個游標(biāo)
        cur = self.head
        pre = None
        while cur:
            if cur.value != item:
                pre = cur
                cur = cur.next
            else:
                pre.next = cur.next
                break

    def remove_head(self):
        """刪除鏈表頭節(jié)點"""
        if self.is_empty():
            return

        self.head = self.head.next

if __name__ == '__main__':
    s = SingleLinkList()
    # 終端1: True
    print(s.is_empty())
    # 鏈表: 100 -> 200 -> 300 -> 400 -> None
    s.add(200)
    s.add(100)
    s.append(300)
    s.append(400)
    # 終端2: 100 200 300 400
    s.travel()
    # 終端3: False
    print(s.is_empty())
    # 鏈表: 100 -> 200 -> 400 -> None
    s.remove(300)
    # 終端4: 100 200 400
    s.travel()
    # 鏈表: 200->400->None
    s.remove_head()
    # 終端5: 200 400
    s.travel()

1.4.3 鏈表練習(xí)一

• 題目

  【1】題目描述
      輸入一個鏈表齐鲤，反轉(zhuǎn)鏈表后斥废，輸出新鏈表的表頭
    
  【2】試題解析
      可以將鏈表的每一個節(jié)點取出來，插入到新的鏈表表頭给郊，同時要保存原鏈表的下一個節(jié)點
  

• 代碼實現(xiàn)

  """
  輸入一個鏈表牡肉，反轉(zhuǎn)鏈表后，輸出新鏈表的表頭
  思路:
      1淆九、創(chuàng)建2個游標(biāo),代表要進(jìn)行反轉(zhuǎn)操作的節(jié)點 和 上一個節(jié)點
      2统锤、代碼邏輯:
         當(dāng)前節(jié)點指針指向上一個節(jié)點
         兩個游標(biāo)同時往后移動
         結(jié)束標(biāo)準(zhǔn): 當(dāng)要操作的節(jié)點為None時,結(jié)束! 此時pre代表的是新鏈表的頭節(jié)點
  """
  class Node:
      def __init__(self, value):
          self.value = value
          self.next = None
  
  class Solution:
      def reverse_link_list(self, head):
          # 1、空鏈表情況
          if head == None:
              return
          # 2吩屹、非空鏈表情況
          pre = None
          cur = head
          while cur:
              # 記錄下一個要操作反轉(zhuǎn)的節(jié)點
              next_node = cur.next
              # 反轉(zhuǎn)節(jié)點cur,并移動兩個游標(biāo)
              cur.next = pre
              pre = cur
              cur = next_node
  
          return pre.value
  
  if __name__ == '__main__':
      s = Solution()
      # 1跪另、空鏈表情況
      head = None
      print(s.reverse_link_list(head))
      # 2、只有1個節(jié)點情況
      head = Node(100)
      print(s.reverse_link_list(head))
      # 3煤搜、有多個節(jié)點情況
      head = Node(100)
      head.next = Node(200)
      head.next.next = Node(300)
      print(s.reverse_link_list(head))
  

1.4.4 鏈表練習(xí)二

• **題目描述 **

  【1】題目描述
      輸入兩個單調(diào)遞增的鏈表免绿，輸出兩個鏈表合成后的鏈表，當(dāng)然我們需要合成后的鏈表滿足單調(diào)不減規(guī)則
    
  【2】試題解析
      a> 比較兩個鏈表的頭節(jié)點擦盾，確認(rèn)合成后鏈表的頭節(jié)點
      b> 繼續(xù)依次比較兩個鏈表元素的大小嘲驾，將元素小的結(jié)點插入到新的鏈表中，直到一個鏈 表為空
  

• 代碼實現(xiàn)

  """
  輸入兩個單調(diào)遞增的鏈表迹卢，輸出兩個鏈表合成后的鏈表辽故，當(dāng)然我們需要合成后的鏈表滿足單調(diào)不減規(guī)則
  思路:
      1、程序最終返回的是: 合并后的鏈表的頭節(jié)點
      2腐碱、先確定新鏈表的頭節(jié)點
      3誊垢、互相比較,移動值小的游標(biāo)
  """
  class Node:
      """節(jié)點類"""
      def __init__(self, value):
          self.value = value
          self.next = None
  
  class Solution:
      def merge_two_link_list(self, head1, head2):
          # 1.確定新鏈表頭節(jié)點
          h1 = head1
          h2 = head2
          if h1.value >= h2.value:
              newhead = h2
              h2 = h2.next
          else:
              newhead = h1
              h1 = h1.next
          # 2.依次循環(huán)比較其他節(jié)點
          newcur = newhead
          while h1 and h2:
              if h1.value <= h2.value:
                  newcur.next = h1
                  newcur = newcur.next
                  h1 = h1.next
              else:
                  newcur.next = h2
                  newcur = newcur.next
                  h2 = h2.next
          # 循環(huán)結(jié)束,h1或h2一定有一個為None
          # 將newcur指向不為None的那個
          if h1:
              newcur.next = h1
          else:
              newcur.next = h2
  
          return newhead
  
  if __name__ == '__main__':
      s = Solution()
      # 鏈表1: 100 200 300 400 None
      head1 = Node(100)
      head1.next = Node(200)
      head1.next.next = Node(300)
      head1.next.next.next = Node(400)
      # 鏈表2: 1 200 600 800 None
      head2 = Node(1)
      head2.next = Node(200)
      head2.next.next = Node(600)
      head2.next.next.next = Node(800)
      # 測試方法
      newhead = s.merge_two_link_list(head1, head2)
      print(newhead.value)
      while newhead:
          print(newhead.value, end=" ")
          newhead = newhead.next
  

1.5 棧（LIFO)

1.5.1 定義

棧是限制在一端進(jìn)行插入操作和刪除操作的線性表（俗稱堆棧）掉弛，允許進(jìn)行操作的一端稱為"棧頂"，另一固定端稱為"棧底"喂走，當(dāng)棧中沒有元素時稱為"空棧"

1.5.2 特點

【1】棧只能在一端進(jìn)行數(shù)據(jù)操作
【2】棧模型具有后進(jìn)先出的規(guī)律（LIFO）

1.5.3 順序棧代碼實現(xiàn)

"""
順序存儲的方式實現(xiàn)棧
思路：
    1殃饿、棧 ：LIFO 后進(jìn)先出
    2、設(shè)計
       列表尾部作為棧頂（入棧芋肠、出棧操作）
       列表頭部作為棧底（不進(jìn)行任何操作）
"""
class Stack:
    def __init__(self):
        """初始化一個空棧"""
        self.elems = []

    def is_empty(self):
        """判斷棧是否為空棧"""
        return self.elems == []

    def push(self, item):
        """入棧: 相當(dāng)于在鏈表尾部添加1個元素"""
        self.elems.append(item)

    def destack(self):
        """出棧: 相當(dāng)于在列表尾部彈出1個元素"""
        if self.is_empty():
            raise Exception('destack from empty stack')
        return self.elems.pop()

if __name__ == '__main__':
    s = Stack()
    # 棧(棧底->棧頂): 100 200 300
    s.push(100)
    s.push(200)
    s.push(300)
    # 終端1: 300 200 100 異常
    print(s.destack())
    print(s.destack())
    print(s.destack())
    print(s.destack())

1.5.4 鏈?zhǔn)綏４a實現(xiàn)

"""
鏈?zhǔn)酱鎯Ψ绞綄崿F(xiàn)棧
思路：
    1乎芳、棧：LIFO 后進(jìn)先出
    2、設(shè)計
       鏈表頭部作為棧頂（入棧帖池、出棧操作）
       鏈表尾部作為棧底（不進(jìn)行任何操作）
"""
class Node:
    """節(jié)點類"""
    def __init__(self, value):
        self.value = value
        self.next = None

class LinkListStack:
    def __init__(self):
        """初始化一個空棧"""
        self.head = None

    def is_empty(self):
        """判斷是否為空棧"""
        return self.head == None

    def push(self, item):
        """入棧操作: 相當(dāng)于在鏈表的頭部添加一個節(jié)點"""
        node = Node(item)
        node.next = self.head
        self.head = node

    def pop(self):
        """出棧操作: 相當(dāng)于刪除鏈表頭節(jié)點"""
        if self.is_empty():
            raise Exception('pop from empty LinkListStack')
        item = self.head.value
        self.head = self.head.next

        return item

if __name__ == '__main__':
    s = LinkListStack()
    # 棧（棧底->棧頂）：300 200 100
    s.push(100)
    s.push(200)
    s.push(300)
    # 終端1: 300
    print(s.pop())
    # 終端2: False
    print(s.is_empty())

1.6 隊列（FIFO）

1.6.1 定義

隊列是限制在兩端進(jìn)行插入操作和刪除操作的線性表奈惑，允許進(jìn)行存入操作的一端稱為"隊尾"，允許進(jìn)行刪除操作的一端稱為"隊頭"

1.6.2 特點

1) 隊列只能在隊頭和隊尾進(jìn)行數(shù)據(jù)操作
2) 隊列模型具有先進(jìn)先出規(guī)律（FIFO）

1.6.3 順序隊列代碼實現(xiàn)

"""
順序存儲方式去實現(xiàn)隊列模型
思路：
    1睡汹、隊列：FIFO 先進(jìn)先出,隊尾負(fù)責(zé)入隊,隊頭負(fù)責(zé)出隊
    2肴甸、設(shè)計：
       列表頭部作為隊頭,負(fù)責(zé)出隊
       列表尾部作為隊尾,負(fù)責(zé)入隊
"""
class Queue:
    def __init__(self):
        """初始化一個空隊列"""
        self.elems = []

    def is_empty(self):
        """判斷隊列是否為空"""
        return self.elems == []

    def enqueue(self, item):
        """隊尾入隊: append(item)"""
        self.elems.append(item)

    def dequeue(self):
        """隊頭出隊: pop(0)"""
        if self.is_empty():
            raise Exception('dequeue from empty Queue')
        return self.elems.pop(0)

if __name__ == '__main__':
    q = Queue()
    # 隊列: 100 200 300
    q.enqueue(100)
    q.enqueue(200)
    q.enqueue(300)
    # 終端1: 100
    print(q.dequeue())
    # 終端2: False
    print(q.is_empty())

1.6.4 鏈?zhǔn)疥犃写a實現(xiàn)

"""
鏈?zhǔn)酱鎯Ψ绞饺崿F(xiàn)隊列
思路：
    1、隊列：FIFO 先進(jìn)先出
    2囚巴、設(shè)計：
       鏈表頭部作為隊頭,負(fù)責(zé)出隊操作
       鏈表尾部作為隊尾,負(fù)責(zé)入隊操作
"""
class Node:
    def __init__(self, value):
        self.value = value
        self.next = None

class LinkListQueue:
    def __init__(self):
        """初始化一個空隊列"""
        self.head = None

    def is_empty(self):
        """判斷隊列是否為空"""
        return self.head == None

    def enqueue(self, item):
        """隊尾入隊: 相當(dāng)于在鏈表尾部添加一個節(jié)點"""
        node = Node(item)
        # 空隊列情況
        if self.is_empty():
            self.head = node
            return
        # 非空隊列
        cur = self.head
        while cur.next:
            cur = cur.next
        # 循環(huán)結(jié)束后,cur一定是指向了原鏈表尾節(jié)點
        cur.next = node
        node.next = None

    def dequeue(self):
        """隊頭出隊: 相當(dāng)于刪除鏈表頭節(jié)點"""
        if self.is_empty():
            raise Exception('dequeue from empty LinkListQueue')
        cur = self.head
        # 刪除頭節(jié)點
        self.head = self.head.next

        return cur.value

if __name__ == '__main__':
    q = LinkListQueue()
    # 隊列: 100 200 300
    q.enqueue(100)
    q.enqueue(200)
    q.enqueue(300)
    # 終端1: 100
    print(q.dequeue())
    # 終端2: False
    print(q.is_empty())

1.7 樹形結(jié)構(gòu)

1.7.1 定義

樹（Tree）是n（n≥0）個節(jié)點的有限集合T雷滋，它滿足兩個條件：有且僅有一個特定的稱為根（Root）的節(jié)點；其余的節(jié)點可以分為m（m≥0）個互不相交的有限集合T1文兢、T2晤斩、……、Tm姆坚，其中每一個集合又是一棵樹澳泵，并稱為其根的子樹（Subtree）

1.7.2 基本概念

# 1. 樹的特點
* 每個節(jié)點有零個或者多個子節(jié)點
* 沒有父節(jié)點的節(jié)點稱為根節(jié)點
* 每一個非根節(jié)點有且只有一個父節(jié)點
* 除了根節(jié)點外,每個子節(jié)點可以分為多個不相交的子樹

# 2. 相關(guān)概念
1) 節(jié)點的度: 一個節(jié)點的子樹的個數(shù)
2) 樹的度: 一棵樹中,最大的節(jié)點的度成為樹的度
3) 葉子節(jié)點: 度為0的節(jié)點
4) 父節(jié)點
5) 子節(jié)點
6) 兄弟節(jié)點
7) 節(jié)點的層次: 從根開始定義起,根為第1層
8) 深度: 樹中節(jié)點的最大層次

1.8 二叉樹

1.8.1 定義

二叉樹（Binary Tree）是n（n≥0）個節(jié)點的有限集合，它或者是空集（n＝0）兼呵，或者是由一個根節(jié)點以及兩棵互不相交的兔辅、分別稱為左子樹和右子樹的二叉樹組成。二叉樹與普通有序樹不同击喂，二叉樹嚴(yán)格區(qū)分左孩子和右孩子维苔，即使只有一個子節(jié)點也要區(qū)分左右

1.8.2 二叉樹的分類

【1】完全二叉樹
    對于一顆二叉樹，假設(shè)深度為d懂昂，除了d層外介时，其它各層的節(jié)點數(shù)均已達(dá)到最大值，并且第d層所有節(jié)點從左向右連續(xù)緊密排列

【2】滿二叉樹
    所有葉節(jié)點都在最底層的完全二叉樹
    
【3】二叉排序樹('二叉搜索樹')
    任何一個節(jié)點凌彬，所有左邊的值都會比此節(jié)點小沸柔，所有右邊的值都會比此節(jié)點大
    
【4】平衡二叉樹
    當(dāng)且僅當(dāng)任何節(jié)點的兩棵子樹的高度差不大于1的二叉樹

• 二叉樹 - 添加元素代碼實現(xiàn)

  """
  二叉樹
  """
  
  class Node:
      def __init__(self, value):
          self.value = value
          self.left = None
          self.right = None
  
  class Tree:
      def __init__(self, node=None):
          """創(chuàng)建了一棵空樹或者是只有樹根的樹"""
          self.root = node
  
      def add(self, value):
          """在樹中添加一個節(jié)點"""
          node = Node(value)
          # 空樹情況
          if self.root is None:
              self.root = node
              return
  
          # 不是空樹的情況
          node_list = [self.root]
          while node_list:
              cur = node_list.pop(0)
              # 判斷左孩子
              if cur.left is None:
                  cur.left = node
                  return
              else:
                  node_list.append(cur.left)
  
              # 判斷右孩子
              if cur.right is None:
                  cur.right = node
                  return
              else:
                  node_list.append(cur.right)
  

1.8.3 廣度遍歷

• 廣度遍歷 - 代碼實現(xiàn)

      def breadth_travel(self):
          """廣度遍歷 - 隊列思想（即：列表的append()方法 和 pop(0) 方法"""
          # 1、空樹的情況
          if self.root is None:
              return
          # 2铲敛、非空樹的情況
          node_list = [self.root]
          while node_list:
              cur = node_list.pop(0)
              print(cur.value, end=' ')
              # 添加左孩子
              if cur.left is not None:
                  node_list.append(cur.left)
              # 添加右孩子
              if cur.right is not None:
                  node_list.append(cur.right)
  
          print()
  

1.8.4 深度遍歷

【1】遍歷
    沿某條搜索路徑周游二叉樹褐澎，對樹中的每一個節(jié)點訪問一次且僅訪問一次。

【2】遍歷方式
    2.1) 前序遍歷： 先訪問樹根伐蒋，再訪問左子樹工三，最后訪問右子樹 - 根 左 右
    2.2) 中序遍歷： 先訪問左子樹迁酸，再訪問樹根，最后訪問右子樹 - 左 根 右
    2.3) 后序遍歷： 先訪問左子樹俭正，再訪問右子樹胁出，最后訪問樹根 - 左 右 根

【1】前序遍歷結(jié)果: 1 2 4 8 9 5 10 3 6 7
【2】中序遍歷結(jié)果: 8 4 9 2 10 5 1 6 3 7
【3】后序遍歷結(jié)果: 8 9 4 10 5 2 6 7 3 1

• 深度遍歷 - 代碼實現(xiàn)

# 前序遍歷
    def pre_travel(self, node):
        """前序遍歷 - 根左右"""
        if node is None:
            return

        print(node.value, end=' ')
        self.pre_travel(node.left)
        self.pre_travel(node.right)

# 中序遍歷
    def mid_travel(self, node):
        """中序遍歷 - 左根右"""
        if node is None:
            return

        self.mid_travel(node.left)
        print(node.value, end=' ')
        self.mid_travel(node.right)

# 后續(xù)遍歷
    def last_travel(self, node):
        """后序遍歷 - 左右根"""
        if node is None:
            return

        self.last_travel(node.left)
        self.last_travel(node.right)
        print(node.value, end=' ')

1.8.5 二叉樹代碼實現(xiàn)

"""
python實現(xiàn)二叉樹
"""

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

class Tree:
    def __init__(self, node=None):
        """創(chuàng)建了一棵空樹或者是只有樹根的樹"""
        self.root = node

    def add(self, value):
        """在樹中添加一個節(jié)點"""
        node = Node(value)
        # 空樹情況
        if self.root is None:
            self.root = node
            return

        # 不是空樹的情況
        node_list = [self.root]
        while node_list:
            cur = node_list.pop(0)
            # 判斷左孩子
            if cur.left is None:
                cur.left = node
                return
            else:
                node_list.append(cur.left)

            # 判斷右孩子
            if cur.right is None:
                cur.right = node
                return
            else:
                node_list.append(cur.right)

    def breadth_travel(self):
        """廣度遍歷 - 隊列思想（即：列表的append()方法 和 pop(0) 方法"""
        # 1、空樹的情況
        if self.root is None:
            return
        # 2段审、非空樹的情況
        node_list = [self.root]
        while node_list:
            cur = node_list.pop(0)
            print(cur.value, end=' ')
            # 添加左孩子
            if cur.left is not None:
                node_list.append(cur.left)
            # 添加右孩子
            if cur.right is not None:
                node_list.append(cur.right)

        print()

    def pre_travel(self, node):
        """前序遍歷 - 根左右"""
        if node is None:
            return

        print(node.value, end=' ')
        self.pre_travel(node.left)
        self.pre_travel(node.right)

    def mid_travel(self, node):
        """中序遍歷 - 左根右"""
        if node is None:
            return

        self.mid_travel(node.left)
        print(node.value, end=' ')
        self.mid_travel(node.right)

    def last_travel(self, node):
        """后序遍歷 - 左右根"""
        if node is None:
            return

        self.last_travel(node.left)
        self.last_travel(node.right)
        print(node.value, end=' ')

if __name__ == '__main__':
    tree = Tree()
    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.add(10)
    # 廣度遍歷：1 2 3 4 5 6 7 8 9 10
    tree.breadth_travel()
    # 前序遍歷：1 2 4 8 9 5 10 3 6 7
    tree.pre_travel(tree.root)
    print()
    # 中序遍歷:8 4 9 2 10 5 1 6 3 7
    tree.mid_travel(tree.root)
    print()
    # 后序遍歷：8 9 4 10 5 2 6 7 3 1
    tree.last_travel(tree.root)

2. 算法

2.1 遞歸算法

2.1.1 遞歸定義及特點

【1】定義
    遞歸用一種通俗的話來說就是自己調(diào)用自己，但是需要分解它的參數(shù)闹蒜，讓它解決一個更小一點的問題寺枉，當(dāng)問題小到一定規(guī)模的時候，需要一個遞歸出口返回
    
【2】特點
    2.1) 遞歸必須包含一個基本的出口绷落，否則就會無限遞歸姥闪，最終導(dǎo)致棧溢出
    2.2) 遞歸必須包含一個可以分解的問題
    2.3) 遞歸必須必須要向著遞歸出口靠近

2.1.2 遞歸示例

• 遞歸示例1

  def f(n):
      if n == 0:
          return 
      print(n)
      f(n-1)
  
  f(3)
  # 結(jié)果: 3 2 1
  # 調(diào)用遞歸之前的語句,是從外到內(nèi)執(zhí)行（遞推的過程中依次執(zhí)行）
  

• 遞歸示例2

  def f(n):
    if n == 0:
      return 
    f(n-1)
    print(n)
    
  f(3)
  # 結(jié)果: 1 2 3
  # 調(diào)用遞歸之后的語句，是從內(nèi)到外執(zhí)行（是在回歸的過程中依次執(zhí)行）
  

• 遞歸示例3

  # 打印 1+2+3+...+n 的和
  def sumn(n):
    if n == 1:
      return 1
    return n + sumn(n-1)
  
  print(sumn(3))
  

遞歸練習(xí)

# 使用遞歸求出 n 的階乘
def fac(n):
  if n == 1:
    return 1
  return n * fac(n-1)

print(fac(5))

2.1.3 遞歸總結(jié)

# 前三條必須記住
【1】遞歸一定要有出口,一定是先遞推,再回歸
【2】調(diào)用遞歸之前的語句砌烁，從外到內(nèi)執(zhí)行筐喳，最終回歸
【3】調(diào)用遞歸或之后的語句，從內(nèi)到外執(zhí)行函喉，最終回歸

【4】Python默認(rèn)遞歸深度有限制避归，當(dāng)遞歸深度超過默認(rèn)值時，就會引發(fā)RuntimeError管呵，默認(rèn)值998
【5】手動設(shè)置遞歸調(diào)用深度
    import sys
    sys.setrecursionlimit(1000000) #表示遞歸深度為100w

• 遞歸動態(tài)圖解一

• 遞歸動態(tài)圖解二

• 遞歸動態(tài)圖解三

2.1.4 遞歸練習(xí)題

【1】給定一棵二叉搜索樹,請找出其中第k小的節(jié)點
    # 二叉搜索樹中序遍歷的結(jié)果是遞增的序列
    def get_k_node(root, k):
        pass
    
【2】一個青蛙一次可以跳1級臺階或2級臺階,一共有n級臺階,問青蛙跳到頂部有幾種跳法
  思路一：舉例大法(找規(guī)律-斐波那契數(shù)列)
         1級臺階：1
         2級臺階：2
         3級臺階：3
         4級臺階：5
         5級臺階：8
         ... ..
  思路二：遞歸思想(f(n))
        考慮最后一跳,最后一跳跳到頂部共有2種跳法
        最后一跳(1級臺階): f(n-1)
        最后一跳(2級臺階): f(n-2)
        總的跳法的種類：f(n) = f(n-1) + f(n-2)

def f(n):
    # 遞歸出口
    if n == 1:
        return 1
    if n == 2:
        return 2
    
    return f(n-1) + f(n-2)

2.2 冒泡排序

2.2.1 排序方式

# 排序方式
遍歷列表并比較相鄰的元素對梳毙，如果元素順序錯誤，則交換它們捐下。重復(fù)遍歷列表未排序部分的元素账锹，直到完成列表排序

# 時間復(fù)雜度
因為冒泡排序重復(fù)地通過列表的未排序部分，所以它具有最壞的情況復(fù)雜度O(n^2)

2.2.2 代碼實現(xiàn)

"""
冒泡排序
3 8 2 5 1 4 6 7
"""
def bubble_sort(li):
    # 代碼第2步: 如果不知道循環(huán)幾次坷襟，則舉幾個示例來判斷
    for j in range(0,len(li)-1):
        # 代碼第1步: 此代碼為一波比對奸柬，此段代碼一定一直循環(huán)，一直比對多次至排序完成
        for i in range(0,len(li)-j-1):
            if li[i] > li[i+1]:
                li[i],li[i+1] = li[i+1],li[i]

    return li

li = [3,8,2,5,1,4,6,7]
print(bubble_sort(li))

2.3 歸并排序

2.3.1 排序規(guī)則

# 思想
分而治之算法

# 步驟
1) 連續(xù)劃分未排序列表婴程，直到有N個子列表廓奕，其中每個子列表有1個"未排序"元素，N是原始數(shù)組中的元素數(shù)
2) 重復(fù)合并档叔，即一次將兩個子列表合并在一起懂从，生成新的排序子列表，直到所有元素完全合并到一個排序數(shù)組中

2.3.2 代碼實現(xiàn)

"""
歸并排序
"""
def merge_sort(li):
    # 遞歸出口
    if len(li) == 1:
        return li

    mid = len(li) // 2
    left = li[:mid]
    right = li[mid:]
    # 遞歸思想
    left_li = merge_sort(left)
    right_li = merge_sort(right)

    return merge(left_li, right_li)

def merge(left_li, right_li):
    result = []
    while left_li and right_li:
        if left_li[0] >= right_li[0]:
            result.append(right_li.pop(0))
        else:
            result.append(left_li.pop(0))

    # 循環(huán)結(jié)束時,一定有一個列表為空了
    if left_li:
        result.extend(left_li)
    else:
        result.extend(right_li)

    return result

if __name__ == '__main__':
    li = [6,4,5,3,1,66,8,6,7,520,2,4]
    r = merge_sort(li)
    print(r)

2.4 快速排序

2.4.1 排序規(guī)則

【1】介紹
    快速排序也是一種分而治之的算法蹲蒲，在大多數(shù)標(biāo)準(zhǔn)實現(xiàn)中番甩，它的執(zhí)行速度明顯快于歸并排序

【2】排序步驟：
    2.1) 首先選擇一個元素，稱為數(shù)組的基準(zhǔn)元素
    2.2) 將所有小于基準(zhǔn)元素的元素移動到基準(zhǔn)元素的左側(cè)届搁；將所有大于基準(zhǔn)元素的移動到基準(zhǔn)元素的右側(cè)
    2.3) 遞歸地將上述兩個步驟分別應(yīng)用于比上一個基準(zhǔn)元素值更小和更大的元素的每個子數(shù)組

2.4.2 代碼實現(xiàn)

"""
快速排序
    1缘薛、left找比基準(zhǔn)值大的暫停
    2窍育、right找比基準(zhǔn)值小的暫停
    3、交換位置
    4宴胧、當(dāng)right<left時漱抓，即為基準(zhǔn)值的正確位置，最終進(jìn)行交換
"""
def quick_sort(li, first, last):
    """快速排序"""
    # 遞歸出口
    if first > last:
        return

    # position:基準(zhǔn)值正確位置下標(biāo)索引,即:分隔li為左右兩部分的值
    position = sort(li, first, last)
    # 遞歸思想,左右兩部分繼續(xù)執(zhí)行快速排序
    quick_sort(li, first, position - 1)
    quick_sort(li, position + 1, last)

def sort(li, first, last):
    """
    :param li: 無序的數(shù)組
    :param first: 基準(zhǔn)值所在位置的下標(biāo)索引
    :param last: 右游標(biāo)的索引值
    :return: 基準(zhǔn)值正確位置的下標(biāo)索引
    """
    lcur = first + 1
    rcur = last
    while True:
        # 左游標(biāo)右移
        while lcur <= rcur and li[lcur] <= li[first]:
            lcur += 1
        # 右游標(biāo)左移
        while lcur <= rcur and li[rcur] >= li[first]:
            rcur -= 1

        if lcur < rcur:
            # 左右游標(biāo)互換位置
            li[lcur],li[rcur] = li[rcur], li[lcur]
        else:
            # 右游標(biāo)和基準(zhǔn)值互換位置
            # 右游標(biāo)就是基準(zhǔn)值的正確位置
            li[first], li[rcur] = li[rcur], li[first]
            # 返回了基準(zhǔn)值正確位置的下標(biāo)索引
            return rcur

if __name__ == '__main__':
    li = [6,5,3,1,8,7,2,8,666,6,2,4]
    quick_sort(li, 0, len(li)-1)

    print(li)

2.5 二分查找

2.5.1 定義及規(guī)則

【1】定義及優(yōu)點
    二分查找又稱折半查找恕齐，優(yōu)點是比較次數(shù)少乞娄，查找速度快，平均性能好

【2】查找過程
　　二分查找即搜索過程從數(shù)組的中間元素開始,如果中間元素正好是要查找的元素,則搜索過程結(jié)束;如果中間元素大于或小于要查找元素,則在小于或大于中間元素的那一半進(jìn)行搜索,而且跟開始一樣從中間元素開始比較. 如果在某一步驟數(shù)組為空,則代表找不到.這種算法每一次比較都會使搜索范圍縮小一半.

【3】適用條件
    '數(shù)組必須有序'

• 二分查找圖解一

• 二分查找圖解二

2.5.2 代碼實現(xiàn)

"""
python實現(xiàn)二分查找
"""

def binary_search(li, item):
    # 1 2 3 4 5 6 7 8 9 10
    # 查找: 0
    first = 0
    last = len(li) - 1
    while first <= last:
        mid = (first + last) // 2
        if li[mid] > item:
            last = mid - 1
        elif li[mid] < item:
            first = mid + 1
        else:
            return True

    return False

if __name__ == '__main__':
    li = [1,2,3,4,5,6,7,8]
    # 終端1: True
    print(binary_search(li, 3))
  # 終端2: False
    print(binary_search(li, 666))