二叉树操作的递归算法分析

詹泽梅

摘要：二叉树是数据结构课程中的重点内容。由于二叉树本身具有递归的特点，因此二叉树的许多操作可采用递归方法求解。该文首先介绍了递归方法，然后采用递归方法分析二叉树的几个常见操作，并给出详细算法。

关键词：递归；二叉树；遍历；算法

中图分类号： TP311 文献标识码：A 文章编号：1009-3044（2016）23-0097-02

Abstract： Binary tree is the key content of the data structure course. Because the binary tree itself has the characteristic of recursion， so many operations of the binary tree can be solved by recursive methods. This paper first introduces the recursive method， and then uses the recursive method to analyze several common operations of the binary tree ， and gives the detailed algorithms.

Key words：recursion； binary tree； traversal； algorithm

1概述

二叉树是数据结构课程内容中的重点和难点，学好数据结构就必须要掌握二叉树的存储结构和基本操作的算法。二叉树最常用的存储结构是二叉链表，根据二叉链表的示意图，我们很容易理解二叉树的这种存储形式。因此，掌握二叉树的关键就是要理解二叉树基本操作的算法。本文将分析二叉树操作的递归求解方法，以求和数据结构爱好者共同学习和研究。

2 递归

递归是一种非常有用的算法设计工具。一个函数、过程如果在其定义或说明内部直接地或间接地出现有其本身的引用，这种用自己定义自己的方法称之为递归 [1]。

递归方法实际上是将一个原问题转化为和原问题相同的子问题，只不过子问题的规模比原问题的规模要小。这种转换多次进行，直到满足某个约束条件为止。用递归方法求解问题关键就是要确定两方面内容：（1）子问题（2）递归结束条件。

例如： 求n！

3 二叉树操作的递归求解方法

二叉树的特点是每个结点至多只有两棵子树（左子树和右子树），且左右子树也是二叉树。因此，二叉树或者为空，或者可分为三部分：根结点、左子树、右子树。由于二叉树中的左子树和右子树也是二叉树，因此，二叉树的组成具有递归的特点，那么，二叉树的许多操作可考虑用递归方法来描述。下面将讨论几个常见二叉树操作的递归算法。

3.1遍历二叉树

遍历二叉树是指按某条搜索路径巡访二叉树中的每个结点，使得每个结点均被访问一次，而且仅被访问一次[2]。常见的二叉树遍历方法有三种：先序遍历、中序遍历、后序遍历，下面以先序遍历为例，分析其递归算法。

先序遍历二叉树的思想是：若二叉树为空，则没有任何结点可访问，因此空操作；当二叉树不为空时，先序遍历二叉树就是要：访问根结点、先序遍历左子树、先序遍历右子树。采用递归方法分析：1）原问题为先序遍历二叉树。2）原问题可分为三步：访问根结点、先序遍历左子树和先序遍历右子树。访问根结点直接对应访问语句，例如输出语句。先序遍历左子树和先序遍历右子树这两个问题都属于先序遍历二叉树的问题，与原问题一样，只不过左子树和右子树比原二叉树规模要小。因此，子问题为先序遍历左子树和先序遍历右子树。3）递归结束条件就是二叉树为空。

3.2 建立二叉树的二叉链表

建立二叉树的二叉链表存储结构是二叉树的必备操作，因为在程序中，只有创建了二叉树的二叉链表存储结构，才可以进行二叉树的其他操作。显然，二叉树中的每个结点对应二叉链表中的一个结点，因此，创建二叉链表，就是要为二叉树中的每个结点建立一个结点存储结构。可以按照某种遍历顺序依次为各个结点建立存储结构。若按照中序遍历顺序或后序遍历顺序建立，则在建立二叉链表过程中，已建立的结点是分散的、不能连接成一个链表，这就不易掌控所有已建立的结点。如果按先序遍历顺序建立，则已建立的结点都可链接在根指针所指的二叉链表中。因此，可按先序遍历的顺序为各个结点建立存储结构。

建立二叉树的二叉链表的算法思想是：若二叉树为空树，则根指针应设置为空；若二叉树非空，则为根结点建立存储结构，再建立左子树的二叉链表和右子树的二叉链表。采用递归方法分析：1）原问题为建立二叉树的二叉链表。2）子问题为建立左子树的二叉链表和建立右子树的二叉链表。3）递归结束条件是二叉树为空树。

3.3 求二叉树的深度

二叉树深度可按如下规则求取：当二叉树为空树，则深度为0；当二叉树只有一个结点，则深度为1；否则，二叉树的深度为左子树深度和右子树深度中的较大值，再加上1。采用递归方法分析：1）原问题为求二叉树的深度。2）子问题为：求左子树深度和求右子树深度。3）递归结束条件是二叉树为空或者二叉树只含有一个结点。

3.4 返回结点e的左兄弟

采用递归方法分析：1）原问题为在一棵二叉树中找结点e的左兄弟。2）子问题可设定为在左子树中找结点e的左兄弟，和在右子树中找结点e的左兄弟。3）递归结束条件可有两种情况：a）若二叉树为空树，则结点e的左兄弟不存在；b）若根结点的右孩子为结点e，则结点e的左兄弟为根结点的左孩子。

4 总结

二叉树是数据结构课程中的重要内容，掌握二叉树关键是掌握二叉树各种操作的算法。本文采用递归方法分析了二叉树的先序遍历、创建二叉链表、求深度、求结点e的左兄弟这四个操作的求解方法。对于二叉树的许多其他操作，也可以与此类似，采用递归方法求解。

参考文献：

[1] 李伟.浅析C语言递归算法[J].电脑知识与技术，2012（10）.

[2] 严蔚敏，吴伟民.数据结构（C语言版）[M].北京：清华大学出版社，2008.