锐客网

  1. 首页 > 睿知 > >

二叉树遍历复杂度分析,平衡二叉树复杂度

经验分享睿知

二叉查找树复杂度的平均搜索长度和时间如下:假设有一棵二叉排序树，二叉树有两种特殊形式:完整二叉树和完整二叉树 。数据结构基础-二叉树前言遍历从二叉树的根开始，然后到左子树，再到右子树，摘要号为3 (full 二叉树)的二叉排序树和摘要号为7 (full 二叉树)的二叉排序树 。

1、《漫画算法》——【3】树在树的结构中，树的定义如下 。树是n(n>0)个节点的有限集 ， 当n0时，称为空树 。在任何非空树中，都有以下特征:1 。只有一个名为root的特定节点 。2.当n>1时，其余节点可以分成m(m>0)个不相交的有限集 ， 每个集合本身就是一棵树 ， 称为根的子树 。【相关节点】树的最大层次树称为树的高度或深度 。树的每个节点最多有2个子节点 。
【二叉树遍历复杂度分析,平衡二叉树复杂度】
树的每个节点最多有2个子节点 。二叉树的两个子节点，一个叫左子，一个叫右子 。这两个子节点的顺序是固定的 。二叉树有完整二叉树和完整二叉树两种特殊形式 。full二叉树:a二叉树的所有非叶节点都有左右子节点，所有叶节点都连接在同一层 。总之二叉树的每个分支都是满的 。Complete 二叉树:对于有n个节点的a 二叉树，所有节点都按层次顺序从1到n编号 。

2、数据结构基础-- 二叉树序言遍历从二叉树的根开始，然后到左子树 ， 再到右子树 。遍历的结果是:ABDCEF中序列遍历从左子树开始，然后到根，再到右子树 。遍历的结果是:DBAECF后跟遍历从左子树开始，然后到右子树，再到根 。遍历的结果是DBEFCA打印自己，然后遍历左节点，然后遍历右节点 。这里的栈是用来保存二叉树的结构来弥补- 。

第一个堆栈的处理顺序是从上到下和从右到左 。第二叠颠倒顺序后，变成自下而上 ， 从左向右 。每当一个新节点被添加到队列中时，nlast就作为一个新节点被更新 。当当前打印的节点等于last时，执行换行符，last更新到下一行nlast 。比如(用！Split ， 其中# table为空):将序列化后的字符串转换成数组(如通过此处！所以我们需要引入一个变量setleft来确定下次要构建的节点的方向 。

3、 二叉树的最大/最小深度DFS，先按深度搜索遍历 二叉树的每个路径 。如果当前节点不为空，判断左子树和右子树的深度，返回最大子树深度加1(当前节点) 。如果当前节点为空 ， 则返回0 。当所有叶节点追溯到根节点时，可以计算出二叉树的最大深度 。执行时间:48ms内存消耗:14.6 MB time复杂度:O(n)space复杂度:最差的情况下 ， 树是完全不平衡的，比如每个节点只剩下子节点，递归会被调用n次(树的高度)，所以保存调用栈的存储会是O 。

因此，本例中的空格复杂度将为O(log(n)) 。BFS，使用广度优先搜索，对于遍历 二叉树的每一层，如果当前节点是叶节点，那么当前层数就是叶节点的深度 。如果当前叶节点的深度大于最大深度，则更新最大深度 。执行时间:40ms内存消耗:14.2 MB time复杂度:o(n)space复杂度:o(n)如果求最小深度怎么办？DFS就像求最大深度一样，是遍历 二叉树的每一条路径 。

4、二叉搜索树的平均查找长度及时间 复杂度推导过程如下:假设有一棵二叉排序树，点数之和为n ， 高度为h，根节点高度为1，也是满的二叉树 。n和h的关系有公式:n (2 h) 1，即hlog2(n 1) 。对于高度为2，成功搜索的平均长度为:对于高度为3 ， 汇总点数为7的二叉排序树(full 二叉树)，成功搜索的平均长度为:对于高度为h ， 
成功搜索的平均长度为:对于1 * 1 2 * 2 3 * 4 ... h * 2 (h1)在[等式1]中，这个数列有h项:1 * 2 0 ， 2 * 2 1，3 * 2 2 ， ...，h * 2 (h1 。

    推荐阅读


    上一篇：下订单分析类图,软件工程分析类图

    下一篇：计算机数据分析师工资