遍历二叉树的一种改进算法 |
| |
引用本文: | 龙玉国,冯玉才.遍历二叉树的一种改进算法[J].计算机工程与应用,1989(9):9-12. |
| |
作者姓名: | 龙玉国 冯玉才 |
| |
作者单位: | 华中理工大学,华中理工大学 |
| |
摘 要: | 在计算机科学与工程中,二叉树是一类十分重要的数据结构,有着广泛的应用。本文介绍二叉树的主要操作:遍历二叉树,和遍历算法;对于后序遍历,提出一种新的改进的非递归算法。传统的后序遍历非递归算法,需要为二叉树的结点建立标志位,用以判断该结点是否应进行访问。标志位随同结点的指针一起存入栈中。标志位的使用无疑增加了存贮空间。我们提出的改进算法,无须为二叉树的结点建立标志位,从而节省了存贮空间,但并不增加算法的时间复杂度。算法中所采用的思想与技巧亦可以推广应用到一般树(多叉树)的遍历算法中。
|
关 键 词: | 二叉树 遍历二叉树 算法 数据结构 |
本文献已被 CNKI 维普 等数据库收录! |
|