二叉树遍历的操作与实现
2023-04-18 15:17:00 时间
先序遍历
先序遍历(递归版)
代码展示
/*
先序遍历(递归版)
*/
Status PreOrderTraverse(BiTree T, Status Visit(TElemType e)) {
if (T)
{
Visit(T->data);
PreOrderTraverse(T->lchild, Visit);
PreOrderTraverse(T->rchild, Visit);
}
return SUCCESS;
}
思路解析
先序遍历,首先判断二叉树T是否为空,若为空则代表二叉树已遍历完成。若非空则代表该结点有值,然后调用Visit方法将结点值打印出来。随后再寻找该结点的左右子结点,再重复上述步骤实现先序遍历。
先序遍历(非递归版)
代码展示
/*
先序遍历(非递归版)
*/
Status PreOrderTraverseStore(BiTree T, Status Visit(TElemType e)) {
if (T == nullptr)
{
return ERROR;
}
BiTree p;
LinkStack S;
InitStack(S);
Push(S, T);//根进栈
while (!StackEmpty(S))
{
while ((GetTop(S, p) && p)) {
if (!Visit(p->data))
{
return ERROR;
}
Push(S, p->lchild);//左走到尽头
}
Pop(S, p);//空指针退栈
if (!StackEmpty(S))//访问结点
{
Pop(S, p);
Push(S, p->rchild);
}
}
return SUCCESS;
}
思路解析
非递归版是采用栈来实现,初始化将原始二叉树赋值给p,然后让其入栈。之后遍历其左子树所有结点,左子树结点遍历完成后,弹出空指针栈顶,开始遍历右子树结点。每遍历一次便将新的头结点二叉树压入栈中。
中序和后序遍历
中序遍历及后序遍历(递归版)
代码展示
/*
中序遍历
*/
Status InOrderTraverse(BiTree T, Status Visit(TElemType e)) {
if (T != nullptr)
{
InOrderTraverse(T->lchild, Visit);
Visit(T->data);
InOrderTraverse(T->rchild, Visit);
}
return SUCCESS;
}
/*
后序遍历
*/
Status PostOrderTraverse(BiTree T, Status Visit(TElemType e)) {
if (T != nullptr)
{
PostOrderTraverse(T->lchild, Visit);
PostOrderTraverse(T->rchild, Visit);
Visit(T->data);
}
return SUCCESS;
}
中序遍历和后序遍历(非递归版)
代码展示
/*
中序遍历(非递归)
*/
Status InOrderTraverseStore(BiTree T, Status Visit(TElemType e)) {
if (T == nullptr)
{
return ERROR;
}
BiTree p;
LinkStack S;
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);
}
}
return SUCCESS;
}
/*
后序遍历(非递归版)
*/
Status PostOrderTraverseStore(BiTree T, Status(*Visit)(TElemType e)) {
if (T == nullptr)
{
return ERROR;
}
BiTree p = T, r = nullptr;
LinkStack S;
InitStack(S);
while (p != nullptr || !StackEmpty(S))
{
if (p)
{
Push(S, p);
p = p->lchild;
}
else
{
GetTop(S, p);
if (p->rchild && p->rchild != r)
{
p = p->rchild;
Push(S, p);
p = p->lchild;
}
else
{
Pop(S, p);
Visit(p->data);
r = p;
p = nullptr;
}
}
}
return SUCCESS;
}
思路解析
中序和后序遍历与先序遍历差别不大,只是在与父结点的顺序有关。父结点在最前即为先序遍历,父结点在左右子结点中便是中序遍历,父结点在左右子结点之后便是后序遍历。代码实现类似,使用递归或栈来实现。
层次遍历
代码展示
/*
层次遍历
*/
Status LevelOrderTraverse(BiTree& T) {
LinkQueue lq;
InitQueue(lq);
QElemType q;
EnQueue(lq, T);
while (QueueEmpty(lq) != SUCCESS) //对列不空,则出队
{
DeQueue(lq, q);
printf("%c ", q->data);
if (q->lchild)
{
EnQueue(lq, q->lchild); //若有左孩子,则入队
}
if (q->rchild)
{
EnQueue(lq, q->rchild); //若有右孩子,则入队
}
}
return SUCCESS;
}
思路解析
层次遍历使用队列来进行遍历,首先原始二叉树入队,然后退队,打印结点值。查询该结点是否有左右子结点,若有则入队。循环往复上述步骤,当队列为空时,则层次遍历完成。
相关文章
- 【技术种草】cdn+轻量服务器+hugo=让博客“云原生”一下
- CLB运维&运营最佳实践 ---访问日志大洞察
- vnc方式登陆服务器
- 轻松学排序算法:眼睛直观感受几种常用排序算法
- 十二个经典的大数据项目
- 为什么使用 CDN 内容分发网络?
- 大数据——大数据默认端口号列表
- Weld 1.1.5.Final,JSR-299 的框架
- JavaFX 2012:彻底开源
- 提升as3程序性能的十大要点
- 通过凸面几何学进行独立于边际的在线多类学习
- 利用行动影响的规律性和部分已知的模型进行离线强化学习
- ModelLight:基于模型的交通信号控制的元强化学习
- 浅谈Visual Source Safe项目分支
- 基于先验知识的递归卡尔曼滤波的代理人联合状态和输入估计
- 结合网络结构和非线性恢复来提高声誉评估的性能
- 最佳实践丨云开发CloudBase多环境管理实践
- TimeVAE:用于生成多变量时间序列的变异自动编码器
- 具有线性阈值激活的神经网络:结构和算法
- 内网渗透之横向移动 -- 从域外向域内进行密码喷洒攻击