python 二叉树(binary tree) 先序遍历 中序遍历 后序遍历

我们在之前数据结构-二叉树基础的篇幅中已经对二叉树(binary tree)的基本性质、特点做了入门介绍，不再做过多的介绍。本篇旨在通过最简单的python代码来模拟实现二叉树的先序遍历、中序遍历、后序遍历。

二叉树是有限个元素的集合，该集合或者为空、或者有一个称为根节点（root）的元素及两个互不相交的、分别被称为左子树和右子树的二叉树组成。

二叉树的基本介绍

1、特点知识回顾

• 二叉树的每个结点至多只有二棵子树(不存在度大于2的结点)，二叉树的子树有左右之分，次序不能颠倒。
• 二叉树的第i层至多有2^{i-1}个结点
• 深度为k的二叉树至多有2^k-1个结点；
• 对任何一棵二叉树T，如果其终端结点数为N0，度为2的结点数为N2，则N0=N2+1

2、上代码

# 定义基本二叉树结构
class Node:
    def __init__(self,value=None,left=None,right=None):
        self.value=value
        self.left=left    #左子树
        self.right=right  #右子树

def preTraverse(root):
    '''
    前序遍历
    '''
    if root==None:
        return
    print(root.value)
    preTraverse(root.left)
    preTraverse(root.right)

def midTraverse(root):
    '''
    中序遍历
    '''
    if root==None:
        return
    midTraverse(root.left)
    print(root.value)
    midTraverse(root.right)

def afterTraverse(root):
    '''
    后序遍历
    '''
    if root==None:
        return
    afterTraverse(root.left)
    afterTraverse(root.right)
    print(root.value)

3、验证

root=Node('D',Node('B',Node('A'),Node('C')),Node('E',right=Node('G',Node('F'))))
print('前序遍历：')
preTraverse(root)
print('\n')
print('中序遍历：')
midTraverse(root)
print('\n')
print('后序遍历：')
afterTraverse(root)
print('\n')

前序遍历：
D
B
A
C
E
G
F

中序遍历：
A
B
C
D
E
F
G

后序遍历：
A
C
B
F
G
E
D