论文部分内容阅读
摘要：二叉树是我们在学习数据结构过程中所遇到的一种常见的非线性存储形式，在我们的现实生活中的许许多多问题所抽象出来的用来描述问题的数据结构的形式都能够用二叉树来表示，它的运算和存储结构都相对来说较为简单，在解决现实生活中问题的过程中我们经常使用二叉树来解决问题，而我们使用二叉树解决问题的本质可以归结为二叉树的遍历。
关键词：二叉树 ；递归；遍历；非递归
1 树
树是n（）个结点的有限集[1]。在任意一棵非空树中：
（1）有且仅有一个特定的称为根的节点[1]；
（2）当n>1时，其余节点可分为m（m>0）个互不相交的的有限集T1，T2，Tm，其中每一个集合本身又是一棵树，并且称为根的子树[1]。
2 二叉树
2.1二叉树的逻辑描述
二叉树是一种特殊的树型结构，它的特点是每个结点至多只有两棵子树（即二叉树中不存在度大于2的结点），并且，二叉树的子树有左右之分，其次序不能任意颠倒[1]。
2.2二叉树的遍历
二叉树的遍历是指按某某条搜索路径寻访树中的每个节点使得每个结点被访问一次而且仅被访问一次[1]。二叉树遍历操作的结果就是非线性结构的线性化。我们以根节点为D，左子树为L，右子树为R二叉树的遍历方式有：DLR、LDR、LRD、DRL、RDL、RLD[1] 。
限定先左后右如果限定先左后右[1]，则二叉树遍历方式有三种：
（1）先序（根）遍历（DLR）：若二叉树为空，则空操作返回；否则：①访问根结点；②前序遍历根结点的左子树；③前序遍历根结点的右子树[1]。图1 中二叉树的先序遍历为：A B D G C E F。
（2）中序（根）遍历（LDR）：若二叉树为空，则空操作返回；否则：①中序遍历根结点的左子树；②访问根结点；③中序遍历根结点的右子树[1]。图1 中二叉树的中序遍历为：D G B A E C F。
（3）后序（根）遍历（LRD）：若二叉树为空，则空操作返回；否则：①后序遍历根结点的左子树；②后序遍历根结点的右子树。③访问根结点[1]。图1 中二叉树的后序遍历为：G D B E F C A。
2.2.1二叉树的递归遍历
我们遍历二叉树的所要解决的问题就是需要寻找到一条路径来访问树中的每一个结点，每个节点都要逐一并且仅仅访问一次[2]。我们已经知道了二叉树是一种非线性结构并且它由三个基本部分组成，即：根、左子树和右子树、只要依次遍历这三个部分，就可以遍历整个二叉树。遍历二叉树的方式通常有三种即：先序遍历（先访问根结点，再访问左子树，最后访问右子树）、中序遍历（先访问左子树，再访问根结点，最后访问右子树）、后序遍历（先访问左子树，再访问右子树，最后访问根结点）[1]。由于二叉树的定义具有递归性，用递归算法来遍历二又树也就顺理成章了。所谓递归就是指在定义自身的同时，又出现了对自身的引用，如果一个算法直接或间接调用自己，则称这个算法是一个递归算法[2]。我们在递归遍历二叉树的时候就是将二叉树的元素分为根结点、左结点和右结点，并且按照左根右、根左右或左右根的顺序依次来访问各个结点并对其做各种处理，如修改、删除。
二叉树的递归遍历，二叉树的节点数据类型定义如图2 中C语言代码所示：
递归先序遍历二叉树算法如下图3 中C语言代码所示：
递归中序遍历二叉树算法如图4 中C语言代码所示：
递归后序遍历二叉树算法如图5中C语言代码所示：
从前面的三种遍历算法可以知道：倘若我们将printf语句所在的那一行代码给删除，从递归的角度看，这三種算法是完全相同的，换种说法这先序、中序、后序遍历二叉树的算法的访问路径是相同的它们只是访问各个结点时机不同。
2.2.2二叉树的非递归遍历
为了将递归算法转化为非递归算法，我们可以通过分析递归算法执行过程中的递归工作栈的状态变化来写出相应的非递归算法[3]。我们以先序遍历为例，非递归先序遍历算法的关键是在前序遍历过某结点的一整个左子树之后，把这个结点的指针存储到栈中，以便之后能通过它找到这个结点的右子树。非递归先序遍历代码如图6：
中序遍历二叉树、后序遍历二叉树的非递归的思想与非递归先序遍历二叉树的思想一致，不再赘述。
3 总结
在我们的生活里许许多多的各类疑难杂症都能够用树和森林表示成模型，并且树和森林能够和二叉树进行等价的转换，学好二叉树对我们学习和解决现实生活中的实际问题有很大的帮助，所以我们掌握好二叉树的遍历算法是非常有用的。我们要充分地理解二叉树的递归与非递归的遍历把它用于学习和生活里。
参考文献：
[1]严蔚敏吴伟民.数据结构[M].第二版.北京：清华大学出版社1992年.
[2]李 彦.遍历二叉树的递归与非递归算法浅析[J]电脑知识与技术2011（8）.
[3]欧阳俊林.遍历二叉树的非递归实现[J]自贡师范高等专科学校学报2003.
[4]盛 魁.二叉树的遍历探究与应用[J]电脑知识与技术2008.
[5]王林.数据结构[M]北京：电子工业出版社.
[6]苏锦.二级公共基础知识教程[M]武汉：华中科技大学出版社，2008.
[7]张立平.二叉树前序遍历浅析[J]教学研究，2009.
[8]单光庆.二叉树的遍历研究及应用[J]科技信息.
通讯作者：贾巧兰
关键词：二叉树 ；递归；遍历；非递归
1 树
树是n（）个结点的有限集[1]。在任意一棵非空树中：
（1）有且仅有一个特定的称为根的节点[1]；
（2）当n>1时，其余节点可分为m（m>0）个互不相交的的有限集T1，T2，Tm，其中每一个集合本身又是一棵树，并且称为根的子树[1]。
2 二叉树
2.1二叉树的逻辑描述
二叉树是一种特殊的树型结构，它的特点是每个结点至多只有两棵子树（即二叉树中不存在度大于2的结点），并且，二叉树的子树有左右之分，其次序不能任意颠倒[1]。
2.2二叉树的遍历
二叉树的遍历是指按某某条搜索路径寻访树中的每个节点使得每个结点被访问一次而且仅被访问一次[1]。二叉树遍历操作的结果就是非线性结构的线性化。我们以根节点为D，左子树为L，右子树为R二叉树的遍历方式有：DLR、LDR、LRD、DRL、RDL、RLD[1] 。
限定先左后右如果限定先左后右[1]，则二叉树遍历方式有三种：
（1）先序（根）遍历（DLR）：若二叉树为空，则空操作返回；否则：①访问根结点；②前序遍历根结点的左子树；③前序遍历根结点的右子树[1]。图1 中二叉树的先序遍历为：A B D G C E F。
（2）中序（根）遍历（LDR）：若二叉树为空，则空操作返回；否则：①中序遍历根结点的左子树；②访问根结点；③中序遍历根结点的右子树[1]。图1 中二叉树的中序遍历为：D G B A E C F。
（3）后序（根）遍历（LRD）：若二叉树为空，则空操作返回；否则：①后序遍历根结点的左子树；②后序遍历根结点的右子树。③访问根结点[1]。图1 中二叉树的后序遍历为：G D B E F C A。
2.2.1二叉树的递归遍历
我们遍历二叉树的所要解决的问题就是需要寻找到一条路径来访问树中的每一个结点，每个节点都要逐一并且仅仅访问一次[2]。我们已经知道了二叉树是一种非线性结构并且它由三个基本部分组成，即：根、左子树和右子树、只要依次遍历这三个部分，就可以遍历整个二叉树。遍历二叉树的方式通常有三种即：先序遍历（先访问根结点，再访问左子树，最后访问右子树）、中序遍历（先访问左子树，再访问根结点，最后访问右子树）、后序遍历（先访问左子树，再访问右子树，最后访问根结点）[1]。由于二叉树的定义具有递归性，用递归算法来遍历二又树也就顺理成章了。所谓递归就是指在定义自身的同时，又出现了对自身的引用，如果一个算法直接或间接调用自己，则称这个算法是一个递归算法[2]。我们在递归遍历二叉树的时候就是将二叉树的元素分为根结点、左结点和右结点，并且按照左根右、根左右或左右根的顺序依次来访问各个结点并对其做各种处理，如修改、删除。
二叉树的递归遍历，二叉树的节点数据类型定义如图2 中C语言代码所示：
递归先序遍历二叉树算法如下图3 中C语言代码所示：
递归中序遍历二叉树算法如图4 中C语言代码所示：
递归后序遍历二叉树算法如图5中C语言代码所示：
从前面的三种遍历算法可以知道：倘若我们将printf语句所在的那一行代码给删除，从递归的角度看，这三種算法是完全相同的，换种说法这先序、中序、后序遍历二叉树的算法的访问路径是相同的它们只是访问各个结点时机不同。
2.2.2二叉树的非递归遍历
为了将递归算法转化为非递归算法，我们可以通过分析递归算法执行过程中的递归工作栈的状态变化来写出相应的非递归算法[3]。我们以先序遍历为例，非递归先序遍历算法的关键是在前序遍历过某结点的一整个左子树之后，把这个结点的指针存储到栈中，以便之后能通过它找到这个结点的右子树。非递归先序遍历代码如图6：
中序遍历二叉树、后序遍历二叉树的非递归的思想与非递归先序遍历二叉树的思想一致，不再赘述。
3 总结
在我们的生活里许许多多的各类疑难杂症都能够用树和森林表示成模型，并且树和森林能够和二叉树进行等价的转换，学好二叉树对我们学习和解决现实生活中的实际问题有很大的帮助，所以我们掌握好二叉树的遍历算法是非常有用的。我们要充分地理解二叉树的递归与非递归的遍历把它用于学习和生活里。
参考文献：
[1]严蔚敏吴伟民.数据结构[M].第二版.北京：清华大学出版社1992年.
[2]李 彦.遍历二叉树的递归与非递归算法浅析[J]电脑知识与技术2011（8）.
[3]欧阳俊林.遍历二叉树的非递归实现[J]自贡师范高等专科学校学报2003.
[4]盛 魁.二叉树的遍历探究与应用[J]电脑知识与技术2008.
[5]王林.数据结构[M]北京：电子工业出版社.
[6]苏锦.二级公共基础知识教程[M]武汉：华中科技大学出版社，2008.
[7]张立平.二叉树前序遍历浅析[J]教学研究，2009.
[8]单光庆.二叉树的遍历研究及应用[J]科技信息.
通讯作者：贾巧兰