文档介绍：电脑编程技巧与维护�
汉诺塔非递归算法�
陈文�
�福州职业技术学院计算机系,福州��
摘要:分析汉诺塔递归算法的特点,由递归算法,结合二叉树的中序遍历算法,提出汉诺塔二叉树的概念及创建�
方法,并证明汉诺塔二叉树特点。由此进一步导出兼顾时间效率与空间效率的非递归算法。最后,提供实现算法的�
�语言程序。�
关键词: 汉诺塔;非递归算法;二叉树�
��
��
��,��,��
��:��—��,��’��
��—��,��.��
��.��.��,��
��.��,��.�
��:��——��——��;��——��;��;�
��引言��一�,�,�,��;�
汉诺塔问题说的是,有三根柱子,不妨称为�、�、�三��%�%�一�%�\��”,�,�,��;�
��一�,�,�,��;�
柱,�柱上有大小不同的�个盘子,最上面的盘子最小,最下�
��
面的盘子最大,不妨用�,�,�,⋯⋯,�从上到下对�个盘�
��
子编号,每次从一个柱中移动一个盘到另一柱上,同时,做�
�兼顾时间与空间的非递归算法�
到大不压小,最后把�个盘移到�柱,要求写出移动过程。�
�.�操作过程与二叉树的对应关系�
汉诺塔问题常用的解法是用递归算法,这是数据结构课中递�
从汉诺塔的递归算法中可知,当盘子的个数大于�时,�
归算法的经典例子。但不难发现,这种递归算法占用相当大�
汉诺塔的移动过程分为�步,第一步将�一�个盘从�移到�;�
栈空间,而且运行速度较慢,当盘数�较大时,常常会因栈�
第二步将第�盘从�移到�;第三步将�一�个盘从�移到�。�
溢出而无法运行。近几年,不少学者对汉诺塔问题的非递归�
如果把移动过程看作是二叉树的中序遍历��,则可用图�盼�
算法作