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++二叉树遍历内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！

赞 (0)

相关推荐

  • C++基于先序、中序遍历结果重建二叉树的方法

    本文实例讲述了C++基于先序.中序遍历结果重建二叉树的方法.分享给大家供大家参考,具体如下: 题目: 输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树.假设输入的前序遍历和中序遍历的结果中都不含重复的数字.例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6},则重建二叉树并返回. 实现代码: #include <iostream> #include <vector> #include <stack> using

  • C++实现二叉树非递归遍历方法实例总结

    一般来说,二叉树的遍历是C++程序员在面试中经常考察的,其实前中后三种顺序的遍历都大同小异,自己模拟两个栈用笔画画是不难写出代码的.现举一个非递归遍历的方法如下,供大家参考. 具体代码如下: class Solution { public: vector<int> preorderTraversal(TreeNode *root) { vector<int> out; stack<TreeNode*> s; s.push(root); while(!s.empty()

  • C++ 数据结构二叉树（前序/中序/后序递归、非递归遍历）

    C++ 数据结构二叉树（前序/中序/后序递归、非递归遍历）

    C++ 数据结构二叉树(前序/中序/后序递归.非递归遍历) 二叉树的性质: 二叉树是一棵特殊的树,二叉树每个节点最多有两个孩子结点,分别称为左孩子和右孩子. 例: 实例代码: #include <iostream> #include <Windows.h> #include <stack> using namespace std; template <class T> struct BinaryTreeNode { int _data; BinaryTree

  • 一波二叉树遍历问题的C++解答实例分享

    题目一: 输入一颗二元树,从上往下按层打印树的每个节点,同一层按照从左往右的顺序打印. 输入样例: 8 / / 6 10 / / / / 5 7 9 11 输出样例: 复制代码 代码如下: 8 6 10 5 7 9 11 思路分析: 把一颗二叉树抽象成三个节点:根节点.左节点.右节点. 先序遍历即可得到按行输出的效果. 对于左子树只要保存其根节点,既保存了整个左子树.(右子树一样) 对于根节点之外的两个子树来说说,始终是先访问左子树的根节点,再访问右子树的根节点. 因此可以使用队列存储. 代码实

  • C++树之遍历二叉树实例详解

    C++树之遍历二叉树实例详解

    在讲遍历之前,我们要先创建一个树: #include <iostream> using namespace std; typedef struct node; typedef node *tree; struct node{ int data; // 结点数值 tree left,right; // 左子树和右子树 }; tree bt; 遍历二叉树有三种方式: 先序遍历 先序遍历的操作如下: 访问根结点 先序遍历左子树(递归) 先序遍历右子树(递归) 二叉树bt的先序遍历结果:1234753

  • C++ 遍历二叉树实例详解

    C++ 遍历二叉树实例详解

    C++ 遍历二叉树实例详解 2叉数又叫红黑树,关于2叉数的遍历问题,有很多,一般有三种常用遍历方法: (1)前序遍历(2)中序遍历(3)后续遍历 以下是经典示例: #include "stdafx.h" #include<stdio.h> #include<malloc.h> #include <math.h > #define MaxSize 20 typedef struct BiTNode { int data; struct BiTNode

  • C++非递归队列实现二叉树的广度优先遍历

    本文实例讲述了C++非递归队列实现二叉树的广度优先遍历.分享给大家供大家参考.具体如下: 广度优先非递归二叉树遍历(或者说层次遍历): void widthFirstTraverse(TNode* root) { queue<TNode*> q; // 队列 q.enqueue(root); TNode* p; while(q.hasElement()) { p = q.dequeue(); // 队首元素出队列 visit(p); // 访问p结点 if(p->left) q.enqu

  • C++ 非递归实现二叉树的前中后序遍历

    C++ 非递归实现二叉树的前中后序遍历

    目录 二叉树的前序遍历 二叉树的中序遍历 二叉树的后序遍历 二叉树的前序遍历 在不使用递归的方式遍历二叉树时,我们可以使用一个栈模拟递归的机制.二叉树的前序遍历顺序是:根 → 左子树 → 右子树,我们可以先将二叉树的左路结点入栈,在入栈的同时便对其进行访问,此时就相当于完成了根和左子树的访问,当左路结点入栈完毕后再从栈顶依次取出结点,并用同样的方式访问其右子树即可. 具体步骤如下: 将左路结点入栈,入栈的同时访问左路结点. 取出栈顶结点top. 准备访问top结点的右子树. struct Tre

  • C++超详细实现二叉树的遍历

    C++超详细实现二叉树的遍历

    目录 二叉树的遍历 前序遍历 中序遍历 后序遍历 层序遍历 二叉树的遍历 Q:什么是二叉树的遍历? A:二叉树的遍历是指从根结点出发,按照某种次序依次访问二叉树中所有结点,使得每个结点被访问一次,且仅被访问一次. Q:二叉树有几种遍历方法? A:二叉树的遍历方法可以有很多种,如果限制了从左到右的习惯方式,那么主要分为以下四种:先序遍历,中序遍历,后序遍历,层序遍历. 前序遍历 Q:什么是先序遍历 A:先序遍历就是先访问树的根节点,再访问树的左子节点,再访问右子节点.可以想象为,从一棵二叉树根节点

  • C语言 超详细总结讲解二叉树的概念与使用

    C语言 超详细总结讲解二叉树的概念与使用

    目录 1.二叉树的概念及结构 2.二叉树链式结构的实现 1.二叉树的概念及结构 ①概念:一棵二叉树是结点的一个有限集合,该集合或者为空,或者是由一个根节点加上两棵别称为左子树和右子树的二叉树组成. ②二叉树的特点: 每个结点最多有两棵子树,即二叉树不存在度大于2的结点.(度最多为2) 二叉树的子树有左右之分,其子树的次序不能颠倒. ③现实中的二叉树: 当一名普通的人看到这样一颗树,可能会想:好标准的一棵树 当一个程序猿看到这样一棵树,可能会想:好像数据结构中的二叉树,并且还是颗满二叉树 ④数据结

  • Java超详细讲解排序二叉树

    目录 排序二叉树概念 排序二叉树类的定义 添加节点 中序遍历 查找节点 查找某一节点的父节点 删除节点 排序二叉树概念 二叉排序树(Binary Sort Tree),又称二叉查找树(Binary Search Tree),亦称二叉搜索树.是数据结构中的一类. 对于二叉排序树的任何一个非叶子节点, 要求左子节点的值比当前节点的值小,右子节点的值比当前节点的值大. 对二叉排序树进行中序遍历,结果就是按从小到大排序的. 排序二叉树类的定义 public class binarySortTree {

  • C++超详细讲解树与二叉树

    C++超详细讲解树与二叉树

    目录 树 树的定义 树的名词解释 树的表示 树的存储结构 二叉树的概念及结构 二叉树的概念 二叉树的性质 二叉树的存储结构 顺序存储结构 链式存储结构 树 树的定义 Q:什么是树 A:树是一种 非线性 的数据结构,它是由 n ( n>=0 )个有限结点组成一个具有层次关系的集合.把它叫做树是因为它看起来像一棵倒挂的树,也就是说它是根朝上,而叶朝下的. Q:树有什么特点 有一个特殊的结点,称为根结点,根节点没有前驱结点. 除根节点外,其余结点被分成M(M>0)个互不相交的集合T1.T2.…….T

  • Java数据结构超详细分析二叉搜索树

    Java数据结构超详细分析二叉搜索树

    目录 1.搜索树的概念 2.二叉搜索树的简单实现 2.1查找 2.2插入 2.3删除 2.4修改 3.二叉搜索树的性能 1.搜索树的概念 二叉搜索树是一种特殊的二叉树,又称二叉查找树,二叉排序树,它有几个特点: 如果左子树存在,则左子树每个结点的值均小于根结点的值. 如果右子树存在,则右子树每个结点的值均大于根结点的值. 中序遍历二叉搜索树,得到的序列是依次递增的. 二叉搜索树的左右子树均为二叉搜索树. 二叉搜索树的结点的值不能发生重复. 2.二叉搜索树的简单实现 我们来简单实现以下搜索树,就不

  • Java 超详细讲解十大排序算法面试无忧

    Java 超详细讲解十大排序算法面试无忧

    目录 排序算法的稳定性: 一.选择排序 二.冒泡排序 三.插入排序 四.希尔排序 五.堆排序 六.归并排序 七.快速排序 八.鸽巢排序 九.计数排序 十.基数排序 排序算法的稳定性: 假定在待排序的记录序列中,存在多个具有相同的关键字的记录,如果排序以后,保证这些记录的相对次序保持不变,即在原序列中,a[i]=a[j],且 a[i] 在 a[j] 之前,排序后保证 a[i] 仍在 a[j] 之前,则称这种排序算法是稳定的:否则称为不稳定的. 一.选择排序 每次从待排序的元素中选择最小的元素,依次

  • Java 超详细讲解数据结构的应用

    Java 超详细讲解数据结构的应用

    目录 一.bfs 二.双端队列 三.算法题 1.kotori和迷宫 2.小红找红点 3.小红玩数组  一.bfs bfs(广度优先搜索),类似二叉树的层序遍历,利用队列完成.一般用于求最短路. 图的最短路问题: 给定一个无向图,每条边的长度都是1.求1号点到x号点的最短距离. 顶点数n  边数为m q次询问  输入x 输出1到x的最短距离. 若1号点到x不连通,则输出-1 二.双端队列 双端队列的应用(区间翻转): 对于长度为n的数组,给定一个长度为m的区间,区间初始位置为a[1]到a[m].

  • C++超详细实现堆和堆排序过像

    C++超详细实现堆和堆排序过像

    目录 有关堆 C++实现堆 堆的应用 堆排序 有关二叉树的性质: 1. 若规定根节点的层数为1,则一棵非空二叉树的第i层上最多有 个结点. 2. 若规定根节点的层数为1,则深度为h的二叉树的最大结点数是 . 3. 对任何一棵二叉树, 如果度为0其叶结点个数为 , 度为2的分支结点个数为 ,则有 ＝ +1 4. 若规定根节点的层数为1,具有n个结点的满二叉树的深度,h= . (ps: 是log以2 为底,n+1为对数) 5. 对于具有n个结点的完全二叉树,如果按照从上至下从左至右的数组顺序对所有节

  • Java超详细精讲数据结构之bfs与双端队列

    Java超详细精讲数据结构之bfs与双端队列

    目录 一.bfs 二.双端队列 三.算法题 1.kotori和迷宫 2.小红找红点 3.小红玩数组 一.bfs bfs(广度优先搜索),类似二叉树的层序遍历,利用队列完成.一般用于求最短路. 图的最短路问题: 给定一个无向图,每条边的长度都是1.求1号点到x号点的最短距离. 顶点数n 边数为m q次询问 输入x 输出1到x的最短距离. 若1号点到x不连通,则输出-1 二.双端队列 双端队列的应用(区间翻转): 对于长度为n的数组,给定一个长度为m的区间,区间初始位置为a[1]到a[m]. 3种操

  • 详解vue3.0 diff算法的使用(超详细)

    前言:随之vue3.0beta版本的发布,vue3.0正式版本相信不久就会与我们相遇.尤玉溪在直播中也说了vue3.0的新特性typescript强烈支持,proxy响应式原理,重新虚拟dom,优化diff算法性能提升等等.小编在这里仔细研究了vue3.0beta版本diff算法的源码,并希望把其中的细节和奥妙和大家一起分享. 首先我们来思考一些大中厂面试中,很容易问到的问题: 1 什么时候用到diff算法,diff算法作用域在哪里? 2 diff算法是怎么运作的,到底有什么作用? 3 在v-f

随机推荐