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)

最近更新

高一语文学习计划(13篇) 38页

论述销售人员忠诚度管理 21页

超音速等离子体炬的磁流体动力学数值研究 3页

负面网络口碑对品牌忠诚影响因素的实证研究 3页

试析热工计量自动检定技术的应用 3页

议题设置推动智库国际化发展的实证研究 3页

规范房屋“养老金”管理实践——以平顶山市为.. 3页

补料工艺对三孢布拉霉菌合成β-胡萝卜素的影响.. 3页

表达能力的重要性 32页

2025年度个人租房合同协议书模板(含租赁房屋.. 7页

2025平安福保险合同电子版健康管理系统合作协.. 9页

脉搏血氧仪的开短路的在线检测应用设计 3页

螺纹环换热器总体介绍 35页

绿色、智能及节能技术在建筑中的应用分析 3页

管道防腐层的检查及分析技术探讨 3页

竹芯模盒现浇混凝土空心楼盖施工技术研究 3页

韶关市“广东技工”职业技能大赛计算机网络应.. 7页

私募股权投资中对赌协议的研究 4页

磁浮轴承及其应用 3页

砒砂岩重塑土力学特性及本构模型试验研究 3页

荧光偏振免疫分析 14页

色谱概论和经典液相色谱法 27页

2025年龙猫电影观后感350字 6页

2025年龙年春节男宝宝名字 5页

2025年龙宝宝有福气的乳名女孩 7页

2025年鲁滨孙漂流记读后感50字 6页

2025年高考生心理焦虑疏导 4页

2025年高考模拟填报志愿注意事项 4页

2025年属鼠2025年有大喜缠身 6页

小学语文新部编版一年级下册第二单元语文园地.. 35页