基于计数栈的非递归二叉树遍历算法.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)