二叉樹其實直觀理解起來還算比較簡單，它是一個樹結(jié)構(gòu)，也就是層級結(jié)構(gòu)，每一層每一個父節(jié)點最多有兩個子節(jié)點。二叉樹用來搜索效果不錯，因為只要保證左節(jié)點比父節(jié)點小，右節(jié)點比父節(jié)點大，那么搜索下來時間復(fù)雜度其實就是很理想的O(logn)。
但是對于一個python新手來說，二叉樹也是比較難實現(xiàn)的，因為按理說樹結(jié)構(gòu)其實應(yīng)該是一種“鏈表”，但是python里面似乎可能好像沒有這種結(jié)構(gòu)，Java是有的（有人開始罵python是一門很low的語言了）……所以一開始我理解起來還很困難！這個怎么能把樹上的每個節(jié)點串起來啊，怎么表示關(guān)系啊，然后我去刷stackoverflow，還真的慢慢地理解了它（的基礎(chǔ)）。
1. 建立節(jié)點
如上文所述，二叉樹的結(jié)構(gòu)就是每一個父節(jié)點都有不超過兩個子節(jié)點。那么對于二叉樹的每個點建一個類，這個類中規(guī)定三個屬性：節(jié)點自身的值value，節(jié)點的左子節(jié)點值left，節(jié)點的右子節(jié)點值right。對于每一個點而言，在初始化的時候都把一個值賦給它自己，同時左右子節(jié)點置為空。這個很好理解吧？葉子節(jié)點的左右子節(jié)點就會一直為空了，但是
代碼：
class TreeNode(object):
def __init__(self,value):
self.value = value
self.left = None
self.right = None
2. 建立搜索樹
現(xiàn)在我們有了點，看起來很簡單，但是該怎么把樹建起來呢？
二叉樹建樹其實就像上面說的，是一個很簡單明確的過程，首先需要一個根節(jié)點，然后每一次新的節(jié)點過來，就跟根節(jié)點比較，比它小就作為左子節(jié)點，比它大就作為右子節(jié)點，然后依次跟下一層比較，直到自己成為葉子節(jié)點停止。
算法的要點是利用遞歸算法 recursion，說實話靠我自己想可能還是太難太抽象了點。但是如果你要去領(lǐng)會它的意思，做得也就是這件事：
class BinaryTree(object):
def insert(self,root, node):
if root is None:
return node
if node.value < root.value:
root.left = self.insert(root.left, node)
else:
root.right = self.insert(root.right, node)
return root
我們定義了一個新的類 二叉樹，這個類里面只有一個insert方法，就是插入一個新的節(jié)點到已生成的樹中。這個方法的記憶點有兩塊：
1.輸入?yún)?shù)：
此處的參數(shù)應(yīng)該是已生成的樹節(jié)點，和準(zhǔn)備加入的新節(jié)點，這兩者的類型都需要是剛剛定義的帶有左右子節(jié)點屬性的類；
2.遞歸，采用三個條件判斷：
如果當(dāng)前節(jié)點為空就返回新的節(jié)點；如果當(dāng)前節(jié)點不為空且比新的節(jié)點值大，那么就遞歸地判斷當(dāng)前節(jié)點的左子節(jié)點和新節(jié)點的關(guān)系，直到當(dāng)前節(jié)點為空；比新的節(jié)點小就遞歸地判斷當(dāng)前節(jié)點的左子節(jié)點和新節(jié)點的關(guān)系，直到當(dāng)前節(jié)點為空返回。
3. 生成二叉搜索樹：
那么下面我們就用一個循環(huán)語句來生成一棵二叉搜索樹吧。
root = Node(5)
tree = BinaryTree()
for i in [2,11,7,3,9,8,4,6,1]:
tree.insert(root,Node(i))
現(xiàn)在基本上大功告成了！當(dāng)你興奮地敲下run之后，當(dāng)當(dāng)當(dāng)當(dāng)——
程序運行完，啥也沒顯示，就完了。
那是因為我們沒有把樹“遍歷”地展示出來，python有一個二叉樹庫 binarytree，可以用pip安裝，允許你打印出樹的結(jié)構(gòu),可以用非常直觀的方式來構(gòu)建二叉樹，看看人家的示例：
>>> from binarytree import Node
>>> root = Node(3)
>>> root.left = Node(2)
>>> root.right = Node(7)
>>> root.left.left = Node(4)
>>> root.left.right = Node(1)
>>> print(root)
__3
/ \
2 7
/ \
4 1
4. 二叉樹的三種遍歷算法及排序
當(dāng)我們已經(jīng)有一個二叉樹的時候，有哪幾種方式來遍歷它呢？
這是一個面試常見考點，相信很多小伙伴腦子里已經(jīng)蹦出了答案：前序遍歷，中序遍歷，后序遍歷
那么哪種遍歷方法可以使二叉樹輸出有序呢？
中序遍歷
在說到二叉樹遍歷的前序，中序和后序的時候，需要牢牢記住，這里的前，中，后的順序，都是相對于節(jié)點本身而言的。所以“前序遍歷”實際上的意思是：把遍歷我這個父節(jié)點先放到前面，然后再左子節(jié)點，然后再右子節(jié)點，一直要保證這個順序。中序遍歷就是把遍歷父節(jié)點放在中間去進(jìn)行，先左子節(jié)點，然后再右子節(jié)點，子節(jié)點的遍歷需要注意的是這個過程也是遞歸的。后序遍歷呢，就是先左子節(jié)點，然后右子節(jié)點，最后再遍歷父節(jié)點。
所以，自然，由于二叉樹本身生成的時候的特性，再遍歷的時候如果采用中序，就能夠保證整個輸出是從小到大有序的了。
所以我們定義三個新的函數(shù)來表示這三種遍歷方法：
# 前序遍歷
def pre_order_print(node):
# self -- left -- right
print(node.value,end=' ')
if node.left:
pre_order_print(node.left)
if node.right:
pre_order_print(node.right)
# 中序遍歷
def mid_order_print(node):
# left --self -- right
if node.left:
mid_order_print(node.left)
print(node.value,end=' ')
if node.right:
mid_order_print(node.right)
# 后序遍歷
def after_order_print(node):
# left-- right--self
if node.left:
after_order_print(node.left)
if node.right:
after_order_print(node.right)
print(node.value, end=' ')
- 完整的程序
class Node(object):
def __init__(self,value):
self.value = value
self.left = None
self.right = None
class BinaryTree(object):
def insert(self, root, node):
if root is None:
return node
if node.value < root.value:
root.left = self.insert(root.left, node)
else:
root.right = self.insert(root.right, node)
return root
def pre_order_print(node):
# self -- left -- right
print(node.value,end=' ')
if node.left:
pre_order_print(node.left)
if node.right:
pre_order_print(node.right)
def mid_order_print(node):
# mid --self -- right
if node.left:
mid_order_print(node.left)
print(node.value,end=' ')
if node.right:
mid_order_print(node.right)
def after_order_print(node):
# left-- right--self
if node.left:
after_order_print(node.left)
if node.right:
after_order_print(node.right)
print(node.value, end=' ')
root = Node(5)
tree = BinaryTree()
for i in [2,11,7,3,9,8,4,6,1]:
tree.insert(root,Node(i))
mid_order_print(root)
這樣輸出的結(jié)果就是有序的了。
