資料結構和算法-18-二叉樹的先序/中序/後序周遊和具體實作

前面一篇我們介紹了二叉樹的廣度優先添加和周遊元素，在二叉樹的周遊技術中，除了廣度優先周遊，還有一種叫深度優先周遊。本篇就來讨論深度周遊的三種重要的方法，它們分别是先序周遊和中序周遊和後序周遊。

1.三種深度周遊的概念

深度周遊有重要的三種方法，這三種方式常被用于通路樹的節點。它們之間不同在于通路每個節點的次序不同。這三種周遊分别叫做先序周遊(preorder)，中序周遊(inorder)和後序周遊（postorder）.

先序周遊

在先序周遊中，我們先通路根節點，然後遞歸使用先序周遊通路左子樹，再遞歸使用先序周遊通路右子樹。

根節點->左子樹->右子樹

中序周遊

遞歸使用中序周遊先通路左子樹，然後通路根節點，最壞遞歸使用中序通路右子樹。

左子樹->根節點->右子樹

後序周遊

遞歸使用後序周遊先通路左子樹，然後遞歸使用後序周遊通路右子樹，最後通路根節點。

左子樹->右子樹->根節點

2.具體一顆二叉樹的三種深度周遊分析

下面給出一個具體二叉樹，然後我們利用上面的概念，來寫出周遊輸出元素的順序。

資料結構和算法-18-二叉樹的先序/中序/後序周遊和具體實作

這個按照前面的廣度優先周遊輸出元素的順序是：0 1 2 3 4 5 6 7 8 9

先序周遊

先序周遊順序是先根節點，然後左子樹，然後右子樹。我們這裡拿先序周遊重點介紹這個思路分析過程。

第一步，周遊根節點，輸出 0

第二步，發現左節點1下形成一個左子樹，右邊節點2也是一顆樹。左子樹優先右子樹周遊，是以第二個輸出 1

第三步，周遊發現3 4節點，左子樹優先元素，輸出 3

第四步，周遊7 8 節點，輸出7

第五步，在 378這個子樹，剩下8這個右節點，是以輸出 8

第六步，因為3節點已經周遊過，這裡周遊輸出 4

第七步，4節點的隻有9這個節點，輸出 9

第八步，到這裡 1節點下左子樹全部周遊完成，這裡開始周遊2子樹，這裡輸出 2

第九步，5 6節點，左邊優先，輸出 5

第十步，輸出 6

是以先序周遊輸出元素順序為：0 1 3 7 8 4 9 2 5 6

中序周遊

根據遇到一棵樹，先左子樹->根節點-右子樹規則

周遊元素順序為：7 3 8 1 9 4 0 5 2 6

後序周遊

根據遇到一棵樹，先左子樹->右子樹->根節點規則

周遊元素順序為：7 8 3 9 4 1 5 6 2 0

3.代碼實作三種深度周遊

下面接着上一篇python代碼，來寫先序中序後序三種周遊的代碼。

先序周遊實作

# coding:utf-8


class Node(object):
    """節點"""
    def __init__(self, itme):
        self.ele = itme
        self.lchild = None
        self.rchild = None


class BinaryTree(object):
    """二叉樹"""
    def __init__(self):
        self.root = None

    def add(self, item):
        node = Node(item)
        if self.root is None:
            self.root = node
            return
        # 一個隊列，添加根元素
        queue = [self.root]
        while queue:
            cur_node = queue.pop(0)
            if cur_node.lchild is None:
                cur_node.lchild = node
                return
            else:
                queue.append(cur_node.lchild)
            if cur_node.rchild is None:
                cur_node.rchild = node
                return
            else:
                queue.append(cur_node.rchild)

    def breadth_travle(self):
        """廣度周遊"""
        if self.root is None:
            return
        queue = [self.root]
        while queue:
            cur_node = queue.pop(0)
            print(cur_node.ele, end=" ")
            if cur_node.lchild is not None:
                queue.append(cur_node.lchild)
            if cur_node.rchild is not None:
                queue.append(cur_node.rchild)

    def preorder(self, node):
        """先序周遊,node 是根節點"""
        if node is None:
            return
        print(node.ele, end=" ")
        self.preorder(node.lchild)
        self.preorder(node.rchild)


if __name__ == "__main__":
    tree = BinaryTree()
    tree.add(0)
    tree.add(1)
    tree.add(2)
    tree.add(3)
    tree.add(4)
    tree.add(5)
    tree.add(6)
    tree.add(7)
    tree.add(8)
    tree.add(9)
    tree.breadth_travle()
    print(" ")
    tree.preorder(tree.root)

運作結果

0 1 2 3 4 5 6 7 8 9  
0 1 3 7 8 4 9 2 5 6

第一個是廣度周遊順序，第二行是先序周遊結果。

中序周遊代碼

上面知道了先序周遊，那麼中序周遊就簡單了，調整以下這行列印順序就行。

# coding:utf-8


class Node(object):
    """節點"""
    def __init__(self, itme):
        self.ele = itme
        self.lchild = None
        self.rchild = None


class BinaryTree(object):
    """二叉樹"""
    def __init__(self):
        self.root = None

    def add(self, item):
        node = Node(item)
        if self.root is None:
            self.root = node
            return
        # 一個隊列，添加根元素
        queue = [self.root]
        while queue:
            cur_node = queue.pop(0)
            if cur_node.lchild is None:
                cur_node.lchild = node
                return
            else:
                queue.append(cur_node.lchild)
            if cur_node.rchild is None:
                cur_node.rchild = node
                return
            else:
                queue.append(cur_node.rchild)

    def breadth_travle(self):
        """廣度周遊"""
        if self.root is None:
            return
        queue = [self.root]
        while queue:
            cur_node = queue.pop(0)
            print(cur_node.ele, end=" ")
            if cur_node.lchild is not None:
                queue.append(cur_node.lchild)
            if cur_node.rchild is not None:
                queue.append(cur_node.rchild)

    def preorder(self, node):
        """先序周遊,node 是根節點"""
        if node is None:
            return
        print(node.ele, end=" ")
        self.preorder(node.lchild)
        self.preorder(node.rchild)

    def inorder(self, node):
        """中序周遊"""
        if node is None:
            return
        self.inorder(node.lchild)
        print(node.ele, end=" ")
        self.inorder(node.rchild)


if __name__ == "__main__":
    tree = BinaryTree()
    tree.add(0)
    tree.add(1)
    tree.add(2)
    tree.add(3)
    tree.add(4)
    tree.add(5)
    tree.add(6)
    tree.add(7)
    tree.add(8)
    tree.add(9)
    tree.breadth_travle()
    print(" ")
    tree.preorder(tree.root)
    print(" ")
    tree.inorder(tree.root)

運作結果

0 1 2 3 4 5 6 7 8 9  
0 1 3 7 8 4 9 2 5 6  
7 3 8 1 9 4 0 5 2 6

第三行是中序結果，下面直接貼出後續代碼。

# coding:utf-8


class Node(object):
    """節點"""
    def __init__(self, itme):
        self.ele = itme
        self.lchild = None
        self.rchild = None


class BinaryTree(object):
    """二叉樹"""
    def __init__(self):
        self.root = None

    def add(self, item):
        node = Node(item)
        if self.root is None:
            self.root = node
            return
        # 一個隊列，添加根元素
        queue = [self.root]
        while queue:
            cur_node = queue.pop(0)
            if cur_node.lchild is None:
                cur_node.lchild = node
                return
            else:
                queue.append(cur_node.lchild)
            if cur_node.rchild is None:
                cur_node.rchild = node
                return
            else:
                queue.append(cur_node.rchild)

    def breadth_travle(self):
        """廣度周遊"""
        if self.root is None:
            return
        queue = [self.root]
        while queue:
            cur_node = queue.pop(0)
            print(cur_node.ele, end=" ")
            if cur_node.lchild is not None:
                queue.append(cur_node.lchild)
            if cur_node.rchild is not None:
                queue.append(cur_node.rchild)

    def preorder(self, node):
        """先序周遊,node 是根節點"""
        if node is None:
            return
        print(node.ele, end=" ")
        self.preorder(node.lchild)
        self.preorder(node.rchild)

    def inorder(self, node):
        """中序周遊"""
        if node is None:
            return
        self.inorder(node.lchild)
        print(node.ele, end=" ")
        self.inorder(node.rchild)

    def postorder(self, node):
        """中序周遊"""
        if node is None:
            return
        self.postorder(node.lchild)
        self.postorder(node.rchild)
        print(node.ele, end=" ")

if __name__ == "__main__":
    tree = BinaryTree()
    tree.add(0)
    tree.add(1)
    tree.add(2)
    tree.add(3)
    tree.add(4)
    tree.add(5)
    tree.add(6)
    tree.add(7)
    tree.add(8)
    tree.add(9)
    tree.breadth_travle()
    print(" ")
    tree.preorder(tree.root)
    print(" ")
    tree.inorder(tree.root)
    print(" ")
    tree.postorder(tree.root)

運作結果

0 1 2 3 4 5 6 7 8 9  
0 1 3 7 8 4 9 2 5 6  
7 3 8 1 9 4 0 5 2 6  
7 8 3 9 4 1 5 6 2 0

資料結構和算法-18-二叉樹的先序/中序/後序周遊和具體實作

繼續閱讀

二叉樹(C++)：建立，前中後序周遊（遞歸+非遞歸），擷取葉子節點個數，擷取樹的高度

資料結構與算法:二叉樹的中序周遊

劍指 Offer 54. 二叉搜尋樹的第k大節點java題解1.思路2.代碼3.複雜度4.結果

LeetCode 298. Binary Tree Longest Consecutive Sequence（二叉樹最長連續序列）

資料結構實驗4-樹與二叉樹先序/中序/後續周遊實驗要求程式代碼運作結果

二叉樹——根據中序和後續重建二叉樹，并以先序傳回

洛谷P1305 新二叉樹

7.7 線索二叉樹

leetcode筆試題二叉樹的前序、中序、後序周遊的遞歸和循環c++實作

【轉】LeetCode中二叉樹題目總結

資料結構 —— 二叉樹的4種周遊，java代碼實作

[LeetCode Solution 98]: Validate Binary Search Tree

中序周遊的三種方法

99.恢複二叉搜尋樹

[劍指Offer]二叉搜尋樹的後序周遊序列(Java)劍指Offer題目題目描述思路代碼

二叉樹（二）——周遊