python基于递归算法实现二叉树

二叉树是一种基础又十分重要树结构。本文首先介绍二叉树的基本原理，然后基于递归算法，利用python编程，实现二叉树的先序遍历、中序遍历、后序遍历这三种遍历方式。

本文主要内容：

1、二叉树的构造

2、递归算法

3、二叉树遍历方式

4、递归实现先序遍历、中序遍历、后序遍历

1、二叉树的构造：

二叉树的每个结点最多有两棵子树（子树的左右顺序不能颠倒），即节点的度不大于2，且二叉树的第i层的结点个数最多为2^(i-1)。

深度为n的二叉树最多有(2^n-1)个结点，且我们把深度为n，节点个数为(2^n-1)的二叉树为“满二叉树”，它的每个结点的度都为2。

如果除了最后一层之外的层都是满的，或者在右边缺少一些连续的结点（第n层的叶子节点是从左到右依次排布），这样的二叉树我们管它叫做完全二叉树。深度为n的完全二叉树，至少有2^(n-1)个结点(最后一层至少有一个结点)，至多有(2^n-1)个结点。

如果一颗二叉树是一颗空树，或者这颗二叉树左右两颗子树的高度差的绝对值不大于1且两颗子树又都具有与其相同的性质，我们把这样的二叉树叫做平衡二叉树。

图1 满二叉树

图2 完全二叉树

2、递归算法：

递归：递归在程序中指的是函数对自身的调用，它的主要思想是把一个大型的问题逐层分解为与原问题相似的较小的问题来求解，即把大问题转变为性质相同的小问题的重复计算。递归的核心思想是“递”和“归”，通俗地可以理解为有“递去”有“回归”（有去有回），一直往下“递去”，知道满足一个临界条件，然后逐步“归来”。

3、二叉树遍历方式：先序遍历、中序遍历、后续遍历、层次遍历

遍历二叉树指的是按照符合一定规则的顺序把二叉树的有所结点都访问一次。对一颗二叉树进行遍历的方式有三种：DLR先根次序遍历、LDR中根次序遍历、LRD后根次序遍历、层次遍历。

先序遍历：即为DLR先根次序遍历。遍历规则为“根左右“，即先遍历根，再遍历左孩子，再遍历右孩子，我们对图2先序遍历的顺序为：1、2、4、8、9、5、10、11、3、6、12、7。

中序遍历：即为LDR中根次序遍历。遍历规则“左根右“，即先遍历左孩子，再遍历根，再遍历右孩子。我们对图2的中序遍历顺序为：8、4、9、2、10、5、11、1、12、6、3、7。

后序遍历：即为LRD后根次序遍历。遍历规则为“左右根“，即先遍历左孩子，再遍历右孩子，再遍历根。我们对图2的后序遍历顺序为：8、9、4、10、11、5、2、12、6、7、3、1。

层次遍历：即按层次遍历。是最容易直观理解的遍历方式。我们对图2进行层次遍历的顺序为：1、2、3、4、5、6、7、8、9、10、11、12。

4、递归实现先序遍历、中序遍历、后序遍历：

输出结果：