数据结构和算法-18-二叉树的先序/中序/后序遍历和具体实现

港控/mmm° 2021-12-18 14:31 142阅读 0赞

前面一篇我们介绍了二叉树的广度优先添加和遍历元素，在二叉树的遍历技术中，除了广度优先遍历，还有一种叫深度优先遍历。本篇就来讨论深度遍历的三种重要的方法，它们分别是先序遍历和中序遍历和后序遍历。

**1.三种深度遍历的概念**

深度遍历有重要的三种方法，这三种方式常被用于访问树的节点。它们之间不同在于访问每个节点的次序不同。这三种遍历分别叫做先序遍历(preorder)，中序遍历(inorder)和后序遍历（postorder）.

**先序遍历**  
在先序遍历中，我们先访问根节点，然后递归使用先序遍历访问左子树，再递归使用先序遍历访问右子树。  
**根节点->左子树->右子树**

**中序遍历**  
递归使用中序遍历先访问左子树，然后访问根节点，最坏递归使用中序访问右子树。  
**左子树->根节点->右子树**

**后序遍历**  
递归使用后序遍历先访问左子树，然后递归使用后序遍历访问右子树，最后访问根节点。  
**左子树->右子树->根节点**

2.具体一颗二叉树的三种深度遍历分析

下面给出一个具体二叉树，然后我们利用上面的概念，来写出遍历输出元素的顺序。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTE1NDE5NDY_size_16_color_FFFFFF_t_70][]

这个按照前面的广度优先遍历输出元素的顺序是：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

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTE1NDE5NDY_size_16_color_FFFFFF_t_70]: /images/20211218/f010f5c1e8784efbadfb12491858bce3.png