上篇文章我們介紹了樹的概念拍棕，今天我們來介紹一種特殊的樹——二叉樹，二叉樹的應(yīng)用很廣勺良，有很多特性绰播。今天我們一一來為大家介紹。
二叉樹
顧名思義尚困，二叉樹就是只有兩個節(jié)點的樹蠢箩，兩個節(jié)點分別為左節(jié)點和右節(jié)點，特別強(qiáng)調(diào)事甜，即使只有一個子節(jié)點也要區(qū)分它是左節(jié)點還是右節(jié)點谬泌。
常見的二叉樹有一般二叉樹、完全二叉樹逻谦、滿二叉樹掌实、線索二叉樹、霍夫曼樹邦马、二叉排序樹贱鼻、平衡二叉樹、紅黑樹滋将、B樹這么多種類邻悬。我們這篇文章中簡單介紹一般二叉樹、完全二叉樹和滿二叉樹随闽。
一般二叉樹
很簡單拘悦，只要滿足子節(jié)點數(shù)不超過兩個的樹就是一棵二叉樹。長這樣：
滿二叉樹
滿二叉樹在一般二叉樹的基礎(chǔ)上要求除了最后一層的節(jié)點之外橱脸，每一個節(jié)點都必須有兩個子節(jié)點础米。
完全二叉樹
完全二叉樹要求從第一層到倒數(shù)第二層組成的樹是一顆滿二叉樹，最后一層的節(jié)點要滿足從左往右排列添诉。
好屁桑，關(guān)于二叉樹的概念，我們就介紹到這里栏赴，下面我們來介紹二叉樹的前序蘑斧、中序、后序遍歷。
在此之前呢竖瘾，我們先創(chuàng)建一顆二叉樹：
class BinaryTree:
def __init__(self, data):
self.data = data
self.left = None
self.right = None
def get(self):
return self.data
def getLeft(self):
return self.left
def getRight(self):
return self.right
def setLeft(self, node):
self.left = node
def setRight(self, node):
self.right = node
好沟突，這里我們定義好了一個二叉樹類，并給它添加了一下方法捕传，然后我們來實例化一顆二叉樹：
binaryTree = BinaryTree(0)
binaryTree.setLeft(BinaryTree(1))
binaryTree.setRight(BinaryTree(2))
binaryTree.getLeft().setLeft(BinaryTree(3))
binaryTree.getLeft().setRight(BinaryTree(4))
binaryTree.getRight().setLeft(BinaryTree(5))
binaryTree.getRight().setRight(BinaryTree(6))
實例化好的二叉樹是長這個樣子的：
前序遍歷
接下來惠拭，我們對這棵樹進(jìn)行前序遍歷。在此之前庸论，我們介紹一下什么是前序遍歷职辅。
前面我們介紹過了樹的深度優(yōu)先遍歷和廣度優(yōu)先遍歷，這里就不再贅述了聂示。
前序遍歷的順序就是先遍歷樹的父節(jié)點域携，然后遍歷樹的左節(jié)點，然后遍歷樹的右節(jié)點鱼喉，以此類推秀鞭。
對于我們上面定義好的二叉樹來說，它的前序遍歷結(jié)果就是：0 -> 1 -> 3 -> 4 -> 2 -> 5 -> 6
對于前序扛禽、中序锋边、后序遍歷來說，采用遞歸的方式是非常方便的旋圆。這里我們就用遞歸來實現(xiàn)一下：
def preorderTraversal(now, result=[]):
if now == None:
return result
result.append(now.data)
preorderTraversal(now.left, result)
preorderTraversal(now.right, result)
return result
print(preorderTraversal(binaryTree))
執(zhí)行結(jié)果：[0, 1, 3, 4, 2, 5, 6]，是不是和我們之前手動遍歷的結(jié)果一樣呢麸恍。
中序遍歷
中序遍歷的順序是：先遍歷樹的左節(jié)點灵巧，再遍歷樹的父節(jié)點，再遍歷樹的右節(jié)點抹沪。
對于我們上面創(chuàng)建的二叉樹刻肄，它的中序遍歷結(jié)果就是：3 -> 1 -> 4 -> 0 -> 5 -> 2 -> 6
在前序遍歷的時候是先遍歷父節(jié)點，所以result.append(now.data)融欧，就在遍歷左節(jié)點和右節(jié)點的前面敏弃。
而中序遍歷要先遍歷左節(jié)點，所以result.append(now.data)就要在遍歷左節(jié)點的后面噪馏，遍歷右節(jié)點的前面麦到。
def intermediateTraversal(now, result=[]):
if now == None:
return result
intermediateTraversal(now.left, result)
result.append(now.data)
intermediateTraversal(now.right, result)
return result
print(intermediateTraversal(binaryTree))
執(zhí)行結(jié)果：[3, 1, 4, 0, 5, 2, 6]
后序遍歷
后序遍歷順序是：先遍歷樹的左節(jié)點，再遍歷樹的右節(jié)點欠肾，再遍歷樹的父節(jié)點瓶颠。
對于我們上面創(chuàng)建的二叉樹，它的后序遍歷結(jié)果是：3 -> 4 -> 1 -> 5 -> 6 -> 2 -> 0
相應(yīng)的遞歸方程為：
def postorderTraversal(now, result=[]):
if now == None:
return
postorderTraversal(now.left, result)
postorderTraversal(now.right, result)
result.append(now.data)
return result
print(postorderTraversal(binaryTree))
執(zhí)行結(jié)果：[3, 4, 1, 5, 6, 2, 0]
好刺桃，今天我們關(guān)于二叉樹的三序遍歷就介紹到這里了粹淋，接下來我們會接著介紹更多的二叉樹類型以及應(yīng)用，記得關(guān)注我的文章。關(guān)于三序遍歷桃移，你還有其他的實現(xiàn)方法嗎屋匕，留言告訴我們把。
