精华内容
下载资源
问答
  • 如何计算完全二叉树的深度

    万次阅读 2017-09-22 19:46:52
    如何计算完全二叉树的深度一棵有12个节点的完全二叉树,其深度是()一棵有12个节点的完全二叉树,其深度是() 4 5 3 6 在此之前我想说一下三种二叉树 Full Binary Tree Perfect Binary Tree Complete Binary Tree ...

    如何计算完全二叉树的深度

    一棵有12个节点的完全二叉树,其深度是()一棵有12个节点的完全二叉树,其深度是()

    • 4
    • 5
    • 3
    • 6

    在此之前我想说一下三种二叉树

    1. Full Binary Tree
    2. Perfect Binary Tree
    3. Complete Binary Tree

    为什么要说到这个问题,是因为在翻译的时候有个坑,特地想拿出来给大家说一下,Full Binary Tree翻译过来应该是满二叉树, 但是国内的满二叉树指的却是 Perfect Binary Tree。

    正文

    本篇博文旨在说明怎样计算完全二叉树的深度。

    证明:
    ​ 设该完全二叉树的深度为k,结点个数为12,根据完全二叉树的定义可知,前k-1层的结点个数为 2^(k-1) - 1个,由此可得

    12 > 2^(k-1)-1

    假设该完全二叉树恰好是一颗满二叉树(Perfect Binary Tree),则该树的结点个数为2^k - 1,由此可得

    2^k - 1 > 12 > 2^(k-1) - 1
    2^k > 13 > 2^(k-1)
    ∴ log2 13 < k < (og2 13) + 13 < k < 5

    因为k 只能为int ,所以取4

    答案选A

    由此可得完全二叉树的深度为log2 n ,其中n 为结点个数,取得下界

    展开全文
  • 完全二叉树的深度

    2020-09-17 19:32:17
    一个有nnn个节点的完全二叉树的深度kkk如何计算?以下是计算步骤。 当树深k=1k=1k=1时,n=1n=1n=1 当树深k=2k=2k=2时,n=3n=3n=3 当树深k=3k=3k=3时,n=7n=7n=7 所以节点个树n和树深k的关系为:2k−1=n2^k-1=n2k−1...

    一个有nn个节点的完全二叉树的深度kk如何计算?以下是计算步骤。

    1. 当树深k=1k=1时,n=1n=1
    2. 当树深k=2k=2时,n=3n=3
    3. 当树深k=3k=3时,n=7n=7
    4. 所以节点个树n和树深k的关系为:2k1=n2^k-1=n
    5. 所以树深:k=log2(n+1)k=log_2(n+1)
    展开全文
  • 物理2、深度为k的完全二叉树所含叶结点个数最多为( B)。A)2k B) 2k-1 C)k D) 2k3、如果对线性表操作只有两种,即删除第一个元素,在最后一个元素后面插入新元素,则最好使用 B 。A.只有表头指针没有表尾指针...

    1、在数据结构中,与所使用的计算机无关的是数据的 A 结构。

    A.逻辑 B.存储 C.逻辑和存储 D.物理

    2、深度为k的完全二叉树所含叶结点的个数最多为( B)。

    A)2k B) 2k-1 C)k D) 2k

    3、如果对线性表的操作只有两种,即删除第一个元素,在最后一个元素的后面插入新元素,则最好使用 B 。

    A.只有表头指针没有表尾指针的循环单链表

    B.只有表尾指针没有表头指针的循环单链表

    C.非循环双链表

    D.循环双链表

    4、当一个作为实际传递的对象占用的存储空间较大并可能需要修改时,应最好把它说明为( )参数,以节省参数值的传输时间和存储参数的空间。

    A.整形 B.引用型

    C.指针型 D.常值引用型?

    5、以下说法正确的是 D 。

    A.数据项是数据的基本单位

    B.数据元素是数据的最小单位

    C.数据结构是带结构的数据项的集合

    D.一些表面上很不相同的数据可以有相同的逻辑结构

    6、数据结构中,从逻辑上可以把数据结构分成(?)。

    ?A.动态结构和静态结构?B.紧凑结构和非紧凑结构?C.线性结构和非线性结构?D.内部结构和外部结构

    7、有向图采用邻接矩阵存储,某一行中非零元素的个数等于

    A.对应顶点v的度

    B.对应顶点v的出度

    C.对应顶点v的入度

    D.依附于对应顶点v的边数

    8、对于图1所示的二叉树,其后序序列为(C )。

    A)ABDECFG B)DBEAFCG

    C)DEBFGCA D)GFCEBDA

    9、已知关键字序列为{66,82,25,51,98,108},利用快速排序方法,以第一个元素为基准得到的一趟排序结果为

    A.{25,51,66,82,98,108}

    B.{25,51,66,98,82,108}

    C.{51,25,66,108,98,82}

    D.{51,25,66,82,98,108}

    10、下列关于哈夫曼树的叙述中,错误的是

    A.用n个结点构造的哈夫曼树是唯一的

    B.哈夫曼树中只有度为0或度为2的结点

    C.树中两个权值最小的结点可能是兄弟结点

    D.同一结点集构造的二叉树中,哈夫曼树的WPL最小

    11、从一棵二叉搜索树中查找一个元素时,其时间复杂度大致为( )。

    A.O(1) B.O(n)

    C.O(1Ogzn) D.O(n2)

    12、通常要求同一逻辑结构中的所有数据元素具有相同的特性,这意味着 B 。

    A.数据元素具有同一特点

    B.不仅数据元素所包含的数据项的个数要相同,而且对应的数据项的类型要一致

    C.每个数据元素都一样

    D.数据元素所包含的数据项的个数要相等

    13、广义表A=(x,((y),((a)),A))的深度是

    A.2 B.3 C.4 D.∞

    14、数据结构在计算机内存中的表示是指 A 。

    A.数据的存储结构 B.数据结构 C.数据的逻辑结构 D

    展开全文
  • 第五章 树与二叉树

    2014-11-27 22:18:34
    性质5-4 具有n个结点的完全二叉树的深度为【log2^n】+1。 性质5-5 对一棵具有n个结点的完全二叉树中的结点从一开始按层序编号,则对于任意的编号为i(1)的结点,有: (1)如果i>1,则结点i的双亲的编号为【i/2】;...
  • 性质1:具有n个结点的完全二叉树的深度为[log2n]+1。 性质2:设完全二叉树共有n个结点。如果从根结点开始,按层次(每一层从左到右)用自然数1,2,……,n给结点进行编号,则对于编号为k(k=1,2,……,n)的结点...
  • 递归:如何找到“最终推荐人”?一、递归二、递归需要满足三个条件① 一个问题解可以分解为几个子...\quad递归是一种非常高效、简洁编码技巧,一种应用非常广泛算法,比如DFS深度优先搜索、前中后序二叉树

    一、递归

    \quad递归是一种非常高效、简洁的编码技巧,一种应用非常广泛的算法,比如DFS深度优先搜索、前中后序二叉树遍历等都是使用递归。

    \quad方法或函数调用自身的方式称为递归调用,调用称为递,返回称为归。即:的过程叫“”,回来的过程叫“”。

    \quad基本上,所有的递归问题都可以用递推公式来表示:一排人的位置(通过询问前一个人的位置):

    \quadf(n)=f(n-1)+1 \quad 其中,f(1)=1

    二、递归需要满足的三个条件

    ① 一个问题的解可以分解为几个子问题的解

    \quad何为子问题?子问题就是数据规模更小的问题。比如,电影院的例子,你要知道,“自己在哪一排”的问题,可以分解为“前一排的人在哪一排”这样一个子问题。2. 这个问题与分解之后的子问题,除了数据规模不同,求解思路完全一样。

    ② 这个问题与分解之后的子问题,除了数据规模不同,求解思路完全一样

    \quad“自己在哪一排”的思路,和前面一排人求解“自己在哪一排”的思路,是一模一样的。

    ③ 存在递归终止条件

    \quad把问题分解为子问题,把子问题再分解为子子问题,一层一层分解下去,不能存在无限循环,这就需要有终止条件。还是电影院的例子,第一排的人不需要再继续询问任何人,就知道自己在哪一排,也就是 f(1)=1,这就是递归的终止条件。

    三、为什么使用递归?递归的优缺点?

    1、优点

    \quad代码的表达力很强,写起来简洁。

    2、缺点

    \quad空间复杂度高、有堆栈溢出风险、存在重复计算、过多的函数调用会耗时较多等问题。

    四、如何实现递归?

    1、递归代码编写

    \quad写递归代码的关键就是找到如何将大问题分解为小问题的规律,并且基于此写出递推公式,然后再推敲终止条件,最后将递推公式和终止条件翻译成代码。

    2、迭代循环的非递归

    \quad笼统的讲,所有的递归代码都可以改写为迭代循环的非递归写法。如何做?抽象出递推公式、初始值和边界条件,然后用迭代循环实现。

    五、递归常见问题及解决方案

    1、警惕堆栈溢出

    \quad可以声明一个全局变量来控制递归的深度,从而避免堆栈溢出。

    2、警惕重复计算

    \quad通过某种数据结构来保存已经求解过的值,从而避免重复计算。

    3、死循环

    \quad数据库里存在脏数据,我们还需要处理由此产生的无限递归问题。如果 A 的推荐人是 B,B 的推荐人是 C,C 的推荐人是 A,这样就会发生死循环。

    六、如何找到“最终推荐人”?

    \quadactor_id 表示用户 id,referrer_id 表示推荐人 id。
    在这里插入图片描述

    long findRootReferrerId(long actorId) {
      Long referrerId = select referrer_id from [table] where actor_id = actorId;
      if (referrerId == null) return actorId;
      return findRootReferrerId(referrerId);
    }
    
    展开全文
  • 34、 编写计算整个二叉树高度的算法(二叉树的高度也叫二叉树的深度)。 35、 编写计算二叉树最大宽度的算法(二叉树的最大宽度是指二叉树所有层中结点个数的最大值)。 回溯法 36、 (组合问题)求出从自然数1,2,...
  • 2.1. 二叉树的基本概念 2.2. 排序二叉树 3. 哈希表 27. 本阶段总结 III. Linux系统编程 28. 文件与I/O 1. 汇编程序的Hello world 2. C标准I/O库函数与Unbuffered I/O函数 3. open/close 4. read/write 5. lseek 6. ...
  • 尝试用Python实现一些简单的算法和数据结构 之前的算法和数据结构基本都是用Swift写的,现在尝试用Python实现一些简单的...面试题39:二叉树的深度:利用递归实现。如果一棵树只有一个结点,那么它的深度为1。递归的...
  • 大话数据结构

    2018-12-14 16:02:18
    6.11树、森林与二叉树的转换 195 有个乡镇企业也买了同样的生产线,老板发现这个问题后找了个小工来说:你必须搞定,不然炒你鱿鱼。小工很快想出了办法:他在生产线旁边放了台风扇猛吹,空皂盒自然会被吹走。 ...
  • 15.1.3 满二叉树、完全二叉树和平衡二叉树 421 15.1.4 二叉树的最大和最小高度 422 15.2 ADT二叉树 425 15.2.1 二叉树的遍历 425 15.2.2 二叉树的操作 428 15.2.3 ADT二叉树的模板接口 430 15.3 ADT二叉查找...
  • 算法笔记 胡凡 曾磊

    2018-10-16 17:38:13
    提高篇(3)——数据结构专题(2) 283 9.1 树与二叉树 283 9.1.1 树的定义与性质 283 9.1.2 二叉树的递归定义 284 9.1.3 二叉树的存储结构与基本操作 285 9.2 二叉树的遍历 289 9.2.1 先序遍历 289 9.2.2 中序遍历 ...
  • 9.1.3 二叉树的存储结构与基本操作 285 9.2 二叉树的遍历 289 9.2.1 先序遍历 289 9.2.2 中序遍历 290 9.2.3 后序遍历 291 9.2.4 层序遍历 292 9.2.5 二叉树的静态实现 298 9.3 树的遍历 302 9.3.1 树的静态写法 302...
  • 8.2.2 计算完全数算法 8.3 亲密数 8.3.1 什么是亲密数 8.3.2 计算亲密数算法 8.4 水仙花数 8.4.1 什么是水仙花数 8.4.2 计算水仙花数算法 8.5 自守数 8.5.1 什么是自守数 8.5.2 计算自守数算法 8.6 最大公约数 8.6.1...
  • 算法设计与分析基础

    2018-02-12 19:26:04
    8.4.2计算完全最短路径Floyd算法 习题8.4 小结 第9章贪婪技术 9.1Prim算法 习题9.1 9.2Kruskal算法 习题9.2 9.3Diikstra算法 习题9.3 9.4哈夫曼树及编码 习题9.4 小结 第10章迭代改进 10.1单纯形法 10.1.1线性规划...
  • Linux C 编程一站式学习.pdf

    千次下载 热门讨论 2010-11-24 01:27:27
    2.1. 二叉树的基本概念 2.2. 排序二叉树 3. 哈希表 27. 本阶段总结 III. Linux系统编程 28. 文件与I/O 1. 汇编程序的Hello world 2. C标准I/O库函数与Unbuffered I/O函数 3. open/close 4. read/write 5. lseek 6. ...
  • 算法导论(part2)

    2010-09-09 22:54:12
    本书将叙述的严谨性以及内容的深度和广度有机地结合了起来。第1版推出后,即在世界范围内受到了广泛的欢迎,被各高等院校用作多种课程的教材和业界的标准参考资料。它深入浅出地介绍了大量的算法及相关的数据结构,...
  • 算法导论(part1)

    2010-09-09 22:51:05
    本书将叙述的严谨性以及内容的深度和广度有机地结合了起来。第1版推出后,即在世界范围内受到了广泛的欢迎,被各高等院校用作多种课程的教材和业界的标准参考资料。它深入浅出地介绍了大量的算法及相关的数据结构,...
  • 算法导论(原书第三版)

    热门讨论 2013-03-06 14:31:34
    第1章 算法在计算作用 1.1 算法 1.2 作为一种技术算法 思考题 本章注记 第2章 算法基础 2.1 插入排序 2.2 分析算法 2.3 设计算法 2.3.1 分治法 2.3.2 分析分治算法 思考题 本章注记 第3章 函数...
  • 算法能力极限10.1 如何求下界习题10.110.2 决策树习题10.210.3 P、NP和NP完全问题习题10.310.4 数值算法挑战习题10.4小结第11章 超越算法能力极限11.1 回溯习题11.111.2 分支界限习题11.211.3 NP困难问题...
  • 算法导论中文版

    2016-10-26 10:13:58
    第1章 算法在计算作用  1.1 算法  1.2 作为一种技术算法  思考题  本章注记 第2章 算法基础  2.1 插入排序  2.2 分析算法  2.3 设计算法  2.3.1 分治法  2.3.2 分析分治算法  思考题  本...
  • 其二、技术层次深:如果期望进入IT服务或者产品公司(类似毕博、DELL、IBM等),Oracle技术能够帮助提高就业的深度。 其三、职业方向多:Oracle数据库管理方向、Oracle开发及系统架构方向、Oracle数据建模数据仓库等...
  • </li><li>限制调用最大深度</li><li>警惕重复计算</li></ul> 编码流程 <ul><li>terminator</li><li>process current logic</li><li>drill down</li><li>restore current status</li></ul> 二叉树遍历递推公式 <ul>...

空空如也

空空如也

1 2
收藏数 26
精华内容 10
关键字:

如何计算完全二叉树的深度