[Python] 實作Binary Tree

因為不是科班出身，所以對於資料結構和演算法都沒什麼概念，利用雙十廉價的機會好好惡補了一番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.right和self.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>