浅析树型数据结构中递归算法的实现
开篇：润墨网以专业的文秘视角，为您筛选了一篇浅析树型数据结构中递归算法的实现范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！
摘 要：针对递归算法在处理树型数据结构的相关问题时具有较好出的较好能力，本文主要研究了C/C++语言在树型数据结构中递归算法的设计与实现，并对比了递归算法和非递归算法，得出递归算法能够大幅度节省系统空间。
关键词：树型结构；递归算法；二叉树；遍历
中图分类号：TP311.12
在数据结构中树形数据结构是一类非常普遍的非线性结构，该结构具有显著的动态优势，目前广泛适用于大多数计算机软件中。而软件在处理树型结构时经常调用递归算法来解决常见问题，数学上递归算法就是函数或某些概念通过自身进行定义的一种形式；在计算机程序编写中，我们将函数运算过程中间接和直接调用自身的情况称为递归调用。
递归算法分为直接调用和间接调用。其中自身定义或调用自身的函数我们称为直接调用，与其他函数互相调用的形式称为间接调用。目前，直接调用算法是处理树型数据结构问题的常用算法，采用直接递归调用算法具有程序清晰易懂，直观明了，便于阅读和维护等诸多优点。
1 树型数据结构中的递归算法设计
1.1 树型数据结构的定义是递归的
一个树型数据结构的不同分支中有可能含有一个或者多个和自身相同的成分。因此，从树型数据结构的分支结构上来看，其定义本身就是一种递归形式。例如我们熟知的二叉树节点定义，就是典型的递归数据结构的例子。二叉树的一个根节点上分别有左右两个子树，左右子树又同时均是一棵二叉树。二叉树中的元素分为两部分，第一部分是构成与后继元素相连的链，第二部分是二叉树信息元素自身，指针指向的类型就是节点自身。
二叉树中定义节点的例程如下：
struct BTreeNode{
Elemtype data；
BTreeNode * left，*right； }；
通常，采用递归形式定义的数据结构，如果处理问题的算法也是用递归调用，那么总是会获得清晰简单的解。
1.2 问题的解法是递归的
因为树型数据结构非线性的特点，导致了解决树型数据结构的常见算法也是非线性的递归调用。其中，深度优先遍历算法就是采用递归调用解决树型数据结构的典型例子。
以下程序是二叉树的深度优先遍历算法：
void PreOrder（BTreeNode* BT） {
if（BT！ =NULL）{
cout
PreOrder（BT->left）；
PreOrder（BT->right）； /依次对根节点及左右子树进行遍历
}
}
由上述程序可以看出，二叉树的深度优先遍历是一个先对根节点进行访问，然后由从左向右的次序依次遍历每一个子树，整个过程是一个递归的遍历过程。
2 树型数据结构中递归算法的实现过程
采用递归算法解决树型数据结构时，计算机软件主要进行两步有效操。第一，由计算目标为出发点，追溯到递归出口。第二，采取逐步回代的形式，直到实现目标。对于递归算法，我们通常不会引入循环结构进行算法的实现，而是采用栈结构来解决问题。栈结构实现递归算法的具体过程是在第一步的追溯递归出口中将每个操作数进行入栈操作，第二步回代过程中再按照顺序进行出栈弹出操作。
由于在一个递归调用的过程中，调用和被调用的是一个函数自身。所以，区别每次调用时函数运行顺序的重要标志就是“层次”结构。例如：我们将提请调用递归函数的主函数定义为第一层，那么从首次递归调用开始就进入了第二层，以此类推，第N层递归调用则会进入到第N+1层。同理，在回代的过程中则进行递归返回，第N层返回到第N-1层。
递归过程中，我们设立一个工作栈作为整个调用过程中的内存区域。调用过程中每一个层中的信息自动生成一个调用记录用来标识返回上一层的地址、局部变量以及所有实参。调用每次进入到下一层，产生的工作记录就会压入我们之前设立的存储工作栈。每回代一层，就会从工作栈中弹出一条工作记录。由于用户不必亲自管理工作栈，而系统可以自动处理，大大方便了程序的编制过程。
3 树型数据结构中递归算法和非递归算法的转换
本节通过介绍二叉搜索树的查找问题，来对比分析树型数据结构中递归算法和非递归算法的转换问题。能够了解递归及非递归转换机理，对于实现树型数据结构中递归算法的调用是非常必要的。以下是递归算法和非递归算法例程序：
例如：采用递归算法的二叉搜索树的查找
bool Find（BreeNode* BST，ElemType& item）{ //BST 为指向根结点的指针
if（BST==NULL）return false； //查找失败，返回 false。
else{
if（item==BST->data）{
item=BST->data；
return true；
//查找成功，返回 true。
}
else if（itemdata）
return Find（BST->left，item）；
else return Find（BST->right，item）；
}
}
采用非递归算法的二叉搜索树的查找
bool Find1（BTreeNode* BST， ElemType& item）{
while（BST！ =NULL）{
if（item==BST->data）{
item=BST->data； return true；
}
else if（itemdata）BST=BST->left；
else BST=BST->right；
}
return false；
}
通过对比我们可以发现，同样解决二叉搜索树的查找问题，采用递归算法可以大大节省内存空间。
4 结论
综上所述，我们可以清晰的发现，将递归算法应用于二叉树中能够简化树型结构的程序设计，使程序清晰易懂，简单明了。同时，递归算法还能大幅降低程序对存储空间的消耗，使得程序员不用担心内存问题而专注于对问题的处理上。因此，树型数据结构中递归算法的实现对于解决许多具有相当难度的树型结构实际问题具有很大帮助。
参考文献：
[1]孙召伟，赵建利，朱东生.数据结构中递归转非递归算法分析及模型设计研究[J].河北科技大学学报，2011，01：43-46.
[2]马海瑛.数据结构中递归算法的描述与实现[J].大众科技，2007，03：177-178+153.
[3]郭韶，张炜.数据结构中递归算法的研究与实现[J].机械管理开发，2007，06：90-91.
作者简介：陈俊伟（1976.01.05-），男，重庆铜梁县人，教师，讲师，重庆大学计算机应用技术专业工学硕士，研究方向：软件技术、计算机网络技术。
作者单位：重庆电子工程职业学院软件学院，重庆 401331