专栏首页用户6093955的专栏数据结构期末复习——树与二叉树一些知识点

数据结构期末复习——树与二叉树一些知识点

  1. 满二叉树:一棵深度为k 且有
({2^k - 1 })

个结点的二叉树。(特点:每层都“充满”了结点)

  1. 完全二叉树:深度为k 的,有n个结点的二叉树,当且仅当其每一个结点都与深度为k 的满二叉树中编号从1至n的结点一一对应.
  2. 具有n个结点的完全二叉树的深度为log2(n)向下取整 + 1.
  3. 满二叉树和完全二叉树的区别:满二叉树是叶子一个也不少的树,而完全二叉树虽然前n-1层是满的,但最底层却允许在右边缺少连续若干个结点。满二叉树是完全二叉树的一个特例.
  4. 完全二叉树中度数为1的结点的个数为0或者为1。
  5. 在非空二叉树中,第i层的结点总数不超过
({2^{i-1}})

, i>=1.

  1. 深度为h的二叉树最多有
({2^h -1})

个结点(h>=1),最少有h个结点.

  1. 对于任意一棵二叉树,如果其叶结点数为N0,而度数为2的结点总数为N2,则N0=N2+1;
  2. 问题:具有1102个结点的完全二叉树的一定有___个叶子结点。 分析: 边数m=n-1,那么m = n1 + 2×n2; 而在完全二叉树中度数为1的点只有1个或0个,所以代入0或1,当n2为整数时得出n2的值, 再利用n0=n2+1可得叶子结点的个数。
  3. 由二叉树的前序序列和中序序列,或由其后序序列和中序序列均能唯一地确定一棵二叉树,但由前序序列和后序序列却不一定能唯一地确定一棵二叉树。 关于根据先序序列和中序序列确定二叉树,由中序序列和后序遍历确立一棵二叉树的方法见链接1链接2
  4. 一棵有n个叶子结点Huffman树2n-1个结点.
  5. 森林结点数,边数与树个数的关系

关于哈夫曼编码有这么几道题注意下:

  1. 设一段文本中包含字符{a, b, c, d, e},其出现频率相应为{3, 2, 5, 1, 1}。则经过哈夫曼编码后,文本所占字节数为: (2分) A.40 B.36 C.25 D.12 思路:这道题目其实问的就是哈夫曼树的带权路径长度是多少。
  2. 设一段文本中包含4个对象{a,b,c,d},其出现次数相应为{4,2,5,1},则该段文本的哈夫曼编码比采用等长方式的编码节省了多少位数? (2分) A.0 B.2 C.4 D.5 思路: 关于采用等长方式的编码需要多少位,可以这样想: 在等长编码中,每个对象就用两位数表示,我们可以定义a:01 b:11 c:10 d:00 按照等长编码的文本长度为2×12=24 按照哈夫曼编码文本长度为4×2+2×3+5×1+1×3=22 故节省2位。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 【完全二叉树的有关规律】-(-待补充)

    先介绍一下完全二叉树的概念:若设二叉树的深度为h,除第 h 层外,其它各层 (1~h-1) 的结点数都达到最大个数,第 h 层所有的结点都连续集中在最左边,这就...

    _DIY
  • sendRedirect()和forward()方法的区别

    虽然二者都可以实现获取相应的url资源,但首先要注意的是,重定向由sendRedirect来实现,请求转发由forward来实现。

    _DIY
  • 【 BowWow and the Timetable CodeForces - 1204A 】【思维】

    题目链接 可以发现 十进制4 对应 二进制100 十进制16 对应 二进制10000 十进制64 对应 二进制1000000 可以发现每多两个零,4的...

    _DIY
  • 剑指Offer的学习笔记(C#篇)-- 平衡二叉树(二叉树后序遍历递归详解版)

    首先要理解一个概念:什么是平衡二叉树,如果某二叉树中任意的左右子树深度相差不超过1,那么他就是一颗平衡二叉树。如下图:

    WeiMLing
  • 快应用标准大会如期举行,只不过 9 大厂商变成了 10 大……

    知晓君
  • 数据结构严书习题6.65已知前中序,求二叉链表

    已知一棵二叉树的前序序列和中序序列分别存于两个一维数组中,试编写算法建立该二叉树的二叉链表。

    glm233
  • 算法基础--堆排序

    为了理解很多都使用了递归,而不是自己通过while进行压栈处理。 代码的初衷是便于理解,网上大神优化过的代码很多,也不建议在项目中copy本文代码。

    刀刀老高
  • 最全BAT算法面试100题:阿里、百度、腾讯、京东、美团、今日头条

    在二叉树结点结构中加一个指针域,使其指向层次遍历的下一个结点,特别地,每一层的最后一个结点为空。(Code)

    java架构师
  • 每天5分钟用C#学习数据结构(15)二叉树 Part 1

    如上图所示,A点称为根节点,它有两棵子树,分别以B、C为根,而以C为根的子树又可以分成两棵子树。

    Enjoy233
  • 常见的数据结构

    实现线性表的方式一般有两种,一种是使用数组存储线性表的元素,即用一组连续的存储单元依次存储线性表的数据元素。另一种是使用链表存储线性表的元素,即用一组任意的存储...

    分母为零

扫码关注云+社区

领取腾讯云代金券