文档介绍：��牟第�期�
中图分类号:��.��文献标识码:�文章编号:��—��—��—��
普通树非递归遍历算法的实现�
高红军�
�辽宁广播电视大学丹东分校,丹东��
摘要:根据普通树与其对应二叉树表示法在遍历序列上的特点,利用堆栈实现普通树深度优�
先遍历的非递归算法,利用队列实现普通树广度优先遍历的非递归算法。同时给出对普通树从�
输入到输出及三种遍历算法实现的完整的��语言程序。�
关键词:树;树的二叉树表示法;深度优先遍历;广度优先遍历�
��
��
��.��
��,��,��
��: ��—��
��,��
��——��
��.��
��.�
��: ��;��;��~��;��
��树与二叉树概念及其转换规则�树在日常生活中广泛存在,家族关系、单位中组�
树是树型数据结构的简称,它是一种重要的非�织结构、一本书的结构、磁盘的目录结构等等,因此�
线性结构。树——或者是一棵空树,或者有且仅有�研究树的运算具有较大的现实意义。要解决的树型�
一个根结点,其余所有结点分属于�个互不相交的�结构问题本身千差万别,如何能够找到一种统一的�
集合中,每个集合又构成一个树,称为树根结点的子�方法来实现树的运算尤为重要。�
树,每个子树又同样是一棵树。例如图�所示的结�二叉树是人们为了解决树型结构问题而创造的�
一种特殊的树,它是度不大于�的有序树。二叉树�
构就是一棵树。�
在实现存储与运算上相对简单,可以先按照一定的�
规则把树转化为二叉树,从而通过实现二叉树的运�
算来完成树的运算。将一棵树转化为二叉树的规则�