数据结构和算法学习记录——层序遍历(层次遍历)、二叉树遍历的应用(输出二叉树中的叶节点、求二叉树的高度、二元运算表达式树及其遍历、由两种遍历序列确定二叉树)

简介: 数据结构和算法学习记录——层序遍历(层次遍历)、二叉树遍历的应用(输出二叉树中的叶节点、求二叉树的高度、二元运算表达式树及其遍历、由两种遍历序列确定二叉树)

层序遍历

层序遍历可以通过一个队列来实现,其基本过程为:

先根节点入队,然后:

  1. 从队列中取出一个元素;
  2. 访问该元素所指的节点;
  3. 若该元素所指节点的左、右孩子节点非空, 则将其左、右孩子的指针顺序入队。
  4. 循环123的步骤,直到队列为空。

思路图解

代码实现

void LevelOrderTraversal(BinTree BT)
{
  Queue Q;
  BinTree T;
  if (!BT)
  {
    return; //若为空树则直接返回
  }
  Q = CreateQueue(); //创建并初始化队列Q
  Add(Q, BT);
  while (!IsEmptyQ(Q))
  {
    T = DeleteQ(Q);
    printf("%d\n", T->data);  //访问取出来的节点
    //若该元素的左右孩子节点不为空,则依次入队
    if (T->Left)
    {
      AddQ(Q, T->Left);     
    }
    if (T->Right)
    {
      AddQ(Q, T->Right);
    }
  }
}

二叉树遍历的应用

输出二叉树中的叶节点

之前讲过的递归先序遍历二叉树写法很简单,而要输出二叉树中的叶节点,就可以在进行遍历的过程中进行检测,如果为叶节点则输出,否则继续遍历。 叶节点即左孩子节点为空、右孩子节点也为空。

代码实现

void PreOrderPrintLeaves(BinTree BT)
{
  if (BT)
  {
    if (!BT->Left && !BT->Right)
      printf("%d ", BT->data);
    PreOrderPrintLeaves(BT->Left);
    PreOrderPrintLeaves(BT->Right);
  }
}

求二叉树的高度

树是递归定义的,一颗二叉树的高度应该等于左右两颗子树的最大高度+1 求二叉树的高度,利用的是后序遍历的一种程序框架来实现的。

思路图解

代码实现

int PostOrderGetHeight(BinTree BT)
{
  int HL, HR, MaxH;
  if (BT)
  {
    HL = PostOrderGetHeight(BT->Left);   //求左子树的高度
    HR = PostOrderGetHeight(BT->Right);  //求右子树的高度
    MaxH = (HL > HR) ? HL : HR;          //取左右子树的最大高度
    return (MaxH + 1);                   //返回树的高度
  }
  else
  {
    return 0;                            //空树的高度为0
  }
}

二元运算表达式树及其遍历

对上面的表达式树进行三种遍历,可以得到三种不同的访问结果:

试着分别写出上面表达式树前序中序和后序遍历的不同表达式,复习一遍之前讲的树的遍历。



先序遍历可以得到前缀表达式:++a*bc*+*defg


中序遍历可以得到中缀表达式:a+b*c+d*e+f*g


后序遍历可以得到后缀表达式:abc*+de*f+g*+


但需要注意的是:中缀表达式会受到运算符优先级的影响,所以单单这样通过中序遍历得出的中缀表达式是不完全准确的。

解决方法是:在输出左子树之前,先输出一个左括号,左子树结束的时候再输出一个右括号。

由两种遍历序列确定二叉树

已知三种遍历中的任意两种遍历序列,能否唯一确定一颗二叉树呢?

答案是:两种遍历序列中,必须要有一种是中序遍历才能够唯一确定一颗二叉树

假设没有中序,看下面两个序列:

先序遍历序列:A B

后序遍历序列:B A

像这样一组简单的序列,只有先序遍历序列和后序遍历序列的情况下,就有两颗是符合的二叉树,其中根节点是容易确定的,先序的第一个节点就是根,后序的最后一个节点就是根;但是左右节点是不好区分的,所以就导致了只有先序序列和后序序列的情况下没法唯一地确认一颗二叉树。


下面就来看看,已知先序序列和中序序列,怎么样来确定一颗二叉树。

思路:

  1. 根据先序遍历序列第一个节点确定根节点;
  2. 根据根节点在中序遍历序列中分割出左右两个子序列;
  3. 对左子树和右子树分别递归使用相同的方法继续分解。


举个例子清晰一下思路:

先序序列: abcdefghij

中序序列: cbedahgijf

所以最终通过先序遍历序列和中序遍历序列唯一确定的二叉树就为:


end



目录
相关文章
|
15天前
|
机器学习/深度学习 存储 算法
【数据结构】算法的复杂度
算法的时间复杂度和空间复杂度
23 1
【数据结构】算法的复杂度
|
8天前
|
存储 算法 Python
“解锁Python高级数据结构新姿势:图的表示与遍历,让你的算法思维跃升新高度
【7月更文挑战第13天】Python中的图数据结构用于表示复杂关系,通过节点和边连接。常见的表示方法是邻接矩阵(适合稠密图)和邻接表(适合稀疏图)。图遍历包括DFS(深度优先搜索)和BFS(广度优先搜索):DFS深入探索分支,BFS逐层访问邻居。掌握这些技巧对优化算法和解决实际问题至关重要。**
11 1
|
15天前
|
算法 JavaScript
JS 【详解】树的遍历(含深度优先遍历和广度优先遍历的算法实现)
JS 【详解】树的遍历(含深度优先遍历和广度优先遍历的算法实现)
13 0
JS 【详解】树的遍历(含深度优先遍历和广度优先遍历的算法实现)
|
13天前
|
算法 安全 调度
逆天改命!Python高级数据结构堆(Heap)与优先队列,让你的算法效率飙升至宇宙级!
【7月更文挑战第8天】Python的heapq模块和queue.PriorityQueue实现了堆和优先队列,提供高效算法解决方案。堆用于Dijkstra算法求解最短路径,例如在图论问题中;PriorityQueue则在多线程下载管理中确保高优先级任务优先执行。这两个数据结构提升效率,简化代码,是编程中的强大工具。
13 0
|
13天前
|
算法 搜索推荐 Java
在Java中实现高效的算法与数据结构
在Java中实现高效的算法与数据结构
|
15天前
|
算法 JavaScript
JS 【详解】二叉树(含二叉树的前、中、后序遍历技巧和算法实现)
JS 【详解】二叉树(含二叉树的前、中、后序遍历技巧和算法实现)
18 0
|
3天前
|
传感器 算法
基于无线传感器网络的MCKP-MMF算法matlab仿真
MCKP-MMF算法是一种启发式流量估计方法,用于寻找无线传感器网络的局部最优解。它从最小配置开始,逐步优化部分解,调整访问点的状态。算法处理访问点的动态影响半径,根据带宽需求调整,以避免拥塞。在MATLAB 2022a中进行了仿真,显示了访问点半径请求变化和代价函数随时间的演变。算法分两阶段:慢启动阶段识别瓶颈并重设半径,随后进入周期性调整阶段,追求最大最小公平性。
基于无线传感器网络的MCKP-MMF算法matlab仿真
|
5天前
|
机器学习/深度学习 算法 数据挖掘
基于改进K-means的网络数据聚类算法matlab仿真
**摘要:** K-means聚类算法分析,利用MATLAB2022a进行实现。算法基于最小化误差平方和,优点在于简单快速,适合大数据集,但易受初始值影响。文中探讨了该依赖性并通过实验展示了随机初始值对结果的敏感性。针对传统算法的局限,提出改进版解决孤点影响和K值选择问题。代码中遍历不同K值,计算距离代价,寻找最优聚类数。最终应用改进后的K-means进行聚类分析。
|
7天前
|
算法 数据安全/隐私保护
基于GA遗传优化算法的Okumura-Hata信道参数估计算法matlab仿真
在MATLAB 2022a中应用遗传算法进行无线通信优化,无水印仿真展示了算法性能。遗传算法源于Holland的理论,用于全局优化,常见于参数估计,如Okumura-Hata模型的传播损耗参数。该模型适用于150 MHz至1500 MHz的频段。算法流程包括选择、交叉、变异等步骤。MATLAB代码执行迭代,计算目标值,更新种群,并计算均方根误差(RMSE)以评估拟合质量。最终结果比较了优化前后的RMSE并显示了SNR估计值。
21 7
|
4天前
|
算法
基于粒子群优化的图像融合算法matlab仿真
这是一个基于粒子群优化(PSO)的图像融合算法,旨在将彩色模糊图像与清晰灰度图像融合成彩色清晰图像。在MATLAB2022a中测试,算法通过PSO求解最优融合权值参数,经过多次迭代更新粒子速度和位置,以优化融合效果。核心代码展示了PSO的迭代过程及融合策略。最终,使用加权平均法融合图像,其中权重由PSO计算得出。该算法体现了PSO在图像融合领域的高效性和融合质量。

热门文章

最新文章