二叉树（binary tree）遍历详解

本文主要是介绍二叉树（binary tree）遍历详解，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

一、简介

二叉树常见的遍历方式包括前序遍历、中序遍历、后序遍历和层序遍历等。我将以下述二叉树来讲解这几种遍历算法。

1、创建二叉树代码实现

class TreeNode:def __init__(self,data):self.data=dataself.left=Noneself.right=Nonedef createTree():treeRoot=TreeNode('F')NodeB=TreeNode('B')NodeG=TreeNode('G')treeRoot.left=NodeBtreeRoot.right=NodeGNodeA=TreeNode('A')NodeD=TreeNode('D')NodeB.left=NodeANodeB.right=NodeDNodeC=TreeNode('C')NodeE=TreeNode('E')NodeD.left=TreeNode('C')NodeD.right=TreeNode('E')NodeI=TreeNode('I')NodeH=TreeNode('H')NodeG.right=NodeINodeI.left=NodeHreturn treeRoot

二、遍历算法详解

1、DLR 前序遍历（先序遍历）（根，左，右）

前序遍历首先访问根节点，然后遍历左子树，最后遍历右子树；在遍历左子树和右子树时，仍然先访问根节点，然后遍历左子树，最后遍历右子树。前序遍历算法一般采用递归的方式实现，代码实现如下：

def preOrder(treeRoot):print(treeRoot.data,end="  ")if treeRoot.left is not None:preOrder(treeRoot.left)if treeRoot.right is not None:preOrder(treeRoot.right)

2、LDR 中序遍历（左、根、右）

中序遍历首先遍历左子树，然后访问根节点，最后遍历右子树；在遍历左子树和右子树时，仍然首先遍历左子树，然后访问根节点，最后遍历右子树，中序遍历算法一般采用递归的方式实现，代码实现如下：

def inOrder(treeRoot):if treeRoot.left is not None:inOrder(treeRoot.left)print(treeRoot.data,end="  ")if treeRoot.right is not None:inOrder(treeRoot.right)

3、LRD 后序遍历（左，右，根）

首先遍历左子树，然后遍历右子树，最后访问根节点；在遍历左子树和右子树时，仍然首先遍历左子树，然后遍历右子树，最后访问根节点，同样后序遍历算法一般采用递归的方式实现，代码实现如下：

def postOrder(treeRoot):if treeRoot.left is not None:postOrder(treeRoot.left)if treeRoot.right is not None:postOrder(treeRoot.right)print(treeRoot.data,end="  ")

4、层序遍历

二叉树的层次遍历，是指从二叉树的第一层（根结点）开始，从上至下逐层遍历，在同一层中，则按从左到右的顺序对结点逐个访问。
二叉树的层次遍历需要使用队列（先进先出）实现。代码实现如下：

def levelOrder(treeRoot):q = []q.append(treeRoot)while(len(q)!=0):node=q.pop(0)print(node.data,end="  ")if node.left is not None:q.append(node.left)if node.right is not None:q.append(node.right)

5、执行结果如下：

if __name__ == '__main__':treeRoot=createTree()preOrder(treeRoot)print("\n############################")inOrder(treeRoot)print("\n############################")postOrder(treeRoot)print("\n############################")levelOrder(treeRoot)

PS C:\Users\love1\Documents\technology\算法与数据结构> python Tree.py
F  B  A  D  C  E  G  I  H
############################
A  B  C  D  E  F  G  H  I
############################
A  C  E  D  B  H  I  G  F
############################
F  B  G  A  D  I  C  E  H

三、复杂度分析

1、前序遍历、中序遍历、后序遍历

• 时间复杂度为 O(n)：所有节点都会被访问有且只有一次，故而 时间复杂度为 O(n)
• 空间复杂度为 O(n)：递归深度累加达到n，系统占用 O(n) 栈帧空间。

2、层序遍历

• 时间复杂度为 O(n)：所有节点都会被访问有且只有一次，故而 时间复杂度为 O(n)
• 空间复杂度为 O(n)：在最差情况下，即满二叉树时，遍历到最底层之前，队列中最多同时存在
  (n+1)/2个节点，最多占用 (n+1)/2个空间，故而空间复杂度为 O(n)。

这篇关于二叉树（binary tree）遍历详解的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---