admin 管理员组文章数量: 1086019
2024年9月14日发(作者：网页界面设计和素材)
第２３卷第１期 电脑开发与应用
文章编号：１００３—５８５０（２０１０）９１—００５３—０３
二叉树的先序遍历和中序遍历的非递归算法
Ｄｉｓｃｕｓｓｉｏｎ ａｎｄ Ａｎａｌｙｓｉｓ ｏｆ Ｎｏｎ—ｒｅｃｕｒｓｉｖｅ Ａｌｇｏｒｉｔｈｍ ｆｏｒ Ｐｒｅｏｒｄｅｒ
Ｔｒａｖｅｒｓａｌ ａｎｄ Ｉｎｏｒｄｅｒ Ｔｒａｖｅｒｓａｌ ｏｆ Ｂｉｎａｒｙ Ｔｒｅｅ
黄 霞
（西安工程大学计算机科学学院 西安 ７１００４８）
【摘 要】从二叉树先序遍历递归算法的执行过程的分析入手，总结出二叉树先序遍历的实质，从而得出利用栈
的二叉树的非递归算法。最后，再从分析二叉树中序遍历与先序遍历过程实质的不同之处，得出了二叉树中序
遍历的非递归算法。重点在于对二叉树先序和中序遍历过程实质的分析。
【关键词】二叉树先序遍历，二叉树中序遍历，栈，递归算法，非递归算法
中图分类号：ＴＰ３１１．１２ 文献标识码：Ａ
ＡＢＳＴＲＡＣＴ ｂｅｇｉｎｎｉｎｇ ａｔ ｔｈｅ ｉｍｐｌｅｍｅｎｔａｔｉｏｎ ｐｒｏｃｅｓｓ ｏｆ ｂｉｎａｒｙ ｔｒｅｅ’Ｓ ｐｒｅｏｒｄｅｒ ｔｒａｖｅｒｓａｉ，ａｕｔｈｏｒ ｓｕｍｍａｒｙ ｔｈｅ ｒｅａｌ ｏｆ ｂｉｎａｒｙ
ｔｒｅｅ’Ｓ ｐｒｅｏｒｄｅｒ ｔｒａｖｅｒｓａｌ ａｎｄ ｏｂｔａｉｎ ｎｏｎ ｒｅｃｕｒｓｉｖｅ ａｌｇｏｒｉｔｈｍ ｆｏｒ ｂｉｎａｒｙ ｔｒｅｅ’Ｓ ｐｒｅｏｒｄｅｒ ｔｒａｖｅｒｓａｌ ｕｓｉｎｇ ｓｔａｃｋ．Ａｔ ｌａｓｔ．ｏｂｔａｉｎｉｎｇ ｎｏｎ
ｒｅｃｕｒｓｉｖｅ ａｌｇｏｒｉｔｈｍ ｆｏｒ ｂｉｎａｒｙ ｔｒｅｅ’Ｓ ｉｎｏｒｄｅｒ ｔｒａｖｅｒｓａｌ ｆｒｏｍａｎａｌｙｓｉｓｉｎｇ ｔｈｅ ｄｉｆｆｅｒｅｎｃｅ ｂｅｔｗｅｅｎ ｉｎｏｒｄｅｒ ｔｒａｖｅｒｓａｌ ａｎｄ ｐｒｅｏｒｄｅｒ
ｔｒａｖｅｒｓａ１．Ｔｈｅ ｉｍｐｏｒｔａｎｃｅ ｉｓ ａｎａｌｙｓｉｓｉｎｇ ｏｆ ｔｈｅ ｒｅａｌ ｆｏｒ ｂｉｎａｒｙ ｔｒｅｅ’Ｓ ｐｒｅｏｒｄｅｒ ｔｒａｖｅｒｓａｌ ａｎｄ ｂｉｎａｒｙ ｔｒｅｅ’Ｓ ｉｎｏｒｄｅｒ ｔｒａｖｅｒｓａ１．
ＫＥＹＷＯＲＤＳ ｂｉｎａｒｙ ｔｒｅｅ’Ｓ ｐｒｅｏｒｄｅｒ ｔｒａｖｅｒｓａｌ，ｂｉｎａｒｙ ｔｒｅｅ’
ａｌｇｏｒｉｔｈｍ
１二叉树先序遍历的非递归算法
点的指针，ＰＡ就表示指向 结点。ｒｏ表示调用此函数
的返回地址；ｒｌ表示从左子树调用子函数的返回地
树是应用比较广泛的一种数据结构，二叉树又是
址 ２表示从右子树调用子函数的返回地址。
树中常用的一种数据结构。对二叉树的遍历可以应用
到程序设计的各个领域。由二又树的先序及中序遍历
的定义，递归遍历算法书写起来容易，但要对其的执行
过程有一深入的理解，递归遍历算法的执行速度也比
较慢；由此，我们可以找出规律，写出其非递归算法。
二又树的存储表示为：
Ｔｙｐｅｄｅｆ ｓｔｒｕｃｔ ｂｉｔｎｏｄｅ
｛
Ｄａｔａｔｙｐｅ ｄａｔａ；
图１二叉树例子
Ｓｔｒｕｃｔ ｂｉｔｎｏｄｅ＊ｌｃｈｉｌｄ，＊ｒｃｈｉｌｄ；
二又树先序遍历递归时栈的变化情形如下：
｝ｂｉｔｎｏｄｅ，＊ｂｉｔｒｅｅ；
由二叉树先序遍历的性质，我们得出二叉树先序
从二叉树先序遍历非递归算法实现时系统栈的变
遍历的递归算法：
化情况，我们不难看出，二叉树先序遍历实际上是走丫
一
Ｐｒｅｏｒｄｅｒ（ｂｉｔｒｅｅ ｂｔ）
条从根结点左外侧开始，由根结点右外侧结束的曲
｛ｖｉｓｉｔ（ｂｔ一＞ｄａｔａ）；
线。该路线从根结点开始沿左子树深入下去．深入到最
Ｐｒｅｏｒｄｅｒ（ｂｔ一＞ｌｃｈｉｌｄ）；
左端，无法再深入下去时，则返回，再逐一进入深入时
Ｐｒｅｏｒｄｅｒ（ｂｔ一＞ｒｃｈｉｌｄ）；
遇到结点的右子树，再进行如此的深入和返回，直到最
｝
后从根结点的右子树返回根结点为止。且深入一个结
由栈与递归的关系，我们知道二叉树先序遍历递 点访问一个结点。
归算法的执行，系统会自动生成一个栈，来完成该算法
在沿左子树深入时，无法再深人下去时，即左子
的执行。下面以一个具体的二叉树为例，给出执行此递
树为空时，就应退回到该结点的右子树，一样是深入时
归算法时栈的情形。假设栈含有两个域，一个为指向结
访问结点。当它的左右子树都走完时，则要退出该结
＊ ２００９—０７—３０收到，２００９—１１－２０改回
＊＊ 黄霞，女，１９６４年生，学士，工程师，研究方向：计算机软件工程。
二叉树的先序遍历和中序遍历的非递ＩＪ］算法
通过上面的分析及二叉树的二叉链表表示，我们
ＰＤ ｒｌ
Ｐ８ ｒ１
Ｐ ｒｌ
』 ７‘Ｏ
』 ｒＯ
（１）显示Ａ （２）显示Ｂ
， １
ｒ１
坨
彤 ｒ２
Ｄ ｒｌ
ＰＤ ｒ１ Ｄ ｒｌ
Ｉ，Ｂ ｒ１
ＰＢ ｒｌ ，）Ｂ ｒ１
】， ｒＯ
ＰＡ ｒＯ Ｐ ｒ０
ｒ２
ｊ ； ｒ２
ｊ Ｄ ｒ１
、
Ｐ８ ｒ１ ｒ２
４ ｒＯ
ＰＡ ｒＯ
（８）显示Ｃ （９）显示Ｅ
ｒｌ ｒ２
ＰＥ ｒｌ ， ｒ１
ＰＦ ｒ２
ｒ２ Ｉ℃ ｒ２
彤 ｒ２
ＰＡ ｒＯ
ａ ｒＯ
，Ｊ以 ｒＯ
（１２）显示Ｆ
ｒｌ
ｒ２
ｒ２
ＰＦ ｒ２
Ｉ Ｒ ｒ２
门 ｒ２
，ＪＡ ｒＯ
ＰＡ ｒＯ
（１３） （１４） （１５）
图２二叉树遍历递归时栈的变化
图３二叉树先序遍历
点，指针指向深入时前一个结点，因此，我们在编写非
递归算法时，就要引人栈这个数据结构。如果该结点的
左右子树仍然都走过，则仍要退栈，若右子树没走过，
则继续深入与返回。而且，我们还可以看到，当栈空且
指针为空时，结束。
我们看到，深入时一定先从左子树开始的，边深入
边访问边进栈，返回时才从右子树进行，并接着退栈与
深入右子树。
可以得出二叉树的先序遍历的非递归算法：
Ｖｏｉｄ ｐｒｅ：ｏｒｄｅｒ（ｂｉｔｒｅｅ ｂｔ）
｛
Ｓｔａｃｋｔｙｐｅ ｓｔａｃｋ［－ｍａｘｎｏｄｅ］；
Ｂｉｔｒｅｅ Ｐ；
Ｉｎｔ ｔｏｐ一０；
Ｐ＝ｂｔ： 、
Ｉ）ｏｆ
Ｗｈｉｌｅ（ｐ！一ｎｕｌ１）
｛ｖｉｓｉｔ（ｐ一）＞ｄａｔａ）；
ｓｔａｃｋ［＋％ｔｏｐ￣一Ｐ；
Ｐ—ｐ－）＞ｌｃｈｉｌｄ；
ｆ
Ｐ：ｓｔａｅｋ［ｔｏｐ￣；
Ｐ—ｐ－＞ｒｃｈｉｌｄ；
｝ｗｈｉｌｅ（ｔｏｐ＞０）
）
表１ 二叉树先序非递归遍历过程
步骤 指针Ｐ 栈ｓ ｔａｃｋ内容 访问结点
初态 一 空
１ 上；
２ Ｄ ．Ｂ Ｂ
３ Ａ， ， ） Ｄ
４ Ｇ ．Ｂ
５ ‘４．Ｂ。Ｇ Ｇ
６ ．
７ Ａ
８ Ｃ 空
９ Ｅ Ｃ Ｃ
】０ Ｃ．Ｅ
１１ Ｃ
１２ Ｆ 空
１３ Ｆ Ｆ
１４ 空
２二叉树中序遍历的非递归算法
二叉树中序遍历的过程与七面介绍的先序遍历是
一
样的。也是走了相同的路线，也是先深入左子树，当
深入不下去时，返回到前一结点深入其右子树，当指针
为空且栈为空时结束等等。由二叉树中序遍历的性质
可知，它只是在左子树深入不下去，返回到其结点的右
子树前，才对该结点进行访问。而其他的过程都与先序
遍历完全相同，因此，二叉树中序遍历的非递归算法只
是访问结点语句改在ｐ—ｓｔａｃｋ［ｔｏｐ］和Ｐ—ｐ－＞ｒｃｈｉｌｄ
之间 （下转第５９页）
第２３卷第１期 电脑开发与应用
３ 实 验
３．１ ＯＲＬ人脸数据库
为验证本算法，实验中采用剑桥ＯＲＩ 人脸数据
库，该数据库由英国剑桥大学的ＡＴ＆Ｔ实验室采集，
包括４０人的每人１０张人脸灰度图像，共计４００张。每
张图像的尺寸为１１２×９２像素，包括表情变化，微小姿
态变化，１０ 以内的尺度变化。比较充分地反应了同一
个人不同人脸图像的变化和差异。将图像库中的人脸
图像平均分为两组，其中２００张为训练样本，另外２００
张为测试样本。
３．２ 实验结果
为便于比较，选取特征空间维数 一１０，训练样本
数ｋ一２００。本文算法对样本进行二次小波分解。几种
算法的识别率如表１所示。
表１三种算法识别率比较
识别方法
］
【＝
］
识别率（
］
）
］
＿寸
ＰＣＡ ８４：．２
２ＤＰＣＡ ８９．２
小波变换＋２ＤＰＣＡ ９２．５
从上面的实验数据我们可以看出：
①传统ＰＣＡ方法的识别率较低，这主要是因为
传统的ＰＣＡ方法是基于图像的灰度统计值，外在因素
带来的图像差异和人脸本身带来的图像差异无法区
分。
②与传统ＰＣＡ方法不同，２ＤＰＣＡ方法最显著地
特点就是采用了最大化类问离散度作为准则，首先利
用了原始图像矩阵来构造图像的协方差矩阵，这样使
得在特征提取上更加直观，总体的计算量也远远小于
传统ＰＣＡ，所以可以显著地提高图像特征的提取速
度。由于有着更小的样本尺寸，使得图像的方差也更
小，这样计算矩阵的协方差也更为准确，因此，识别率
也有了明显的提高。
⑧通过小波变换，人脸图像的分辨率降低，图像
维数降低，显著地减轻了２ＤＰＣＡ计算复杂度，也节约
了存储空间；同时提供了空问域和频域的局部信息，选
择小波分解的低频分量，由于不包含高频信息，因此削
弱了光线、表情变化和部分附属物对２ＤＰＣＡ算法识
别率的影响，增强了对噪声的鲁棒性。采用基于小波变
换的２ＤＰＣＡ识别方法，可以获得很好的识别效果，同
时降低了运算的复杂度，从而节约了时间。
４结论
实验结果表明，本文提出的算法不仅提高了特征
提取的速度，降低了识别时间，而且识别率和识别速度
也都得到了进一步的改善；同时对于人脸表情变化、姿
态变化、附属物干扰具有一定的鲁棒性。
参考文献
Ｐｅｎｔｌａｎｄ Ａ．Ｌｏｏｋｉｎｇ ａｔ Ｐｅｏｐｌｅ： Ｓｅｎｓｉｎｇ ｆｏｒ
Ｕｂｉｑｕｉｔｏｕｓ ａｎｄ Ｗｅａｒａｂｌｅ Ｃｏｍｐｕ２ｔｉｎｇ［Ｊ］．ＩＥＥＥ
Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｐａｔｔｅｒｎ ＡｎａｌＭａｃｈｉｎｅ Ｉｎｔｅｌｌ，２０００，
２２（１）：１０７—１１９．
Ｂｅｌｈｕｍｅｕｒ Ｐ Ｎ，Ｈｅｓｐａｎｈａ Ｊ Ｐ，Ｉｅｎｇｍａｎ Ｋ Ｒ Ｄ Ｊ．
Ｅｉｇｅｎｆａｃｅｓ ＶＳ Ｆｉｓｈｅｒｆａｃｅｓ：Ｒｅｃｏｇｎｉｔｉｏｎ Ｕｓｉｎｇ Ｃｌａｓｓ
Ｓｐｅｃｉｆｉｃ Ｌｉｎｅａｒ Ｐｒｏｊｅｃｔｉｏｎ［Ｊ］．ＩＥＥＥ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ
Ｐａｔｔｅｒｎ ＡｎａｌＭａｃｈｉｎｅ Ｉｎｔｅｌｌ，１９９７，１９（７）：７１１－７２０．
Ｉ ｉｕ Ｋ，Ｃｈｅｎｇ Ｙ Ｑ，Ｙａｎｇ ｊ Ｙ．Ａｌｇｅｂｒａｉｃ Ｆｅａｔｕｒｅ
Ｅｘａｃｔｉｏｎ ｆｏｒ Ｉｍａｇｅ Ｒｅｃｏｇｎｉｔｉｏｎ ｂａｓｅｄ ｏｎ ａｎ Ｏｐｔｉｍａｌ
Ｄｉｓｅｒｉｍｉｎａｎｔ Ｃｅｉｔｅｒｉｏｎ［Ｊ］．Ｐａｔｔｅｎ Ｒｅｃｏｇｎｉｔｉｏｎ。ｌ ９９３，
２６（６）：９０３—９１１．
Ｙａｎｇ Ｊ，Ｚｈａｎｇ Ｄａｖｉｄ，Ｙａｎｇ Ｊ Ｙ．Ｔｗｏ—ｄｉｍｅｎｓｉｏｎａｌ
ＰＣＡ：ａ Ｎｅｗ Ａｐｐｒｏａｃｈ ｔＯ Ａａｐｐｅａｒａｎｃｅ—ｂａｓｅｄ Ｆａｃｅ
Ｒｅｐｒｅｓｅｎｔａｔｉｏｎ ａｎｄ Ｒｅｃｏｇｎｉｔｉｏｎ ［Ｊ］． ＩＥＥＥ
Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｐａｔ｛ｅｒｎ Ａｎａｌｙｓｉｓ ａｎｄ Ｍａｃｈｉｎｅ
Ｉｎｔｅｌｌｉｇｅｎｃｅ，２００４，２６（ｉ）：Ｉ３１一ｉ３７．
胡元奎，汪增福．可变光照条件下的人脸图像识别ｌ＿Ｊ］．
中国图象图形学报，２００５，１Ｏ（７）：８４４—８４９．
（上接第５４页）
．
可以表示如下：
Ｖｏｉｄ ｉｎｏｒｄｅｒ（ｂｉｔｒｅｅ ｂｔ）
｛
Ｓｔａｃｋｔｙｐｅ ｓｔａｃｋ Ｆｍａｘｎｏｄｅ；
Ｂｉｔｒｅｅ Ｐ；
Ｉｎｔ ｔｏｐ一０；
Ｐ＝ｂｔ：
１）ｏ｛
Ｗｈｉｌｅ（ｐ！一ｎｕｌ１）
｛ｓｌａｃｋ［＋＠ｔｏｐ￣一Ｐ；
Ｐ＝Ｐ￣ｌｃｈｉｌｄ：
）
ｐ＝ｓｔａｃｋ［ｔｏｐ￣；
ｖｉｓｉｔ（ｐ一＞ｄａｔａ）；
Ｐ＝ ｐ－￣ｒｃｈｉｌｄ；
｝ｗｈｉｌｅ（ｔｏｐ￣Ｏ）
｝
参考文献
严蔚敏，吴伟民编著．数据结构（（：语言版）［Ｍ］．北京：
…
清华大学出版社，２００８．
Ｌ
耿国华编著．数据结构（ｃ语言版）［Ｍ］．西安：西安电
子科技大学出版社，２００３．
［。］
蒋文蓉编著．数据结构ＥＭ］．北京：高等教育出版社，
２００３．
版权声明：本文标题：二叉树的先序遍历和中序遍历的非递归算法 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://roclinux.cn/p/1726249156a932785.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。
发表评论