上篇文章我們介紹了樹的概念，今天我們來介紹一種特殊的樹——二叉樹，二叉樹的應用很廣，有很多特性。今天我們一一來為大家介紹。

二叉樹

顧名思義，二叉樹就是只有兩個節點的樹，兩個節點分別為左節點和右節點，特別強調，即使只有一個子節點也要區分它是左節點還是右節點。

常見的二叉樹有一般二叉樹、完全二叉樹、滿二叉樹、線索二叉樹、霍夫曼樹、二叉排序樹、平衡二叉樹、紅黑樹、B樹這么多種類。我們這篇文章中簡單介紹一般二叉樹、完全二叉樹和滿二叉樹。

一般二叉樹

很簡單，只要滿足子節點數不超過兩個的樹就是一棵二叉樹。長這樣：

滿二叉樹

滿二叉樹在一般二叉樹的基礎上要求除了最后一層的節點之外，每一個節點都必須有兩個子節點。

完全二叉樹

完全二叉樹要求從第一層到倒數第二層組成的樹是一顆滿二叉樹，最后一層的節點要滿足從左往右排列。

好，關于二叉樹的概念，我們就介紹到這里，下面我們來介紹二叉樹的前序、中序、后序遍歷。

在此之前呢，我們先創建一顆二叉樹：

          
            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))
          
        

實例化好的二叉樹是長這個樣子的：

前序遍歷

接下來，我們對這棵樹進行前序遍歷。在此之前，我們介紹一下什么是前序遍歷。

前面我們介紹過了樹的深度優先遍歷和廣度優先遍歷，這里就不再贅述了。

前序遍歷的順序就是先遍歷樹的父節點，然后遍歷樹的左節點，然后遍歷樹的右節點，以此類推。

對于我們上面定義好的二叉樹來說，它的前序遍歷結果就是：0 -> 1 -> 3 -> 4 -> 2 -> 5 -> 6

對于前序、中序、后序遍歷來說，采用遞歸的方式是非常方便的。這里我們就用遞歸來實現一下：

          
            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))
          
        

執行結果： [0, 1, 3, 4, 2, 5, 6] ，是不是和我們之前手動遍歷的結果一樣呢。

中序遍歷

中序遍歷的順序是：先遍歷樹的左節點，再遍歷樹的父節點，再遍歷樹的右節點。

對于我們上面創建的二叉樹，它的中序遍歷結果就是：3 -> 1 -> 4 -> 0 -> 5 -> 2 -> 6

在前序遍歷的時候是先遍歷父節點，所以 result.append(now.data) ，就在遍歷左節點和右節點的前面。

而中序遍歷要先遍歷左節點，所以 result.append(now.data) 就要在遍歷左節點的后面，遍歷右節點的前面。

          
            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))
          
        

執行結果： [3, 1, 4, 0, 5, 2, 6]

后序遍歷

后序遍歷順序是：先遍歷樹的左節點，再遍歷樹的右節點，再遍歷樹的父節點。

對于我們上面創建的二叉樹，它的后序遍歷結果是：3 -> 4 -> 1 -> 5 -> 6 -> 2 -> 0

相應的遞歸方程為：

          
            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))
          
        

執行結果： [3, 4, 1, 5, 6, 2, 0]

好，今天我們關于二叉樹的三序遍歷就介紹到這里了，接下來我們會接著介紹更多的二叉樹類型以及應用，記得關注我的文章。關于三序遍歷，你還有其他的實現方法嗎，留言告訴我們把。