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

二叉樹

顧名思義，二叉樹就是只有兩個節(jié)點的樹，兩個節(jié)點分別為左節(jié)點和右節(jié)點，特別強調(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)方法嗎，留言告訴我們把。