前面介紹用linked list寫Binary tree，今天給大家demo用python list(固定大小(with capacity limited))寫。不同於linked list存取的方式，我們將leftchild存在index=2(parent_index)的位子，rightchild存在index=2(parent_index)+1，index=0的位子不用如下圖:

class BT_List:
    # 創建一個有限大小的Binary，tree Time: O(1), Space: O(1)
    # 因為0不用，所以我們的customList size要+1
    def __init__(self, maxsize):
        self.customList = [None]*(maxsize+1)
        self.maxsize = maxsize
        self.lastnode = 0
        
    # 可以把樹裡的東西都print出來: Time: O(n), Space: O(1) 
    def __str__(self):
        res = ''
        for i in range(1, self.lastnode+1):
            res += str(self.customList[i])
            res += ' '
        return res
        
    # 在樹裡插入一個節點: Time:O(1), Space: O(1)
    # 考慮到樹是有大小限制的
    def insertNode(self, value):
        if self.lastnode == self.maxsize:
            return 'The tree is full!'
        else:
            self.lastnode += 1
            self.customList[self.lastnode] = value
            return 'The node is inserted'
            
    # 搜尋節點: Time: O(n), Space: O(1)
    def searchNode(self, value):
        for i in self.customList:
            if i == value:
                return 'Success'
        return 'Not found!'

    # preordertraversal: Time: O(n), Space: O(n)
    def preordertraversal(self, index):
        if index > self.lastnode:
            return
        else:
            print(self.customList[index])
            self.preordertraversal(2*index)
            self.preordertraversal(2*index+1)

    # inordertraversal: Time: O(n), Space: O(n)
    def inordertraversal(self, index):
        if index > self.lastnode:
            return
        else:
            self.inordertraversal(2*index)
            print(self.customList[index])
            self.inordertraversal(2*index+1)

    # postordertraversal: Time: O(n), Space: O(n)
    def postordertraversal(self, index):
        if index > self.lastnode:
            return
        else:
            self.postordertraversal(2*index)
            self.postordertraversal(2*index+1)
            print(self.customList[index])

    # levelordertraversal: Time: O(n), Space: O(n)
    def levelordertraversal(self, index):
        if self.lastnode == 0:
            return 'There is no element in the tree'
        else:
            for i in range(1, len(self.customList)):
                if self.customList[i] == None:
                    pass
                else:
                    print(self.customList[i])

    # 我們要將用最後一個node取代被刪掉的node
    # Time: O(n), Space: O(1)
    def deleteNode(self, value):
        if self.lastnode == 0:
            return 'There is no element in the tree'
        for i in range(1, len(self.customList)):
            if self.customList[i] == value:
                self.customList[i] = self.customList[self.lastnode]
                self.customList[self.lastnode] = None
                self.lastnode -= 1
                return 'The node is deleted !!!'
        return 'Cannot find the node!'
    # 刪除整個二元樹
    # Time: O(1), Space: O(1)
    def deleteall(self):
        self.customList = None
        self.lastnode = 0
        self.maxsize = 0
        return 'The tree is deleted'

那用昨天的例子來放在python list來看看:

BT = BT_List(8)
BT.insertNode('Drinks')
BT.insertNode('Hot')
BT.insertNode('Cold')
BT.insertNode('Chocolate')
BT.insertNode('Coffee')
BT.insertNode('Coke')
BT.insertNode('Fenta')
print(BT)
>> Drinks Hot Cold Chocolate Coffee Coke Fenta
print('===preordertraversal===')
BT.preordertraversal(1)
print('===inordertraversal===')
BT.inordertraversal(1)
print('===postordertraversal===')
BT.postordertraversal(1)
print('===levelordertraversal')
BT.levelordertraversal(1)
>> ===preordertraversal===
    Drinks
    Hot
    Chocolate
    Coffee
    Cold
    Coke
    Fenta
    ===inordertraversal===
    Chocolate
    Hot
    Coffee
    Drinks
    Coke
    Cold
    Fenta
    ===postordertraversal===
    Chocolate
    Coffee
    Hot
    Coke
    Fenta
    Cold
    Drinks
    ===levelordertraversal
    Drinks
    Hot
    Cold
    Chocolate
    Coffee
    Coke
    Fenta
# 插入Tea
BT.insertNode('Tea')
print(BT)
>> Drinks Hot Cold Chocolate Coffee Coke Fenta Tea
BT.deleteNode('Tea')
print(BT)
>>　Drinks Hot Cold Chocolate Coffee Coke Fenta

到這裡相信大家都對用Python List做Binary Tree非常了解了。下面是兩種方法BigO的比較:

參考資料:
本文主要為udemy課程: The Complete Data Structures and Algorithms Course in Python的學習筆記，有興趣的人可以自己上去看看。