2015年10月11日 星期日

[Python] 實作Binary Tree

enter image description here
因為不是科班出身,所以對於資料結構和演算法都沒什麼概念,利用雙十廉價的機會好好惡補了一番Orz…
Binary Tree(簡稱BT)在資料結構中是很基本的概念,概念上是每個節點都有左右兩個子節點,每個節點儲存一個值,最上面會有一個起始節點(或稱為root),每往下長一層就多了2**n個節點,以此類推.從BT衍伸出許多相關概念例如heap或各種樹,可能的優點包括加快搜尋速度或是排序速度等等,所以先了解BT是很重要的.



BT是由節點構成,每個節點在python中可以表示為這個樣子
class Node(object):
    def __init__ (self, x):
        self.value = x
        self.left = None
        self.right = None
創造一個Node的物件,每個Node裡面只有三個值:
1. Node的數值self.value
2. 左邊子Node和右邊子Node self.rightself.left ,預設值為None
接著要幫這個Node建立新增子Node的方法:
    def insertRight(self, x):
        if self.right == None:
            self.right = Node(x)
        else:
            newNode = Node(x)
            newNode.right = self.right
            self.right = newNode.right
這是插入右邊的方法:
  • 第一個條件判斷如果要插入的右邊沒有東西self.right == None就在右邊建立一個新的Node(x) x 為這個Node的value.
  • 如果右邊的子Node已經有東西了,就把右邊的Node往下推一層.
插入左邊的方法也是以此類推:
    def insertLeft(self, x):
        if self.left == None:
            self.left = Node(x)
        else:
            newNode = Node(x)
            newNode.left = self.left
            self.left = newNode.left
這樣子我們就可以透過這些方法來建立一棵小樹:
root = Node(1) #建立根
root.insertLeft(3) #插入左節點
root.insertRight(2) #插入右節點
root.left.insertRight(4) #在左節點上在插入右節點
root.left.insertLeft(5)
root.right.insertRight(6)
最後樹會長成這樣子
     1
   /   \
  3     2
 / \     \      
5  4      6
如果你去看每個節點的內容,會看到一個Node物件和對應的記憶體位置
root.right
#<__main__.Node at 0x106565150>