首页 > 编程语言 >二叉树遍历算法分析

二叉树遍历算法分析

时间:2023-04-15 19:56:08浏览次数:40  
标签:输出 遍历 递归 孩子 算法 二叉树

二叉树遍历算法分析

前/中/后序遍历算法

可以发现这三种遍历算法只有一行代码,也就是输出结点数据域的位置不同

  1. 前序遍历是先输出数据域再递归到左孩子和右孩子
  2. 中序遍历是先递归到左孩子等返回的时候输出数据域再递归到右孩子
  3. 后序遍历是指先递归到左孩子,然后递归到右孩子,最后返回的时候输出数据域

屏幕截图(339)

递归树

很明显这三种算法的遍历顺序是相同的,只是访问到每个根节点时打印该结点的数据域的时机不同

屏幕截图(340)

遍历算法的时空复杂度

1.时间为O(n)

2.空间为O(n)

屏幕截图(341)

标签:输出,遍历,递归,孩子,算法,二叉树
From: https://www.cnblogs.com/harper886/p/17321729.html

相关文章

  • COMS3200 算法解答
    COMS3200Assignment12023S1100totalmarks,25%overallcoursemarkDue:15:0019April20231Preface1.1NotesThisdocumentissubjecttochangeforthepurposesofclarification.Changesmadesincetheoriginalreleasewillbehighlightedinred.Please......
  • 归并排序算法
    一、归并排序分治思想。  求解一个比较复杂的问题时我们通常都会把复杂的问题分解为几个简单的步骤逐一解决后对所形成的解进行处理得到最终解。分治排序算法就是利用这个思想。把一个给定数组进行拆分成最小的有顺序的单元,然后对最小单元进行排序组合成新数组的过程。二、归......
  • 数据结构-->二叉树_02
    今天,接着上一期的博文,继续推进!!请看下面的的代码:>求一棵树的高度,为何需要存储起来呢?解答这个问题之前,需要稍微改动一下,上述的代码!会发现上述代码有很大的好处!//二叉树的高度intTreeHight(BTNode*root){ if(root==NULL){ return0;}returnTreeHight(root->l......
  • 二叉树的创建和中序及后序遍历
    二叉树的创建和中序及后序遍历二叉的先序创建使用#号来表示该结点为null实现代码先进行先序创建然后进行先序遍历#include<iostream>#include<algorithm>#include<cstdio>#include<cstring>#include<vector>#include<cstring>#include<unordered_set>#includ......
  • 排序算法-插入排序
    排序算法-插入排序1.直接插入排序InsertSort1.1InsertSort介绍InsertSort也是一种简单的内部排序算法,其是对待排序的元素以插入的方式寻找该元素的适当位置,以达到排序的目的,是一种稳定的排序算法。InserSort的基本思想是:将待排序序列看作一个有序表和一个无序表,初始时......
  • 【故障诊断】基于KNN、SVM、RF、DT、ET多种算法实现制冷系统故障诊断附Matlab代码
    ✅作者简介:热爱科研的Matlab仿真开发者,修心和技术同步精进,matlab项目合作可私信。......
  • 【锂电池健康状态预测】基于布谷鸟算法优化BP神经网络实现锂电池健康状态预测附含Matl
    ✅作者简介:热爱科研的Matlab仿真开发者,修心和技术同步精进,matlab项目合作可私信。......
  • 【数据结构】二叉树的基本操作与遍历(C语言)
     目录定义满二叉树 完全二叉树性质应用计算二叉树结点个数 计算叶子结点的个数第 k层结点的个数查找值为x的节点遍历前序遍历中序遍历后序遍历层序遍历判断是否为完全二叉树定义......
  • 算法-并查集-200
    publicclassSolution{publicintNumIslands(char[][]grid){if(grid==null||grid.Count()==0)return0;introwCount=grid.Count();intcolCount=grid[0].Count();intwaters=0;UnionFinduf=newUnionFind(grid);for......
  • 关于js对象遍历保证顺序的问题
    Object.keys(obj).sort().forEach(...),注:仅用于对象的key值是可定义顺序的,如key值为时间错,数字等,通过sort(),可默认按照数组大小排序(也可通过sort的自定义函数排序)object.keys/values()和forin不能保证对象传成数组或遍历的顺序友情链接1友情链接2......