C++超详细实现二叉树的遍历
二叉树的遍历
Q：什么是二叉树的遍历？
A：二叉树的遍历是指从根结点出发，按照某种次序依次访问二叉树中所有结点，使得每个结点被访问一次，且仅被访问一次。
Q：二叉树有几种遍历方法？
A：二叉树的遍历方法可以有很多种，如果限制了从左到右的习惯方式，那么主要分为以下四种：先序遍历，中序遍历，后序遍历，层序遍历。
前序遍历
Q：什么是先序遍历
A：先序遍历就是先访问树的根节点，再访问树的左子节点，再访问右子节点。可以想象为，从一棵二叉树根节点为起点，沿着二叉树外沿，逆时针走一圈回到根节点，路上遇到的元素顺序，就是先序遍历的结果。
如图：遍历的顺序为 ABDGHCEIF
操作定义
若二叉树为空，则空操作返回，否则：
- 访问根节点
- 先序遍历左子树
- 先序遍历右子树
代码演示
void PreOrderTraversal(BiTree BT)
{
if( BT ！= NULL )
{
printf(“%d\n”, BT->Data); //对节点的数据进行打印
PreOrderTraversal(BT->Left); //访问左子树
PreOrderTraversal(BT->Right); //访问右子树
}
}
中序遍历
Q：什么是中序遍历
A：中序遍历就是访问完所有左子数后再访问根节点，最后访问右子树，即左子树-根节点-右子树。中序遍历可以看成，二叉树每个节点，垂直方向投影下来，然后从左往右数，得出的结果便是中序遍历的结果。
如图：遍历的顺序为GDHBAECF
操作定义
若二叉树为空，则空操作返回，否则：
- 中序遍历左子树
- 访问根节点
- 中序遍历右子树
代码演示
void InOrderTraversal(BiTree BT)
{
if(BT)
{
InOrderTraversal(BT->Left);
printf("%d\n", BT->Data);
InOrderTraversal(BT->Right);
}
}
后序遍历
Q：什么后序遍历
A：后序遍历就是先访问左子树和右子树，最后访问节点，即左子树-右子树-根节点。后序遍历可以看成围着树的外围绕一圈，若下面只有一个结点就摘下来，得出的结果便是后序遍历的结果。
如图：遍历的顺序为GHDBIEFCA
操作定义
若二叉树为空，则空操作返回，否则：
- 后序遍历左子树
- 后序遍历右子树
- 访问根节点
代码演示
void PostOrderTraversal(BiTree BT)
{
if (BT)
{
PostOrderTraversal(BT->Left);
PostOrderTraversal(BT->Right);
printf("%d\n", BT->Data);
}
}
层序遍历
Q：什么层序遍历
A：层次遍历就是从根节点开始，一层一层，从上到下，每层从左到右，依次取值。
如图：遍历的顺序为ABCDEFGHL
代码演示
void LevelOrder(BiTree T){
InitQueue(Q); //初始化辅助队列
BiTree p;
EnQueue(Q,T); //将根结点入队
while(!IsEmpty(Q))
{ //队列不空则循环
DeQueue(Q,p); //队头结点出队
visit(p); //访问出队结点
if(p->1child!=NULL)
EnQueue(Q,p->lchild);//左子树不空，则左子树根结点入队
if(p->rchild!=NULL)
EnQueue(Q,p->rchild);//右子树不空，则右子树根结点入队
}
}
到此这篇关于C++超详细实现二叉树的遍历的文章就介绍到这了,更多相关C++二叉树遍历内容请搜索猪先飞以前的文章或继续浏览下面的相关文章希望大家以后多多支持猪先飞！
原文出处：https://blog.csdn.net/Ceylan__/article/details/124453242
相关文章
- vector是表示可以改变大小的数组的序列容器，本文主要介绍了C++STL标准库std::vector的使用详解，文中通过示例代码介绍的非常详细，具有一定的参考价值，感兴趣的小伙伴们可以参考一下...2022-03-06
- 这篇文章主要介绍了C++中取余运算的实现，文中通过示例代码介绍的非常详细，对大家的学习或者工作具有一定的参考学习价值，需要的朋友们下面随着小编来一起学习学习吧...2021-02-23
- 这篇文章主要介绍了C++ string常用截取字符串方法，文中通过示例代码介绍的非常详细，对大家的学习或者工作具有一定的参考学习价值，需要的朋友们下面随着小编来一起学习学习吧...2020-04-25
- 本文通过例子，讲述了C++调用C#的DLL程序的方法，作出了以下总结，下面就让我们一起来学习吧。...2020-06-25
- 本篇文章主要介绍了C++中四种加密算法之AES源代码，小编觉得挺不错的，现在分享给大家，也给大家做个参考。...2020-04-25
- 整数拆分，指把一个整数分解成若干个整数的和。本文重点给大家介绍C++ 整数拆分方法详解，非常不错，感兴趣的朋友一起学习吧...2020-04-25
- 下面小编就为大家带来一篇js遍历json的key和value的实例。小编觉得挺不错的，现在就分享给大家，也给大家做个参考。一起跟随小编过来看看吧...2017-01-26
- 这篇文章主要介绍了C++中Sort函数详细解析，sort函数是algorithm库下的一个函数，sort函数是不稳定的，即大小相同的元素在排序后相对顺序可能发生改变...2022-08-18
- 这篇文章主要介绍了C++万能库头文件在vs中的安装步骤(图文)，文中通过示例代码介绍的非常详细，对大家的学习或者工作具有一定的参考学习价值，需要的朋友们下面随着小编来一起学习学习吧...2021-02-23
JavaScript中的数组遍历forEach()与map()方法以及兼容写法介绍
下面小编就为大家带来一篇JavaScript中的数组遍历forEach()与map()方法以及兼容写法介绍。小编觉得挺不错的，现在分享给大家，也给大家做个参考。一起跟随小编过来看看吧...2016-05-20- 这篇文章主要介绍了C++ bitset用法，文中通过示例代码介绍的非常详细，对大家的学习或者工作具有一定的参考学习价值，需要的朋友们下面随着小编来一起学习学习吧...2020-04-25
- 本篇文章小编并不是为大家讲解string类型的用法，而是讲解我个人比较好奇的问题，就是string 类型占几个字节...2020-04-25
- 这篇文章主要为大家详细介绍了C++ Eigen库计算矩阵特征值及特征向量，具有一定的参考价值，感兴趣的小伙伴们可以参考一下...2020-04-25
jQuery遍历DOM的父级元素、子级元素和同级元素的方法总结
借助jQuery我们可以轻松地堆DOM元素进行向上、向下遍历以及同级的遍历,本文我们即来整理jQuery遍历DOM的父级元素、子级元素和同级元素的方法总结:...2016-07-25- 这篇文章主要介绍了c# 遍历 Dictionary的四种方式，帮助大家更好的理解和使用c#，感兴趣的朋友可以了解下...2020-12-08
- 这篇文章主要介绍了C++ pair的用法实例详解的相关资料,需要的朋友可以参考下...2020-04-25
- 这篇文章主要介绍了VSCode C++多文件编译的简单使用方法,本文给大家介绍的非常详细，对大家的学习或工作具有一定的参考借鉴价值，需要的朋友可以参考下...2021-03-29
- 虽然C++11引入了智能指针的，但是开发人员在与内存的斗争问题上并没有解放，如果我门实用不当仍然有内存泄漏问题，其中智能指针的循环引用缺陷是最大的问题。下面通过实例代码给大家介绍c++中的循环引用，一起看看吧...2020-04-25
- 这篇文章主要给大家介绍了关于C++随机点名生成器的相关资料，文中通过示例代码介绍的非常详细，对大家的学习或者工作具有一定的参考学习价值，需要的朋友们下面随着小编来一起学习学习吧...2020-04-25
- 下面就为大家带来一篇jquery对Json的各种遍历方法总结(必看篇)。小编觉得挺不错的，现在就分享给大家，也给大家做个参考。一起跟随小编过来看看吧...2016-10-02