二叉樹(shù)其實(shí)直觀理解起來(lái)還算比較簡(jiǎn)單若专，它是一個(gè)樹(shù)結(jié)構(gòu)久信，也就是層級(jí)結(jié)構(gòu)窖杀，每一層每一個(gè)父節(jié)點(diǎn)最多有兩個(gè)子節(jié)點(diǎn)。二叉樹(shù)用來(lái)搜索效果不錯(cuò)入篮，因?yàn)橹灰ＷC左節(jié)點(diǎn)比父節(jié)點(diǎn)小陈瘦，右節(jié)點(diǎn)比父節(jié)點(diǎn)大，那么搜索下來(lái)時(shí)間復(fù)雜度其實(shí)就是很理想的O(logn)潮售。
但是對(duì)于一個(gè)python新手來(lái)說(shuō)，二叉樹(shù)也是比較難實(shí)現(xiàn)的锅风，因?yàn)榘蠢碚f(shuō)樹(shù)結(jié)構(gòu)其實(shí)應(yīng)該是一種“鏈表”酥诽，但是python里面似乎可能好像沒(méi)有這種結(jié)構(gòu)，Java是有的（有人開(kāi)始罵python是一門很low的語(yǔ)言了）……所以一開(kāi)始我理解起來(lái)還很困難皱埠！這個(gè)怎么能把樹(shù)上的每個(gè)節(jié)點(diǎn)串起來(lái)啊肮帐，怎么表示關(guān)系啊，然后我去刷stackoverflow边器，還真的慢慢地理解了它（的基礎(chǔ)）训枢。
1. 建立節(jié)點(diǎn)
如上文所述，二叉樹(shù)的結(jié)構(gòu)就是每一個(gè)父節(jié)點(diǎn)都有不超過(guò)兩個(gè)子節(jié)點(diǎn)忘巧。那么對(duì)于二叉樹(shù)的每個(gè)點(diǎn)建一個(gè)類恒界，這個(gè)類中規(guī)定三個(gè)屬性：節(jié)點(diǎn)自身的值value，節(jié)點(diǎn)的左子節(jié)點(diǎn)值left砚嘴，節(jié)點(diǎn)的右子節(jié)點(diǎn)值right十酣。對(duì)于每一個(gè)點(diǎn)而言涩拙，在初始化的時(shí)候都把一個(gè)值賦給它自己，同時(shí)左右子節(jié)點(diǎn)置為空耸采。這個(gè)很好理解吧兴泥？葉子節(jié)點(diǎn)的左右子節(jié)點(diǎn)就會(huì)一直為空了，但是
代碼：
class TreeNode(object):
def __init__(self,value):
self.value = value
self.left = None
self.right = None
2. 建立搜索樹(shù)
現(xiàn)在我們有了點(diǎn)虾宇，看起來(lái)很簡(jiǎn)單，但是該怎么把樹(shù)建起來(lái)呢嘱朽？
二叉樹(shù)建樹(shù)其實(shí)就像上面說(shuō)的燥翅，是一個(gè)很簡(jiǎn)單明確的過(guò)程森书，首先需要一個(gè)根節(jié)點(diǎn)凛膏，然后每一次新的節(jié)點(diǎn)過(guò)來(lái)猖毫，就跟根節(jié)點(diǎn)比較吁断，比它小就作為左子節(jié)點(diǎn)仔役，比它大就作為右子節(jié)點(diǎn)，然后依次跟下一層比較任柜，直到自己成為葉子節(jié)點(diǎn)停止宙地。
算法的要點(diǎn)是利用遞歸算法 recursion宅粥，說(shuō)實(shí)話靠我自己想可能還是太難太抽象了點(diǎn)粹胯。但是如果你要去領(lǐng)會(huì)它的意思风纠，做得也就是這件事：
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
我們定義了一個(gè)新的類 二叉樹(shù)竹观，這個(gè)類里面只有一個(gè)insert方法臭增，就是插入一個(gè)新的節(jié)點(diǎn)到已生成的樹(shù)中誊抛。這個(gè)方法的記憶點(diǎn)有兩塊：
1.輸入?yún)?shù)：
此處的參數(shù)應(yīng)該是已生成的樹(shù)節(jié)點(diǎn)拗窃，和準(zhǔn)備加入的新節(jié)點(diǎn)随夸，這兩者的類型都需要是剛剛定義的帶有左右子節(jié)點(diǎn)屬性的類宾毒；
2.遞歸诈铛，采用三個(gè)條件判斷：
如果當(dāng)前節(jié)點(diǎn)為空就返回新的節(jié)點(diǎn)幢竹；如果當(dāng)前節(jié)點(diǎn)不為空且比新的節(jié)點(diǎn)值大，那么就遞歸地判斷當(dāng)前節(jié)點(diǎn)的左子節(jié)點(diǎn)和新節(jié)點(diǎn)的關(guān)系，直到當(dāng)前節(jié)點(diǎn)為空咬荷；比新的節(jié)點(diǎn)小就遞歸地判斷當(dāng)前節(jié)點(diǎn)的左子節(jié)點(diǎn)和新節(jié)點(diǎn)的關(guān)系幸乒，直到當(dāng)前節(jié)點(diǎn)為空返回罕扎。
3. 生成二叉搜索樹(shù)：
那么下面我們就用一個(gè)循環(huán)語(yǔ)句來(lái)生成一棵二叉搜索樹(shù)吧腔召。
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)——
程序運(yùn)行完抡柿，啥也沒(méi)顯示洲劣，就完了闪檬。
那是因?yàn)槲覀儧](méi)有把樹(shù)“遍歷”地展示出來(lái)粗悯，python有一個(gè)二叉樹(shù)庫(kù) binarytree样傍，可以用pip安裝衫哥，允許你打印出樹(shù)的結(jié)構(gòu),可以用非常直觀的方式來(lái)構(gòu)建二叉樹(shù)，看看人家的示例：
>>> 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. 二叉樹(shù)的三種遍歷算法及排序
當(dāng)我們已經(jīng)有一個(gè)二叉樹(shù)的時(shí)候膛锭，有哪幾種方式來(lái)遍歷它呢初狰？
這是一個(gè)面試常見(jiàn)考點(diǎn)奢入，相信很多小伙伴腦子里已經(jīng)蹦出了答案：前序遍歷腥光，中序遍歷议双，后序遍歷
那么哪種遍歷方法可以使二叉樹(shù)輸出有序呢聋伦？
中序遍歷
在說(shuō)到二叉樹(shù)遍歷的前序觉增，中序和后序的時(shí)候逾礁，需要牢牢記住，這里的前砾嫉，中焕刮，后的順序配并，都是相對(duì)于節(jié)點(diǎn)本身而言的溉旋。所以“前序遍歷”實(shí)際上的意思是：把遍歷我這個(gè)父節(jié)點(diǎn)先放到前面嫉髓，然后再左子節(jié)點(diǎn)恕沫，然后再右子節(jié)點(diǎn)，一直要保證這個(gè)順序偷霉。中序遍歷就是把遍歷父節(jié)點(diǎn)放在中間去進(jìn)行叙身，先左子節(jié)點(diǎn)信轿，然后再右子節(jié)點(diǎn)财忽，子節(jié)點(diǎn)的遍歷需要注意的是這個(gè)過(guò)程也是遞歸的。后序遍歷呢隶校，就是先左子節(jié)點(diǎn)，然后右子節(jié)點(diǎn)舞终，最后再遍歷父節(jié)點(diǎn)。
所以，自然满俗，由于二叉樹(shù)本身生成的時(shí)候的特性，再遍歷的時(shí)候如果采用中序辕万，就能夠保證整個(gè)輸出是從小到大有序的了醉途。
所以我們定義三個(gè)新的函數(shù)來(lái)表示這三種遍歷方法：
# 前序遍歷
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é)果就是有序的了。
