递归思想在二叉树遍历中的应用

李萍

摘要：递归是程序设计中简化复杂问题的一种有力工具，可以将一个大的问题分解成同种类型小问题的迭代。该文介绍了递归的核心与特点，并以二叉树的遍历实现了递归的过程。

关键词：递归；二叉树遍历；迭代

中图分类号：TP18；TP301.6 文献标识码：A 文章编号：1009-3044（2018）27-0039-02

Application of Recursion on Traversing the Binary Tree

LI Ping

（Department of Mathematics and Information Technology， Yuncheng University， Yuncheng 044000， China）

Abstract：Recursion is a powerful tool for simplifying comples problems in program design. It can decompose a large problem into some problems of the same type.The article introduces the core and feature of recursion and implements the recursive process by traversing the binary tree.

Key words： Recursion； the traversion of binary tree； iterate

1 递归算法的描述

在一个函数的定义中直接或间接调用自身就称为函数的递归，该算法的本质体现了“以此类推”“用同样的步骤重复”这样的思想，可以用简单的程序来解决某些复杂的计算问题，但是运算量较大。以下为n的阶乘经典的递归算法描述递归程序的核心。

2 二叉树遍历算法

一棵非空二叉树是由树根和分别称为左右子树的二叉树构成，由二叉树的定义可知存在递归的思想。所以在编写与二叉树相关的算法时，要谨记递归。例：求二叉树结点的个数。

Int num（BTtree T）

{int leftnum，rightnum；

if（T==NULL） return 0；//递减到空树，不能再减二叉树的结点个数为0个

Else

Leftnum=num（T→lchild）；//递减，以同样的方式求左子树结点个数

Rightnum=num（T→rchild）；//递减，以同样的方式求右子树结点个数

Return leftnum+rightnum+1；}返回左右子树结点个数+根结点的1

递归求二叉树结点个数的递归函数调用过程如图1所示：

3 二叉树先序遍历非递归算法

非递归遍历的基本思想如下：

（1） 根结点进栈

（2） 结点出栈，被访问

（3） 结点的右，左孩子（非空）进栈

（4） 反复执行2，3步，至栈为空

算法描述如下：

void NLR（BiTree T）

{initstac（s）；// 初始化一个栈

BiTNode *p； p=T；

if（T==NULL） print（“it is NULL”）；

else {

push（s，p）；

while（！Stackempty（s））

{p=&pop;（s）；

printf（“%d”，p→data）；

if（p→rchild！=NULL） push（s，p→rchild）；

if（p→lchild！=NULL） push（s，p→lchild）；}}

}

4 总结

递归求解問题的方式简化了程序设计，结构清晰，易于理解。但是每执行一次递归函数需要额外增加存储空间。在不考虑空间的前提下应用于二叉树遍历，掌握递归的核心，提高程序的可读性。

参考文献：

[1] 黄艳峰，陈伟.递归问题的Java实现[J].电脑知识与技术，2017（7）：27-28.

[2] 张建波.一种将递归过程转换为非递归过程的方法研究[J].计算机教育，2017（8）：20-21.

[3] 朱朝霞.递归对自顶向下语法分析的影响[J].电脑知识与技术，2018（2）：146-147.

[4] 周法国.基于递归的程序设计浅析[J].天津科技，2017（6）：20-21.

[5] 王军.基于一道二叉树习题的教学案例辨析[J].福建电脑，2017（5）：8-10.

[6] 卓明敏，卓文.非递归后序遍历二叉树二址栈法[J].福建电脑，2017（10）：3-5.

[通联编辑：代影]