1 / 9
文档名称:

基于计数栈的非递归二叉树遍历算法.pdf

格式:pdf   大小:604KB   页数:9页
下载后只包含 1 个 PDF 格式的文档,没有任何的图纸或源代码,查看文件列表

如果您已付费下载过本站文档,您可以点这里二次下载

分享

预览

基于计数栈的非递归二叉树遍历算法.pdf

上传人:iris028 2022/5/1 文件大小:604 KB

下载得到文件列表

基于计数栈的非递归二叉树遍历算法.pdf

相关文档

文档介绍

文档介绍:基于计数栈的非递归二叉树遍历算法
作者:中山大学 赵耀 10389332
时间:
目录
基于计数栈的非递归二叉树遍历算法 ...............................栈的第 n 个元素代表路径序列中,位于二叉树第 n 层的元素。算法思想
根据以上分析,我们只需要模拟按箭头经过每一节点的过程,并在每次进入插入对应的
访问函数,就可以形成对应的遍历算法。
如何模拟呢?当每次进入一个节点,我们需要根据已经进入该节点的次数来决定下一节
和所使用的访问函数,所以首先需要对节点的进入次数进行计数。计数和访问该节点之后,
下一节点可能是子节点,也可能是父节点。综上,可以通过对每一节点的数据结构增设一计
数量和一父指针来实现该算法。
现在讨论另一种实现方式,即通过计数栈来实现。
基于以上分析,由于每一条路径唯一对应于一个栈状态,并且,如果栈的元素是节点,
那么栈中每一元素的上一个元素就是该节点的父节点,所以可以一边访问每一个节点,一边
形成对应的栈,在需要返回父节点时,只需要出栈上一节点即可,并且,注意到任一节点只
有在访问满 3 次后才会从栈中移除,因此可以将该计数值设置在栈元素上,而不必设置到每
一个节点上。由于栈的最大深度对应于树的深度,所以相对于前一种实现方案,该方案将节
省许多空间。数据结构
struct BTree
{
int value;
BTree* lchild;
BTree* rchild;
};具体算法
void travel(BTree* tree)
{
stack<pair<BTree*, int>> work_stack;
(make_pair(tree, 0));

while (!())
{
pair<BTree*, int> p = ();
();

// increase the count to indicate that the node
// has been entered (again)
int count = ++;

if (count == 1)
{
preVisit();
(p);
if (->lchild != NULL)
(make_pair(->lchild, 0));
}
else if (count == 2)