二叉树（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