首页 > 其他分享 >二叉树的遍历

二叉树的遍历

时间:2023-09-15 11:08:12浏览次数:53  
标签:优先 遍历 结点 访问 二叉树 深度 广度


总结深度优先与广度优先的区别
1、区别
1) 二叉树的深度优先遍历的非递归的通用做法是采用栈,广度优先遍历的非递归的通用做法是采用队列。
2) 深度优先遍历:对每一个可能的分支路径深入到不能再深入为止,而且每个结点只能访问一次。要特别注意的是,二叉树的深度优先遍历比较特殊,可以细分为先序遍历、中序遍历、后序遍历。具体说明如下:
先序遍历:对任一子树,先访问根,然后遍历其左子树,最后遍历其右子树。
中序遍历:对任一子树,先遍历其左子树,然后访问根,最后遍历其右子树。
后序遍历:对任一子树,先遍历其左子树,然后遍历其右子树,最后访问根。
广度优先遍历:又叫层次遍历,从上往下对每一层依次访问,在每一层中,从左往右(也可以从右往左)访问结点,访问完一层就进入下一层,直到没有结点可以访问为止。
3)深度优先搜素算法:不全部保留结点,占用空间少;有回溯操作(即有入栈、出栈操作),运行速度慢。
广度优先搜索算法:保留全部结点,占用空间大; 无回溯操作(即无入栈、出栈操作),运行速度快。
通常 深度优先搜索法不全部保留结点,扩展完的结点从数据库中弹出删去,这样,一般在数据库中存储的结点数就是深度值,因此它占用空间较少。
所以,当搜索树的结点较多,用其它方法易产生内存溢出时,深度优先搜索不失为一种有效的求解方法。  
广度优先搜索算法,一般需存储产生的所有结点,占用的存储空间要比深度优先搜索大得多,因此,程序设计中,必须考虑溢出和节省内存空间的问题。

但广度优先搜索法一般无回溯操作,即入栈和出栈的操作,所以运行速度比深度优先搜索要快些

树的遍历

二叉树的遍历_深度优先搜索


标签:优先,遍历,结点,访问,二叉树,深度,广度
From: https://blog.51cto.com/u_1481758/7479128

相关文章

  • Java数组遍历
    publicclassbianli{publicstaticvoidmain(String[]args){int[]arr={11,22,33,44,55};printArray(arr);}publicstaticvoidprintArray(int[]arr){System.out.print("[");......
  • print()不带逗号、括号输出列表内容(不使用遍历)
    假设有一个列表li=[1,4,6,7,2,5]1、直接输出列表print(li)[1,4,6,7,2,5]2、增加*可以不带逗号、括号输出列表元素print(*li)1467253、还可以使用sep参数自定义每个元素之间的间隔符print(*li,sep='#')1#4#6#7#2#5 ......
  • 遍历输入框时出现输入一个字符立刻失焦,无法正常输入
    原因:循环时绑定输入框值为key,双向绑定时改变输入框值,key值被修改则失焦。解决:动态值不要作为key值 ......
  • 洛谷OJ [P5018 对称二叉树] (深度优先搜索、二叉树、思维)
    P5018[NOIP2018普及组]对称二叉树题意:给定一棵树,树上的每个结点有一个权值,问你这棵树的子树中节点数最多的对称二叉树的节点数是多少?对称二叉树的定义如下:对于树中的每一个结点,要么没有子节点,要么既有左儿子,又有右节点,且对称位置的结点点权相等。输入格式:第一行......
  • c++ 实现 二叉树的 先序遍历,中序遍历 ,后序遍历
    遍历二叉树跟数组不同,树是一种非线性的数据结构,是由n(n>=0)个节点组成的有限集合。如果n==0,树为空树。如果n>0,树有一个特定的节点,叫做根节点(root)。 对于树这种数据结构,使用最频繁的是二叉树。每个节点最多只有2个子节点的树,叫做二叉树。二叉树中,每个节点的子节点作为根的两个子......
  • 洛谷[P1305 新二叉树] Tag:二叉树、基础数据结构
    P1305新二叉树题目描述:输入一串二叉树,输出其前序遍历。输入格式:第一行为二叉树的节点数$n(1\len\le26)$,后面\(n\)行,每一个字母为节点,后两个字母分别为其左右儿子。特别地,数据保证第一行读入的节点必为根节点。空节点用*表示输出格式:二叉树的前序遍历。思路:对......
  • leetcode 二叉树的最大深度
    给定一个二叉树root,返回其最大深度。二叉树的最大深度是指从根节点到最远叶子节点的最长路径上的节点数。示例1:输入:root=[3,9,20,null,null,15,7]输出:3示例2:输入:root=[1,null,2]输出:2解题思路这里可以转化思路为计算当前节点左子树的深度和右子树的深度......
  • 平衡二叉树(Balanced Binary Tree)
    平衡二叉树(BalancedBinaryTree)平衡二叉树是一种特殊的二叉搜索树,它具有以下特点:每个节点的左子树和右子树的高度差不超过1。所有的子树也都是平衡二叉树。通过保持平衡性,平衡二叉树可以在最坏情况下仍然具有较好的性能,保证查找、插入和删除操作的时间复杂度为O(logn)。......
  • leetcode450删除搜索二叉树的节点
    删除的二叉树节点分4种情况:叶子节点,直接删除就行左节点不为空,右节点为空;直接将左子树返回左节点为空,右节点不为空;直接将右子树返回左节点和右节点不为空;将右子树最小的节点作为根节点,返回右子树TreeNode*deleteNode(TreeNode*root,intkey){if(!root)returnn......
  • 二叉树 遍历 hdu-1710-Binary Tree Traversals
    给出二叉树的前序遍历和中序遍历,求后序遍历。。 算法:由前序遍历的第一个元素可确定左、右子树的根节点,参照中序遍历又可进一步确定子树的左、右子树元素。如此递归地参照两个遍历序列,最终构造出二叉树。 由前序和中序结果求后序遍历结果树的遍历: 给你一棵树的先......