---
# System prepended metadata

title: DataStructure & Algorithm

---

DataStructure & Algorithm
===
```python
# codind:utf-8
# Q. a+b+c=1000, a^2+b^2=c^2
# 枚舉法

# 解一: 197s
# import time
# start = time.time()
# for a in range(0,1001):
#     for b in range(0,1001):
#         for c in range(0,1001):
#             if a+b+c==1000 and a**2+b**2==c**2:
#                 print("a, b , c: %d ,%d ,%d"%(a, b, c))

# 解二: 1s
# c = 1000-a-b
import time
start = time.time()
for a in range(0,1001):
    for b in range(0,1001):
        c = 1000-a-b
        if a**2+b**2==c**2:
            print("a, b , c: %d ,%d ,%d"%(a, b, c))



end = time.time()
print("time: %d" %(end-start))
print("end")
```
> 如何判斷算法效率?
> - 單純以運行時間?
>   - 計算機環境等足以影響運行時間, 
>   - 故以運行時間判斷不一定好
> - 基本運算數量
>   - 機器執行總時間不同,
>   - 但執行基本運算數量(步驟數)大體相同
>   - 基本運算數量的總和, 稱為『時間複雜度』

### 時間複雜度(解一)
> `for a` > 1000, `for b` > 1000, `for c` > 1000
> `if(a+b+c`, `a+b+c==1000`, 
> `a\**2`,`b\**2`,`c\**2`, `a\**2+b\**2`,`a\**2+b\**2\==c**2`,`and`>8
> `print(%)`, `print()`>2
> T = 1000\*1000\*1000\*10
> 
> Q. a+b+c=2000, a^2^+b^2^=c^2^
> T = 2000\*2000\*2000\*10
> Q. a=b=c=N ,...
> T(n) = N^3^ * 10 > T(n)即為時間複雜度

#### 大O記法
> - 取時間複雜度的漸進函數(忽略常數)
> - T(n) = N^3^ * 10 > G(n) = N^3^
> - 亦即T(n) = k*G(n) + c = O(G(n))

#### 時間複雜度基本計算規則
> - 順序: +
> - 循環: *
> - 分支: 取最大值
> - 基本操作> O(1)
> - 一般分析算法都是指『最壞時間複雜度』
>   - 最優時間複雜: 最少基本操作
>   - 最壞時間複雜: 最多基本操作
>   - 平均時間複雜: (最優+最壞)/2
> - 最後忽略常數項與次要項
>   - ax^2^+bx+c: 
>     - a,c :常數  
>     - bx: 次要

#### 時間複雜度(解二)
> for a > 1000, for b > 1000
> c = O(1)
> if = 1(True, print) or 0(False) > max=1 
> T(n) = 1000 \* 1000 \* (1+max(1,0)) = 1000^2^ \*2
> T(n) = n^2^ \* 2 = O(n^2^)

#### 常見時間複雜度
|舉例|階|
|:--:|:--:|
|10|O(1)|
|an+b|O(n)|
|an^2^+b|O(n^2^)|
|an^3^+b|O(n^3^)|
|alog~2~n+b|O(logn)|
|an+bnlog~2~n+c|O(nlogn)|
|2^n^|O(2^n^)|
> O(1)<O(logn)<O(n)<O(nlogn)<O(n^2^)<O(n^3^)<O(2^n^)<O(n!)<O(n^n^)

## timeit
`class timeit.Timer(stmt='pass', setup='pass', timer=<timer function>)`
> - Timer: 測試代碼執行速度的類
> - stmt: 測試代碼語句(statment)
> - setup: 設置
> - timer: 定時器(與平台有關)

`timeit.Timer.timeit(number=1000000)`
> - timeit返回平均速度
> - number: 測試次數
```python
#coding:utf-8
from timeit import Timer


# 運作模式:(vs.extend)
    # 先建立一個空列表
    # 將li丟進該列表後,再將i丟進該列表
    # 最後li指向新的列表
def t1():
    li = []
    for i in range(10000):
        li = li + [i]

# +=的運作模式跟extend差不多,
# 都是在原來的列表進行操作
def t2():
    li = []
    for i in range(10000):
        li += [i]

# extend運作模式:(vs.+)
    # 直接在li列表中加入i
# extend追加列表或可迭代對象, 將其所有元素都添加(vs.append)
def t3():
    li = []
    for i in range(10000):
        li.extend([i])

# append只能追加單一元素(vs.extend)
# 對列表尾添加(vs.insert)
def t4():
    li = []
    for i in range(10000):
        li.append(i)

# 對列表頭添加(vs.append)
# 因為數據結構的關係, 對頭添加的速度非常慢
def t5():
    li = []
    for i in range(10000):
        li.insert(0, i)

# 註一
def t6():
    li = [i for i in range(10000)]

# 註二
def t7():
    li = list(range(10000))

# Timer 不是在這個文件執行, 故要導入到該執行文件中
# 作為啟動文件, 名字應該是__main__
timer1 = Timer("t1()", "from __main__ import t1")
print("+:", timer1.timeit(1000))

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

timer3 = Timer("t3()", "from __main__ import t3")
print("extend:", timer3.timeit(1000))

timer4 = Timer("t4()", "from __main__ import t4")
print("append:", timer4.timeit(1000))

timer5 = Timer("t5()", "from __main__ import t5")
print("insert:", timer5.timeit(1000))

timer6 = Timer("t6()", "from __main__ import t6")
print("[i for i in range]:", timer6.timeit(1000))

timer7 = Timer("t7()", "from __main__ import t7")
print("range(list):", timer7.timeit(1000))
```
```$
+: 181.142842282
+=: 0.9807232400000032
extend: 1.4030078149999952
append: 0.8890636299999812
insert: 22.47004824000001
[i for i in range]: 0.4352005479999832
range(list): 0.19273629400001369
```
```python
# 註一: 複習
In [29]: a = (i for i in range(10))
In [30]: a                              
Out[30]: <generator object <genexpr> at 0x10d4a3f48>
In [31]: next(a)                        
Out[31]: 0
In [32]: next(a)                        
Out[32]: 1
In [33]: list(a)                        
Out[33]: [2, 3, 4, 5, 6, 7, 8, 9]

In [34]: a = [i for i in range(10)]
In [35]: a                              
Out[35]: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

# 註二: 複習(python2 vs python3的range)
# python3
In [36]: a = range(10)
In [37]: a                              
Out[37]: range(0, 10)
In [38]: list(a)                        
Out[38]: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

# python2
In [1]: a = range(10)
In [2]: a
Out[2]: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
```


#### dict內置操作的時間複雜度
|||
|:--:|:--:|
|copy|O(n)|
|get item|O(1)|註一|
|set item|O(1)|
|delete item|O(1)|
|contains(in)|O(1)|
|iteration|O(n)|

> 註一:
> > key取value

## 數據結構
> - 對於計算機來說, 基本類型僅為str, floar, int, char等
> - 且基本類型也僅僅存一個數據而已, 如何把數個基本元素組合即為數據結構欲探討的議題
> - 數據組成方式不同, 處理數據時的算法也就不同
```python
# Q. 如何保存學生信息?
# [()]
student1 = [
    ("Mary", 18, "ADDR1"),
    ("Edison", 17, "ADDR2")
]

# 查詢
for i in student1: # O(n)
    if i(0) == "Mary":
        print(i)
# [{}]
student2 = [
    {
        "name":"Mary",
        "age": 18,
        "ADDR":"ADDR1"
    },
    {
    
    }
]
# {{}}
student3 = {
    "Mary":{
        "age": 18,
        "ADDR": "ADDR1"
    },
    "Edison":{
    
    }
}
# 查詢
student3["Mary"] # O(1)
```
> 程序 = 數據結構 + 算法 

### 抽象數據類型(Abstract Data Type)
> - 把數據類型與其運算方法封裝
> - 常見的運算方法如增刪改查
  
```python
class arr(obj):
  def pop(self):
  def append(self):
  ...
```


## 線性表
### 順序表
> Q. Int = 1,11,111, 如何保存這三個整數?
```
# li = []  => 高階數據結構

- 內存
  - 連續的存儲單元
  - 基本單元: 1Byte = 8bit
  - 一個單元會有一個地址標示, CPU就可以依據標示找到相應數據
          _ _ _ _ _ _ _ _
    0x01 |_|_|_|_|_|_|_|_| : 1Byte
    0x02 |_|_|_|_|_|_|_|_|
    0x03 |_|_|_|_|_|_|_|_|
    0x04 |_|_|_|_|_|_|_|_|
 
- INT
  - 對於32位元機器來說, Int佔4Byte
  - Int a = 1
          _ _ _ _ _ _ _ _
    0x01 |0|0|0|0|0|0|0|0| 
    0x02 |0|0|0|0|0|0|0|0|
    0x03 |0|0|0|0|0|0|0|0|
    0x04 |0|0|0|0|0|0|0|1|
          ‾ ‾ ‾ ‾ ‾ ‾ ‾ ‾
- char: 
  - 1Byte
  - 字符, 
  - 字符集合 = str

- 類型
  - 以上面0x01~0x04為例, 
  - 如果我告訴計算機為整數, 那麼就是1
  - 如果我告訴計算機為char, 那麼此時就要對應  char * 4
    - 00000000為何
    - 00000001為何
  - 亦即類型定義了記憶體中佔多大, 以及電腦讀取時如何處理這些二進制數據

- 順序表
  - 按順序連續存放, 此時即可方便處理, 此稱為順序表

- 回到問題, 如何存儲 li = [1,11,111]
                    ________
    li-> 0x18~0x22 |_______1| : 4Byte
         0x22~0x26 |______11|
         0x26~0x30 |_____111|
  - 向os申請12Byte, os會一次返回
  - 數據存儲完畢後, li就會指向起始地址(0x18)
  - li[0] = 0x18 + 0*4Byte
  - li[2] = 0x18 + 2*4Byte
    - 故該數字代表偏移量的意思
  - 此種存儲方法前提必須每個存儲數據大小相同
  
- 元素外置
  - 當存儲數據大小不同的數據時, 此時就無法用基本順序表存儲
  - 故此時可以存儲數據地址
  - 每個地址事實上佔用4Byte
  - li = [11, "ab\0", 1.11]
                      ________           ________
    li-> 0x300~0x304 |____0x99|-> 0x99  |_11_____|
         0x304~0x308 |___0x121|-> 0x121 |_"ab\0"_|
         0x308~0x312 |___0x231|-> 0x231 |_1.11___|
```
#### 順序表的結構
```
# 順序表包含了表頭信息與數據區
# 而表頭信息包含了容量與元素個數
  # 容量:
    # 在向os申請內存空間時, 必須估計大小, 否則os也不知道要給你多少
  # 元素個數:
    # 已使用多少空間
    
# 一體式 li = [1,11,111] -> 0x10
   _max _num ____ ____ ____ ____
  |   4|   3|   1|  11| 111|    |    
   ‾‾‾‾ ‾‾‾‾ ‾‾‾‾ ‾‾‾‾ ‾‾‾‾ ‾‾‾‾ 
   0x10 0x14 0x18 0x22 0x26 0x30
   
# 分離式 li = [1,11,111]
   _max _num ____     ____ ____ ____ ____ 
  |   4|   3|0x18|   |   1|  11| 111|    |
   ‾‾‾‾ ‾‾‾‾ ‾‾‾‾ ↘   ‾‾‾‾ ‾‾‾‾ ‾‾‾‾ ‾‾‾‾ 
   0x55 0x59 0x63     0x18 0x22 0x26 0x30

# 區別:
  # 假設 li = [1,11,111,10,7]
  # 此時超過當時申請的空間
  # 一體式:
    # 重新申請新的內存空間後存儲對應數據
    # 故li 指向會改變
  # 分離式:
    # 只需申請數據區的內存空間
    # 信息區重新指向新內存空間地址即可
    # 故li 指向不變

# 擴充預留
  # 預留多: 佔用大, 擴充次數少
  # 預留少: 佔用小, 擴充次數多
```
#### 順序表增刪
```
# 增
# 表尾添加
   _max _num ____ ____ ____ ____ ____ ____ ____ ____
  |   8|   3|   1|  11| 111|  21|  22|  23|  26| →20|    
   ‾‾‾‾ ‾‾‾‾ ‾‾‾‾ ‾‾‾‾ ‾‾‾‾ ‾‾‾‾ ‾‾‾‾ ‾‾‾‾ ‾‾‾‾ ‾‾‾‾ 
   # 直接插入: O(1)

# 保序添加 
   _max _num ____ ____ ____ ____ ____ ____ ____ ____
  |   8|   3| →20|   1|  11| 111|  21|  22|  23|  26|   
   ‾‾‾‾ ‾‾‾‾ ‾‾‾‾ ‾‾‾‾ ‾‾‾‾ ‾‾‾‾ ‾‾‾‾ ‾‾‾‾ ‾‾‾‾ ‾‾‾‾ 
   # 先將26往後移,接著將23往後移...: O(7)
   # 最後插入20: O(8)/ O(n)

# 非保序添加(少見)
   _max _num ____ ____ ____ ____ ____ ____ ____ ____
  |   8|   3| →20|  11| 111|  21|  22|  23|  26|   1|  
   ‾‾‾‾ ‾‾‾‾ ‾‾‾‾ ‾‾‾‾ ‾‾‾‾ ‾‾‾‾ ‾‾‾‾ ‾‾‾‾ ‾‾‾‾ ‾‾‾‾ 
   # 將1一到最後一位
   # 插入20: O(2)/O(1)
   
# 刪除亦同, 刪完往前補
  # 表尾: O(1)
  # 保緒: O(n)
  # 非保緒: O(1)
```
#### Python順序表
```
# list
  - 下標查詢(index x[]): O(1) > 順序表
  - 『任意元素』加入, 『id標示不變』> 元素外置,分離式
  - 建立一個空列表時, 系統分配8個元素存儲區(存儲地址\4Byte)
  - 擴充: 每次4倍, 當該表到一定大小時, 則改為一倍

# tuple
  - 下標查找> 順序表
``` 
#### list內置操作的時間複雜度
|Operation|Big-O Efficiency||
|:--:|:--:|:--:|
|index x[]|O(1)||
|index assignment|O(1)||
|append|O(1)||
|pop()|O(1)||
|pop(i)|O(n)||
|insert(i,item)|O(n)||
|del operator|O(n)|註一|
|iteration|O(n)|迭代|
|contains(in)|O(n)|需遍歷一次才知道存不存在|
|get slice[x:y]|O(k)|註二|
|del slice|O(n)|註三|
|set slice|O(n+k)|註四|
|reverse|O(n)||
|concatenate|O(k)|註五|
|sort|O(n log n)||
|multiply|O(nk)||

> 註一:
> - 元素外置, 
> - 列表地址可以一次刪除, 
> - 但是指向的存儲空間必須一個一個刪
> 
> 註二:
> > - k: 距離
> > - 取x時: O(1)
> > - 取到y即停止: O(k)
> 
> 註三:
> > - 刪除後, 後面的要補上, 故O(n)
> 
> 註四:
> ```python
> In [12]: a = [1,2,3,4,5]
> In [13]: a[0:2] = [55,66,77,88]
> In [14]: a
> Out[14]: [55, 66, 77, 88, 3, 4, 5]
> # 先刪掉指定切片O(n)
> # 補充多少個O(k)
> ```
> 
> 註五:
> > - li += [li]
> > - 往後面添加多少個元素: O(k)
> 
> 註六:
> ```python
> In [15]: a = [1] # n
> In [16]: a*5 # k
> Out[16]: [1, 1, 1, 1, 1]
> ```

### 鏈表
#### 單鏈表
```
 ______ ______ 
| 數據區| 鏈接區|
 ‾‾‾‾‾‾ ‾‾‾‾‾‾   
element  next      
      __ ____     __ ____     __ ____ 
 p-> | 1|0x66|-> |11|0x87|-> |20| ⊥ |
      ‾‾ ‾‾‾‾     ‾‾ ‾‾‾‾     ‾‾ ‾‾‾
      0x55        0x66        0x87 

  # P 變量
  # ⊥ 表示指向空的意思
  # 數據區+鏈接區, 整體稱為節點(node)
  
# 實現:
  # 思考:
    a = 10
    b = 20
    a,b = b,a
    是如何實現的?
  
    # a = 10, b = 20
      _a__    __    _b__    __
     |next|->|10|, |next|->|20|
      ‾‾‾‾    ‾‾    ‾‾‾‾    ‾‾
    # a,b = b,a
      # 先找到b的地址後, 地址指向存有20的內存
      # 接著換a
      # a,b = 20,10
      
    # a->20, b->10
      # 最後a與b中的鏈接區改變next的指向
      # 故改變的只有a,b本身的內存指向, 
      # 原本存有10與20的內存完全沒有變動
  # cf. C
    # int a = 10;
       _a
      |10|
       ‾‾ 
    # C語言申請空間時就指定了該空間的類型, 且該空間的別名就為a
    # a空間只能保存int

  # def func():
      pass
    a = func
    # 所以python的變量才可以任意改變元素類型, 因為他保存的僅僅是地址
    
  # 實現單鏈概念
     ____________0x55      ____________0x66
    |class node1():  |    |class node2():  |
    |    element = 10|    |    element = 20|
    |    next = node2| -> |    next        |
     ‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾      ‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾
    # 亦即node1的next指向0x66
```
#### 實現單鏈表
```python
#coding:utf-8

class Node(object):
    def __init__(self, elem):
        self.elem = elem
        # 一開始並不知道指向誰,所以先指向None
        self.next = None

class SingleLinkList(object):
    """"""
    # 需要保存頭節點(p)信息,故創建head屬性, 保存在對象中
    # 對於使用者來說,並不需要知道頭節點屬性, 故私有
    # 假設有用戶會先創立一個節點, 然後直接傳進來讓head指向的需求
    # 假設有用戶沒有先創或傳node進來的需求, 故將node預設為Node, 以避免沒傳參報錯
    def __init__(self, node=None):
        self.__head = node

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

    def length(self):
        """"""
        # current游標: 用來移動遍歷節點
        cur = self.__head
        # content記錄數量
        # 初始值要等於0?1?
        # 如果初始值為1的話, 那麼一開始node=None時要額外處理, 否則會多1
        # 以人腦的邏輯來看, 應該是一開始0, 數一次+1, 故我使用0
        content = 0
        # 判斷式cur!=None? cur.next!=None?
        # 如果下次是next就不+的話, 會少+1次
        while cur != None:
            content+=1
            cur = cur.next
        return content

    def travel(self):
        """遍歷列表"""
        cur = self.__head
        while cur != None:
            print(cur.elem , end=" ")
            cur = cur.next
        print("")
    def append(self, item):
        """尾插法"""
        # item不是節點! 而是一個數據
        # 故首先建立一個節點
        node = Node(item)
        # 如果一開始就指向None,
        # 由於None沒有next, 故會出錯
        # 所以須先判斷
        # if self.__head == None:
        if self.is_empty():
            self.__head = node
        else:
            cur = self.__head
            # 先讓游標一直往後走, 走到next=None跳出
            while cur.next != None:
                cur = cur.next
            # 此時游標停在尾節點處, 尾節點指向剛創建的節點即可
            cur.next = node

    def add(self, item):
        """頭插法"""
        node = Node(item)
        # 注意順序, 
        # 如果先把self.__head指向node, 
        # 那麼原本self.__head的數據就會0而被回收
        # node.next就沒東西指了
        node.next = self.__head
        self.__head = node

    def insert(self, pos, item):
        """"""
        # 特殊情況: 位置插在0或負數, 視為頭插
        if pos <=0:
            self.add(item)
        # 特殊情況: 位置插在最後面, 通通視為尾插
        elif pos > (self.length()-1):
            self.append(item)
        else:
            node = Node(item)
            # pre/prior 當前的上一個
            pre = self.__head
            count = 0
            while count < (pos-1):
                count +=1
                pre = pre.next
            node.next = pre.next
            pre.next = node
         
    def remove(self, item):
        """"""
        cur = self.__head
        pre = None
        while cur != None:
            if cur.elem == item:
                # 如果是頭節點, pre指向None> 沒有next
                # 故要直接用self來操作
                if cur == self.__head:
                    self.__head = cur.next
                else:
                    pre.next = cur.next
                break
            else:
                pre = cur
                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__":

    sll = SingleLinkList()
    print(sll.is_empty())
    print(sll.length())

    sll.append(1) 
    print(sll.is_empty())
    print(sll.length())
    print("-"*10)    
    sll.append(2)
    sll.add(99)
    sll.append(3)
    sll.append(4) #99 1 2 3 4
    sll.insert(-100, 1000)
    sll.insert(2, 100)
    sll.insert(100, 10)
    sll.travel()

    print("-"*10)    
    print(sll.search(3))
    print(sll.search(999))
    sll.remove(3)
    sll.travel()
    sll.remove(1000)
    sll.travel()
    sll.remove(10)
    sll.travel()
```
```python
# == 判斷返回T/F
In [14]: a = None
In [15]: print(a==None)
True

# len
  __sll      cont=0__node1     cont=1__node2      cont2__node3    cont=3
 |_head| -> |elem = 100  |    |elem = 10   |     |elem = 10   |
 |     |    |next = node2| -> |next = node3| ->  |next = None | -> None
  ‾‾‾‾‾      ‾‾‾‾‾‾‾‾‾‾‾‾      ‾‾‾‾‾‾‾‾‾‾‾‾       ‾‾‾‾‾‾‾‾‾‾‾‾
   ->None 0       +1=1              +1=2              +1=3
```
### 鏈表 vs 順序表
|操作|鏈表|順序表|
|:--:|:--:|:--:|
|訪問|O(n)|O(1)|
|頭插(刪)|O(1)|O(n)|
|尾插(刪)|O(n)|O(1)|
|中插(刪)|O(n)|O(n)|
||離散|連續|
- 優點: 有效運用『分散』的內存(順序表: 連續內存)
- 缺點: 
    - 單個節點所需空間較大
        - 每個節點都需要存數據跟鏈接
        - 順序表只需要存一次(表頭信息)
    - 無法一次性定位

### 雙鏈表
```
     prev __ next  -> prev __ next  -> prev __ next 
p-> |None| 1|0x66|   |0x55|11|0x87|   |0x66|20| ⊥  |
     ‾‾‾‾ ‾‾ ‾‾‾‾  <- ‾‾‾‾ ‾‾ ‾‾‾‾  <- ‾‾‾‾ ‾‾ ‾‾‾‾
         0x55             0x66             0x87
```
```python
#coding:utf-8
from singleLinkList import SingleLinkList

class Node(object):
    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 == None

    def length(self):
        """"""
        cur = self.__head
        content = 0
        while cur != None:
            content+=1
            cur = cur.next
        return content

    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.prev = node
        #self.__head = node
        # 順序二
        self.__head = node
        node.next.prev = node

    def append(self, item):
        """尾插法"""
        node = Node(item)
        if self.is_empty():
            self.__head = node
        else:
            cur = self.__head
            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:
            node = Node(item)
            cur = self.__head
            count = 0
            while count < pos:
                count +=1
                cur = cur.next
            node.prev = cur.prev
            node.next = cur
            # 順序一
            cur.prev.next = node
            cur.prev = node
            # 順序二
            #cur.prev = node
            #node.prev.next = node

    def remove(self, item):
        """"""
        cur = self.__head
        while cur != None:
            if cur.elem == item:
                if cur == self.__head:
                    self.__head = cur.next
                    # 如果只有一個節點
                    # 那個next會指向None
                    # 而None沒有prev
                    # 故應判斷cur.next is True(不是None)
                    if cur.next:
                        cur.next.prev = None
                else:
                    # 理由同上
                    if cur.next:
                        cur.next.prev = cur.prev
                    cur.prev.next = cur.next
                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(dll.is_empty())
    print(dll.length())

    dll.append(1) 
    print(dll.is_empty())
    print(dll.length())
    print("-"*10)    
    dll.append(2)
    dll.add(99)
    dll.append(3)
    dll.append(4) #99 1 2 3 4
    dll.insert(-100, 1000)
    dll.insert(2, 100)
    dll.insert(100, 10)
    dll.travel()

    print("-"*10)    
    print(dll.search(3))
    print(dll.search(999))
    dll.remove(3)
    dll.travel()
    dll.remove(1000)
    dll.travel()
    dll.remove(10)
    dll.travel()
```

### 單向循環鍊錶
> 尾節點轉回來連到頭節點
```python
#coding:utf-8

class Node(object):
    def __init__(self, elem):
        self.elem = elem
        self.next = None

class SingleCycleLinkList(object):
    """"""
    def __init__(self, node=None):
        self.__head = node
        # 先判斷節點不為None
        if node:
            node.next = node

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

    def length(self):
        """"""
        if self.is_empty():
            return None
        cur = self.__head
        # 用next會少一次, 故起始設1
        content = 1
        # while cur != None:
        # 循環列表會從頭, 故不會有None
        # cur == self.__head也無法使用,
        # 因為頭節點本來就會指向self.__head,
        # 故會無法判斷是第一輪還是循環回來的 
        while cur.next != self.__head:
            content+=1
            cur = cur.next
        return content

    def travel(self):
        """遍歷列表"""
        if self.is_empty():
            return None
        cur = self.__head
        while cur.next != self.__head:
            print(cur.elem , end=" ")
            cur = cur.next
        # 尾節點未打印
        print(cur.elem)
    
    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
            self.travel()

    def add(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
            self.__head = node
            #cur.next = node
            cur.next = self.__head

    def insert(self, pos, item):
        """"""
        if pos <=0:
            self.add(item)
        elif pos > (self.length()-1):
            self.append(item)
        else:
            node = Node(item)
            pre = self.__head
            count = 0
            while count < (pos-1):
                count +=1
                pre = pre.next
            node.next = pre.next
            pre.next = node
         
    def remove(self, item):
        """"""
        # 一開始就None
        if self.is_empty():
            return
        cur = self.__head
        pre = None
        while cur.next != self.__head:
            if cur.elem == item:
                # 頭節點
                if cur == self.__head:
                    temp = self.__head
                    while temp.next != self.__head:
                        temp = temp.next
                    self.__head = cur.next
                    temp.next = self.__head
                # 中間節點
                else:
                    pre.next = cur.next
                # 用break退出循環後會執行下面的if,
                # 然後被指向None..., 
                # 故結束後直接return退出def
                # break
                return
            else:
                pre = cur
                cur = cur.next
        # 退出循環後, cur指向尾節點
        if cur.elem == item:
            # 只有一個節點
            if pre == None:
                self.__head = None
            else:
                pre.next = cur.next


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

if __name__ == "__main__":

    sll = SingleCycleLinkList()
    print(sll.is_empty())
    print(sll.length())

    sll.append(1)
    print(sll.is_empty())
    print(sll.length())
    
    print("-"*10)
    sll.append(2)
    sll.add(99)
    sll.append(3)
    sll.append(4) #99 1 2 3 4
    sll.insert(-100, 1000)
    sll.insert(2, 100)
    sll.insert(100, 10)
    sll.travel()
    print("-"*10)
    
    print(sll.search(3))
    print(sll.search(999))

    sll.remove(3)
    sll.travel()
    sll.remove(1000)
    sll.travel()
    sll.remove(10)
    sll.travel()
```

### 思考
> - 雙向循環鏈錶
> - 鏈表做表頭信息
```
     __      prev __ next  -> prev __ next 
p-> |  | -> |None| 1|0x66|   |0x55|11|0x87|
     ‾‾      ‾‾‾‾ ‾‾ ‾‾‾‾  <- ‾‾‾‾ ‾‾ ‾‾‾‾ 
             0x55             0x66     
```

## 棧(Stack)
> - 一種線性容器
> - 只允許從一端操作
> - 後進先出(Last In First Out, LIFO)
```python
#coding:utf-8


class Stack(object):
    """"""

    def __init__(self):
        self.__list = []

    def push(self, item):
        """"""
        # 視資料結構而定
        # 尾插
            # 順序表O(1)
            # 鏈表O(n)
        # 頭插
            # 順序表O(n)
            # 鏈表O(1)
        # 這裡使用順序表寫, 故用尾插
        self.__list.append(item)
        # self.__list.insert(0, item)


    def pop(self):
        """"""
        return self.__list.pop()
        # return self.__list.pop(0)    


    def peek(self):
        """"""
        if self.__list:
            return self.__list[-1]
        else:
            return None

    def is_empty(self):
        """"""
        return self.__list == []

    def size(self):
        """"""
        return len(self.__list)


if __name__ == "__main__":
    s = Stack()
    print(s.is_empty())
    s.push(1)
    s.push(2)
    s.push(3)
    print(s.is_empty())
    print(s.size())
    print(s.pop())
    print(s.pop())
    print(s.pop())
    print(s.is_empty())
```

## 隊列(queue)
> - 一種線性容器
> - 只允許一端進一端出
> - 先進先出(FIFO)
```python
#coding:utf-8

class Queue(object):
    """"""
    def __init__(self):
        self.__list = []
    
    def enqueue(self, item):
        """"""
        # 當出入隊頭尾插複雜度剛好相反時,
        # 視使用頻率而定
        self.__list.append(item)
        # self.__list.insert(0, item)

    def dequeue(self):
        """"""
        return self.__list.pop(0)
        #return self.__list.pop()

    def is_empty(self):
        """"""
        return self.__list == []

    def size(self):
        """"""
        return len(self.__list)

if __name__ == "__main__":
    q = Queue()
    print(q.is_empty())
    q.enqueue(1)
    q.enqueue(2)
    q.enqueue(3)
    print(q.size())
    print(q.dequeue())
    print(q.dequeue())
    print(q.dequeue())
    print(q.size())
```

### 雙端隊列(deque, double-ended queue)
> 雙進雙出
```python
#coding:utf-8

class Deque(object):
    """"""
    def __init__(self):
        self.__list = []
    
    def add_front(self, item):
        """頭插"""
        self.__list.insert(0, item)
    
    def add_rear(self, item):
        """尾插"""
        self.__list.append(item)

    def remove_front(self):
        """頭刪"""
        return self.__list.pop(0)
    
    def remove_rear(self):
        """尾刪"""
        return self.__list.pop()

    def is_empty(self):
        """"""
        return self.__list == []

    def size(self):
        """"""
        return len(self.__list)

if __name__ == "__main__":
    q = Deque()
    print(q.is_empty())
    q.add_front(1)
    q.add_front(2)
    print(q.size())
    print(q.remove_front())
    print(q.remove_front())
    print(q.size())
```

## 排序算法(Sorting Algorithm)

### 穩定性
```
# li = [(8,0),(3,1),(2,2),(8,3),(4,4)]
還小至大排序
(2,2),(3,1),(4,4),(8,0),(8,3) > 依序 > 穩定
(2,2),(3,1),(4,4),(8,3),(8,0) > 改序 > 不穩定
```

### 冒泡排序(Bubble Sort)
> 重複遍歷排序
> 一次比較兩個
```python
#coding:utf-8

# [0] [1] [2] [3] n = 4

# 第一趟比較
  # [0]<>[1] [1]<>[2] [2]<>[3]
  # 此時 [3] 會得到最大的數
  # 總共比較了 n-1 次

# 第二趟比較
  # [0]<>[1] [1]<>[2]
  # [5]已經是最大的數了，故不需要再參與比較
  # 此趟會得到[2]第二大的數
  # 總共比較了 n-2 次

# 第三趟比較
  # [0]<>[1]
  # [1]得到第三大的數
  # 總共比較了 n-3 次


# 總共會跑 n-1 趟 (確定[1]~[3]) 的數
  # [1]~[3] 都確定時, [0] 就確定了

''' 以前寫的東西
def bubble_sort(alist):
    n = len(alist) # 假設n=4
    for j in range(0, n-1):
        """Y軸"""
        print(j,"-"*10)
        for i in range(0, n-1-j):
            """X軸"""
            # 直接從0開始, 取首位比較方便
              # 第1圈(j=0)比較 n-1(3)次 > n-1-0
              # 第2圈(j=1)比較 n-2(2)次 > n-1-1
              # 第3圈(j=2)比較 n-3(1)次 > n-1-2
            if alist[i] > alist[i+1]:
                alist[i], alist[i+1] = alist[i+1], alist[i]
            print(i,alist)
'''
# 19/ 11/ 19 的新想法
  # 把j改成1, 表示第一圈, 這樣比較易讀
def bubble_sort(alist):
    n = len(alist)
    count = 0
    for j in range(1,n):
        print('第%d圈'%j)
        count += 1
        for i in range(0,n-j):
            if alist[i] > alist[i+1]:
                alist[i], alist[i+1] = alist[i+1], alist[i]
            count += 1
            print('i = %d: '%(i), alist)
    print(count)
    
if __name__ == "__main__":
    li = [54,26,93,17,77,31,44,55,20]
    bubble_sort(li)
    
# j = 0 [26, 54, 17, 77, 31, 44, 55, 20, 93]
# j = 1 [26, 17, 54, 31, 44, 55, 20, 77, 93]
# j = 2 [17, 26, 31, 44, 54, 20, 55, 77, 93]
# j = 3 [17, 26, 31, 44, 20, 54, 55, 77, 93]
# j = 4 [17, 26, 31, 20, 44, 54, 55, 77, 93]
# j = 5 [17, 26, 20, 31, 44, 54, 55, 77, 93]
# j = 6 [17, 20, 26, 31, 44, 54, 55, 77, 93]
# j = 7 [17, 20, 26, 31, 44, 54, 55, 77, 93]

# 從結果可以看到，有可能還沒跑完所有趟數就已經完全排好了
# 此時應該用判斷來跳出而簡化時間複雜度
```
```python
#coding:utf-8

# 優化
'''以前的我寫法
def bubble_sort(alist):
    n = len(alist)
    for j in range(0, n-1):
        """Y軸"""
        count = 0
        print(j,"-"*10)
        for i in range(0, n-1-j):
            """X軸"""
            if alist[i] > alist[i+1]:
                alist[i], alist[i+1] = alist[i+1], alist[i]
                count+=1 # 如有交換, 計數+1
            print(i,count,alist)
        # 如果都沒換表示順序正常, 跳出
        if 0 == count:
            break
'''
# 19/ 11/ 19 的新想法
def bubble_sort(alist):
    n = len(alist)
    count = 0 # 專門紀錄時間複雜度
    for j in range(1,n):
        print('第%d圈'%j)
        count+=1
        isSort = True # 一開始假設已經排好了
        
        for i in range(0,n-j):
            if alist[i] > alist[i+1]:
                alist[i], alist[i+1] = alist[i+1], alist[i]
                isSort = False # 如果有進if交換, 表示還沒排好
            count +=1
            print('i = %d: '%(i), alist)
        print(isSort)
        if isSort: # 如果跑完整趟內圈for都沒進if, 表示已經排序完成, 直接跳出
            break
    print(count)

if __name__ == "__main__":
    #li = [54,26,93,17,77,31,44,55,20]
    li = [1,2,3,5,4]
    bubble_sort(li)
# 最優O(n)
# 最壞O(n^2)
# 穩定性: 穩定
# li = [(8,0),(3,1),(2,2),(8,3),(4,4)]
    # (3,1),(8,0),(2,2),(8,3),(4,4)
    # (3,1),(2,2),(8,0),(8,3),(4,4) 依樣大，不換
    # (3,1),(2,2),(8,0),(4,4),(8,3)
    # ...
    # (2,2),(3,1),(4,4),(8,0),(8,3) 最後8,0還是在8,3前面
```

### 選擇排序(Selection Sort)
> - 從序列中找到最小(大)值, 放到前面依序排列
![](https://i.imgur.com/Ashdkvn.gif)

```python
#coding:utf-8

def selection(alist):
    """"""
    n = len(alist)
    print(alist)
    for j in range(n-1):
        min = j
        print(j,'-'*10)
        #for i in range(1,n):
        for i in range(j+1, n):
            if alist[min] > alist[i]:
                min = i
            print(min)
        alist[min], alist[j] = alist[j], alist[min]
        print(alist)


#    alist = [54,226,93,17,77,31,44,55,20]
#             0   1  2  3  4  5  6  7  8
#   
#    j = 0
#    min = 0 vs 0+1...
#    alist[0], alist[3]= alist[3], alist[0] 
#    
#    j = 1
#    min = 1 vs 1+1...  j vs j+1
#    min = 2,3,4,5,6,7,8
#    [1],[8]=[8],[1]

if __name__ == "__main__":
    alist = [54,226,93,17,77,31,44,55,20]
    selection(alist)

# 最優O(n^2) 每個都必須比較
# 最壞O(n^2)
# 穩定性: 不穩定

# li = [(8,0),(3,1),(2,2),(8,3),(4,4)]
# max = 8,0 > (3,1),(2,2),(8,3),(4,4),(8,0)
# max = 8,3 > (3,1),(2,2),(4,4),(8,3),(8,0) 8,3跑到前面了
```

### 插入排序(insert sort)
> - 從無序序列中取一個與有序序列比較,
> - 與選擇排序不同處:
>   - 選擇排序
>     - 選擇排序為在無序序列中選擇最小(大)至有序序列依序排列
>     - 被選擇者所排序位置為固定
>   - 插入排序
>     - 插入排序為選擇後與有序序列比較,
>     - 有序序列為浮動的

```python
#coding:utf-8

def insertSort(alist):
    
    n = len(alist)
    print(alist)
    for j in range(1, n):
        # i 代表起始位置
        i = j
        # 從無序序列取起始位置(i)值與有序序列比較
        while i > 0:
            # 相比滿足條件換位
            if alist[i-1] > alist[i]:
                alist[i-1], alist[i] = alist[i], alist[i-1]
                i-=1
            # 不滿足表示正確序列, 跳出
            else:
                break
            print(alist)

#    26, 54, 93  17
#    i-3 i-2 i-1 i 
#     26,54, 17, 93
#            i-1
if __name__ == "__main__":
    
    li = [54,26,93,17,77,31,44,55,20]
    insertSort(li)
# 最優O(n)
# 最壞O(n^2)
# 穩定
```

### ShellSort
> - 插入排序改版
> - Shell步長為1相當於Insert
```python
#coding:utf-8

def shell_sort(alist):
    """"""
    # n = 9
    n = len(alist)
    # gap = 4
    gap = n // 2
    print(alist)
    print("-"*10)
    while gap>=1:
        for i in range(gap, n):
            print(i)
            while i>=gap:
                if alist[i] < alist[i-gap]:
                    alist[i], alist[i-gap] = alist[i-gap], alist[i]
                    i-=gap
                else:
                    break
            print(alist)
        print("-"*10)
        # 縮短步長
        gap //= 2


if __name__=="__main__":
    li = [54,26,93,17,77,31,44,55,20]
    shell_sort(li)
    #print(li)

# 最優: 依步長而定O(n^1.3)
# 最壞: O(n^2)
# 不穩定
```

### 快速排序(Quicksort)

> - 思想:
>   - 將第一個值插入中間
>   - 形成左邊比首值小, 右邊比首值大的效果
>   - 兩邊再重複同樣操作, 直到剩一個值為止
> - 使用非常頻繁！最重要！  
```python
#coding:utf-8

def quick_sort(alist, first, last):
    """"""
    if first >= last:
        return
    #n = len(alist)
    #middle_value = alist[0]
    #low = 0
    #hight = n-1
    middle_value = alist[first]
    low = first
    hight = last
    print(middle_value, low, hight)
    
    # 把大於mid的都丟到右邊, 小於的都丟左邊
    while low < hight:
        while low < hight and alist[hight] >= middle_value:
            hight-=1
        alist[low] = alist[hight]
        print("-", alist)

        while low < hight and alist[low] < middle_value:
            low+=1
        alist[hight] = alist[low]
        print("|", alist)
    # 退出時,low = hight
    # 此時即分線, 放入middle
    alist[low] = middle_value
    print(alist)

    # 接著使用嵌套方式重複執行
    #quick_sort(alist[:low])
    #quick_sort(alist[low+1:])
    # 使用切片傳值返回的是一個新的列表(註),
    # 不論怎麼操作都是對新列表操作而非原本的list > 白忙一場
    
    # mid左邊 
    quick_sort(alist, first, low-1)
    # mid右邊
    quick_sort(alist, low+1, last)

if __name__ == "__main__":
    li = [54,26,93,17,77,31,44,55,20]
    quick_sort(li, 0, len(li)-1)
    #print(li)

# 最優O(nlogn)
  # while low<hight 全部都要跑一遍 > n
  # 嵌套次數視數量而定, 每次切半 > log2n
# 最壞O(n^2)
# 不穩定
```
```python
# 註
In [1]: def test(a): 
   ...:     print(id(a)) 
   ...:     test(a) 
   ...:                                                                                  
In [2]: b = [1,2,3,4,5,6]                       
In [3]: test(b)                         
4437755336
4437755336
4437755336
...

# 切片返回的是新的指向
In [4]: def test(a): 
   ...:     print(id(a)) 
   ...:     test(a[:3]) 
   ...:                                         
   
In [5]: test(b)                          
4437755336
4440166280
4440138504
...
```
> - 最優O(nlogn)
>   - while low<hight 全部都要跑一遍 > O(n)
>   - 嵌套次數視數量而定, 每次切半 > log~2~n >O(logn)
> - 最壞O(n^2^)
>   - 已經排序完成的話再執行的效果, 
>   - 每次middle_value都等於alist[0]
>   - 這樣就要切n次, 故O(n^2^)
> - 不穩定

### 歸併排序(Merge Sort)
> - 全部拆成一個後再兩兩依序合併
![](https://i.imgur.com/NV8TEAo.gif)



```python
#coding:utf-8

def merge_sort(alist):
    """"""
    print(alist)
    n = len(alist)
    if n <= 1 :
        return alist 
    # 開拆
    mid = n // 2

    left_li = merge_sort(alist[:mid])
    right_li = merge_sort(alist[mid:])
    

    # 開組
    left_pointer = 0
    right_pointer = 0
    result = []
    
    print(left_li, right_li)
    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:]
    result += right_li[right_pointer:]
    print(result)
    return result


if __name__ == "__main__":
    li = [54,26,93,17,77,31,44,55,20]
    merge_li = merge_sort(li)
    #print(li)
    #print(merge_li)
```
```python
# 註
In [1]: a = [1,2,3]
In [2]: a[4:]                          
Out[2]: []
```
> - 最優O(nlogn)
>   - 每次都要兩兩比較 > n
>   - 拆幾次就合幾次, 亦即合 log~2~n 次
> - 最壞O(nlogn)
>   - 每次都切半, 沒有特殊切法
>   - 快
>   - 但是必須產生額外的空間來運行
> - 穩定


## 搜索
### 二分查找( Binary Search)

> - 每次切半, 視查找東西在一半之前還後,
> - 接著重複過程到找到或不能再切為止
> - 使用條件:
>   - 有序 : 要知道在前還後
>   - 支持下標索引(順序表) : 切半用

```python
#coding:utf-8

def binary_search(alist, item):
    """遞歸"""
    n = len(alist)
    mid = n // 2
    if n > 0:
        if alist[mid] == item:
            return True
        elif alist[mid] > item:
            return binary_search(alist[:mid], item)
        elif alist[mid] < item:
            return binary_search(alist[mid+1:], item)
    return False

def binary_search_2(alist, item):
    """非遞歸"""

    n = len(alist)
    first = 0
    last = n-1

    while first <= last:
        mid = (first+last) // 2
        if alist[mid] == item:
            return mid
        elif item < alist[mid]:
            last = mid-1
        elif alist[mid] < item:
            first = mid+1
    return False


if __name__ == "__main__":
    li = [1,2,3,4,5,6]
    #print(binary_search(li, 1))
    #print(binary_search(li, 6))
    #print(binary_search(li, 7))


    print(binary_search_2(li, 1))
    print(binary_search_2(li, 6))
    print(binary_search_2(li, 7))
```
> - 最壞: 每次切半可切幾次 > log~2~n > O(logn) 
> - 最優: 1 > 一切就中
> - vs.`for i in range(n)`
>   - 最壞: O(n)
>   - 最優: 1


## 樹
![](https://i.imgur.com/zsK9j5X.png)


> - 特點：
>   - 每個節點下的節點稱為『子節點』
>   - 沒有父節點的節點稱為『根節點』
>   - 每個子節點只有一個父節點
> - 術語：
>   - 節點度: 幾個下級(B:3, G:2)
>   - 樹度: 最大節點度(B>3)
>   - 枝葉點(終端節點): 最下層的節點(K,J,F,L,O,P)
>   - 節點層次: 1>A, 2>BC, 3>DEFGH...
>   - 樹的深度(高度): 最大層次(5)
> - 種類:
>   - 無序樹(自由樹)
>   - 有序樹
>     - 二叉樹: 樹的度為2
>       - 完全二叉樹: 除了最底層外，每層都達最大度
(假設有五層, 1>2>4>8>n)
>       - 滿二叉樹: 所有層都滿(1>2>4>8>16)
>       - 平衡二叉樹: 子樹高度差不大於1
>       - 排序二叉樹: 類似二分查找邏輯
>     - 霍夫曼樹: 
>     - B樹
>  
> - 存儲:
>   - 順序存儲
>     ![](https://i.imgur.com/XLVYinO.png)
>   - 鏈式存儲(常用)

### 二叉樹
```python
#coding:utf-8

class Node(object):
    def __init__(self, elem):
        self.elem = elem
        self.lchild = None
        self.rchild = None

class Tree(object):
    def __init__(self):
        self.root = None

    def add(self, elem):
        node = Node(elem)


        if self.root is None:
            self.root = node
            return
        queue = [self.root]
        # 註1
        while queue:
            cur_node = queue.pop(0)
            if cur_node.lchild == None:
                cur_node.lchild = node
                return
            else:
                queue.append(cur_node.lchild)

            if cur_node.rchild == None:
                cur_node.rchild = node
                return
            else:
                queue.append(cur_node.rchild)


    def breadth_travel(self):
        """廣度遍歷(層次遍歷)"""
        if self.root == 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, root):
        """先序遍歷(根左右)"""
        if root is None:
            return
        print(root.elem, end="")
        self.preorder(root.lchild)
        self.preorder(root.rchild)

    def inorder(self, root):
        """中序遍歷(左根右)"""
        if root is None:
            return
        self.inorder(root.lchild)
        print(root.elem, end="")
        self.inorder(root.rchild)

    def postorder(self, root):
        """後序遍歷(左右根)"""
        if root is None:
            return
        self.postorder(root.lchild)
        self.postorder(root.rchild)
        print(root.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(" ")
```
```python
# 註1
In [1]: bool([])                      
Out[1]: False
In [3]: bool([None])                    
Out[3]: True # 即使[]元素僅為None, 判斷一樣事True
```