二叉树的层次遍历（非递归）可否借助栈来实现？

2025-01-23 07:01:40

推荐回答（2个）

回答1：

//层次遍历代码

template
void BinTree::view()
{
if (IsNull()) return;
deque*> q;

TreeNode* temp;
q.push_back(root);
while(!q.empty())
{
temp = q.front();
q.pop_front();
cout<data;
if (temp->Left!=NULL)
q.push_back(temp->Left);
if (temp->Right!=NULL)
q.push_back(temp->Right);
}
cout<}

1.先序遍历非递归算法
#define maxsize 100
typedef struct
{
Bitree Elem[maxsize];
int top;
}SqStack;

void PreOrderUnrec(Bitree t)
{
SqStack s;
StackInit(s);
p=t;

while (p!=null || !StackEmpty(s))
{
while (p!=null) //遍历左子树
{
visite(p->data);
push(s,p);
p=p->lchild;
}//endwhile

if (!StackEmpty(s)) //通过下一次循环中的内嵌while实现右子树遍历
{
p=pop(s);
p=p->rchild;
}//endif

}//endwhile

}//PreOrderUnrec

2.中序遍历非递归算法
#define maxsize 100
typedef struct
{
Bitree Elem[maxsize];
int top;
}SqStack;

void InOrderUnrec(Bitree t)
{
SqStack s;
StackInit(s);
p=t;
while (p!=null || !StackEmpty(s))
{
while (p!=null) //遍历左子树
{
push(s,p);
p=p->lchild;
}//endwhile

if (!StackEmpty(s))
{
p=pop(s);
visite(p->data); //访问根结点
p=p->rchild; //通过下一次循环实现右子树遍历
}//endif

}//endwhile

}//InOrderUnrec

3.后序遍历非递归算法
#define maxsize 100
typedef enum tagtype;

typedef struct
{
Bitree ptr;
tagtype tag;
}stacknode;

typedef struct
{
stacknode Elem[maxsize];
int top;
}SqStack;

void PostOrderUnrec(Bitree t)
{
SqStack s;
stacknode x;
StackInit(s);
p=t;

do
{
while (p!=null) //遍历左子树
{
x.ptr = p;
x.tag = L; //标记为左子树
push(s,x);
p=p->lchild;
}

while (!StackEmpty(s) && s.Elem[s.top].tag==R)
{
x = pop(s);
p = x.ptr;
visite(p->data); //tag为R，表示右子树访问完毕，故访问根结点
}
if (!StackEmpty(s))
{
s.Elem[s.top].tag =R; //遍历右子树
p=s.Elem[s.top].ptr->rchild;
}
}while (!StackEmpty(s));
}//PostOrderUnrec

问题来自《数据结构》（严蔚敏、吴伟民著，C语言描述，清华大学出版社，1997年4月第1版），第6章树与二叉树，6.3遍历二叉树和线索二叉树。

遍历二叉树的非递归算法，教材的描述如下（见130页）：

仿照递归算法执行过程中递归工作栈的状态变化状况可直接写出相应的非递归算法。例如，从中序遍历递归算法执行过程中递归工作栈的状态可见：（1）工作记录中包含两项，其一是递归调用的语句编号，其二是指向根结点的指针，则当栈顶记录中的指针非空时，应遍历左子树，即指向左子树根的指针进栈；（2）若栈顶记录中的指针值为空，则应退至上一层，若是从左子树返回，则应访问当前层即栈顶记录中指针所指的根结点；（3）若是从右子树返回，则表明当前曾的遍历结束，应继续退栈。从另一角度看，这意味着遍历右子树时不再需要保存当前层的根指针，可直接修改栈顶记录中的指针即可。由此可得两个中序遍历二叉树的非递归算法如下：

=============================================================

算法一：

Status InOrderTraverse(BiTree T, Status(*Visit)(TElemType e))
{
//采用二叉链表存储结构，Visit是对数据元素操作的应用函数。
//中序遍历二叉树T的非递归算法，对每个数据元素调用函数Visit。

InitStack(S);
Push(S,T); //根指针进栈

while(!StackEmpty(s))
{
while(GetTop(S,p)&&p)
Push(S,p->lchild); //向左走到尽头
Pop(S,p); //空指针退栈
if(!StackEmpty(S)) //访问结点，向右一步
{
Pop(S,p);
if(!Visit(p->data))
return ERROR;
Push(S,p->rchild);
}//if
}//while
return OK;
}//InOrderTraverse 算法一
============================================================
============================================================
算法二：

Status InOrderTraverse(BiTree T, Status (*Visit)(TelemType e))
{
//采用二叉链表存储结构，Visit是对数据元素操作的应用函数。
//中序遍历二叉树T的非递归算法，对每个数据元素调用函数Visit。
InitStack(S);
p=T;
while(p||!StackEmpty(S))
{
if(p)
{
Push(S,p);
p=p->lchild;
}//if 根指针进栈，遍历左子树
else
{
Pop(S,p);
if(!Visit(p->data))
return ERROR;
p=p->rchild;
}//else 根指针退栈，访问根结点，遍历右子树
}//while
}InOrderTraverse() 算法二
============================================================

我的问题是，文字描述中提到的“从中序遍历递归算法执行过程中递归工作栈的状态可见：……”的这一部分。我不明白什么是“栈顶记录中的指针”，什么是“工作记录”。不明白第（2）句话中，先说“栈顶记录中的指针值为空”的时候怎么怎么样，后面为什么又会有对“栈顶记录中指针所指的根结点”的访问？这不是前后矛盾的吗？在读完后面的代码并作了认真的分析之后，仍不明白这一段话到底描述了一个什么样的过程，不理解转化成非递归过程的具体实现。请达人指教。
问题补充：参考：

对代码中与栈有关的函数的说明：
InitStack(&S) 构造一个空栈S；
Push(&S,e) 栈已存在时，插入元素e为新的栈顶元素；
StackEmpty(S) 栈已存在时，若为空栈返回TRUE，否则返回FALSE；
GetTop(S,&e) 栈已存在且非空时，用e返回S的栈顶元素；
Pop(&S,&e) 栈S存在且非空时，删除栈顶元素，并用e返回其值；
——摘自该书45页。

中序遍历二叉树的操作递归定义：
若二叉树为空，则空操作；
否则
（1）中序遍历左子树；
（2）访问根结点；
（3）中序遍历右叉树；
——摘自该书128页。

递归过程转为非递归过程的实质：
将原由系统管理的递归工作栈改为由程序员管理。在非递归过程中，递归工作栈同样起着两个作用：其一是将递归调用室的实在参数和返回地址传递给下一层递归；其二是保存本层参数和局部变量，以便从下一层返回本层时继续恢复使用。如果将栈的每一层视为一项待处理的事务，则栈顶记录则是当前急待处理的事务。
——摘自《数据结构》PASCAL语言描述，严蔚敏、吴伟民著，清华大学出版社。