当前位置: 首页 > article >正文

树和二叉树知识点大全及相关题目练习【数据结构】

树和二叉树

要注意树和二叉树是两个完全不同的结构、概念,它们之间不存在包含之类的关系
在这里插入图片描述

树的定义

树(Tree)是n(n≥0)个结点的有限集,它或为空树(n = 0);或为非空树,对于非空树T:
(1)有且仅有一个称之为根的结点;
(2)除根结点以外的其余结点可分为m(m>0)个互不相交的有限集T1, T2, …, Tm, 其中每一个集合本身又是一棵树,并且称为根的子树(SubTree)。
显然,树的定义是一个递归的定义

树的基本术语

根:即根结点(没有前驱)
叶子:即终端结点(没有后继)
森林:指m棵不相交的树的集合(例如删除A后的子树个数)
有序树:结点各子树从左至右有序,不能互换(左为第一)
无序树:结点各子树可互换位置
双亲:即上层的那个结点(直接前驱)
孩子: 即下层结点的子树的根(直接后继)
兄弟:同一双亲下的同层结点(孩子之间互称兄弟)
堂兄弟:即双亲位于同一层的结点(但并非同一双亲)
祖先:即从根到该结点所经分支的所有结点
子孙:即该结点下层子树中的任一结点
结点:即树的数据元素
结点的度:结点挂接的子树数
结点的层次:从根到该结点的层数(根结点算第一层)
终端结点:即度为0的结点,即叶子
分支结点:即度不为0的结点(也称为内部结点)
树的度:所有结点度中的最大值
树的深度(或高度):指所有结点中最大的层数

二叉树的定义

二叉树(Binary Tree)是n(n≥0)个结点所构成的集合,它或为空树(n = 0);或为非空树,对于非空树T:
(1)有且仅有一个称之为根的结点;
(2)除根结点以外的其余结点分为两个互不相交的子集T1和T2,分别称为T的左子树和右子树,且T1和T2本身又都是二叉树。
所有树都可以转为唯一对应的二叉树,不失一般性,任何树都可以与二叉树相互转换。
二叉树不是树的特殊情况,它们是两个概念

二叉树的特点

1、每个结点最多有两孩子(二叉树中不存在度大于2的结点)
2、子树有左右之分,其次序不能颠倒
3、二叉树可以是空集合,根可以有空的左子树或空的右子树
二叉树的五种基本形态:
在这里插入图片描述
(虽然二叉树与树概念不同,但有关树的基本术语对二叉树都适用)

二叉树的性质

性质一
在这里插入图片描述
第i层上至少有1个结点
性质二
在这里插入图片描述
深度为k时至少有k个结点

性质三
以n(0)表示度为0的结点的个数,以n(1)表示度为1的结点的个数,以n(2)表示度为2的结点个数
n(0)=n(2)+1
推导:
设一棵二叉树总结点个数为n,则从下往上看,每一个结点都有一条边和它的双亲结点相连(有且只有一条),头结点除外,因为他没有双亲结点,则这棵二叉树总共有n-1条边
又因为度为2的结点n(2)会生出两条边,度为1的结点n(1)会生出一条边,度为0的结点没有边,因此n-1=2* n(2)+1* n(1)
又因为总结点个数n=度为二的结点个数n(2)+度为一的结点个数n(1)+度为零的结点个数n(0)
n=n(2)+n(1)+n(0)
n-1=2 * n(2)+1 * n(1)
合并整理得n(0)=n(2)+1
在这里插入图片描述

两种特殊形式的二叉树

在这里插入图片描述
在这里插入图片描述
满二叉树在同样深度的二叉树中结点个数最多
满二叉树在同样深度的二叉树中叶子结点个数最多

在这里插入图片描述
在这里插入图片描述
在满二叉树中,从最后一个结点开始,连续去掉任意个结点,即是一颗完全二叉树
满二叉树一定是完全二叉树
完全二叉树不一定是满二叉树

相关题目练习

  1. (判断题)二叉树中每个结点的度不能超过2,所以二叉树是一种特殊的树。
    A. 对
    B. 错
    正确答案: 错
    二叉树和树完全是两个概念,两个东西,二叉树不是树的特例
  2. (判断题)哈夫曼树的总结点个数(多于1时)不能为偶数。
    A. 对
    B. 错
    正确答案: 对
    哈夫曼编码树中没有度为1的结点。若叶子结点的个数为n,则哈夫曼编码树的结点总数为 2n-1,因此总结点个数(多于1时)不能为偶数
  3. (判断题)由二叉树的先序序列和后序序列可以唯一确定一颗二叉树。
    A. 对
    B. 错
    正确答案: 错
    哈夫曼树一定是完全二叉树。
    A. 对
    B. 错
    正确答案: 错
  4. (判断题)满二叉树一定是完全二叉树,完全二叉树不一定是满二叉树。
    A. 对
    B. 错
    正确答案: 对
  5. (判断题)设一棵树T可以转化成二叉树BT,则二叉树BT中一定没有右子树。
    A. 对
    B. 错
    正确答案: 对
  6. (判断题)哈夫曼树中没有度数为1的结点。
    A. 对
    B. 错
    正确答案: 对
  7. (判断题)先序遍历一棵二叉排序树得到的结点序列不一定是有序的序列。
    A. 对
    B. 错
    正确答案: 对
  8. (判断题)中序遍历二叉排序树可以得到一个有序的序列。
    A. 对
    B. 错
    正确答案: 对
  9. (选择题)具有60个结点的二叉树,其叶子结点有12个,则度为1的结点数为( )。
    A. 11
    B. 13
    C. 48
    D. 37
    正确答案: D:37
  10. (选择题)Huffman树的带权路径长度WPL等于( )。
    A. 除根结点之外的所有结点权值之和
    B. 所有结点权值之和
    C. 各叶子结点的带权路径长度之和
    D. 根结点的值
    正确答案: C:各叶子结点的带权路径长度之和
  11. (选择题)在一棵二叉树上第4层的结点数最多为( )。
    A. 2
    B. 4
    C. 6
    D. 8
    正确答案: D
  12. (选择题)用顺序存储的方法将完全二叉树中的所有结点逐层存放在数组中R[1…n],结点R[i]若有左孩子,其左孩子的编号为结点( )。
    A. R[2i+1]
    B. R[2i]
    C. R[i/2]
    D. R[2i-1]
    正确答案: B
  13. (选择题)由权值分别为3,8,6,2,5的叶子结点生成一棵哈夫曼树,它的带权路径长度为( )。
    A. 24
    B. 48
    C. 72
    D. 53
    正确答案: D:53
  14. (选择题)如果F是由有序树T转换而来的二叉树,那么T中结点的前序就是F中结点的( )。
    A. 中序
    B. 前序
    C. 后序
    D. 层次序
    正确答案: B:前序
  15. (选择题)欲实现任意二叉树的后序遍历的非递归算法而不必使用栈,最佳方案是二叉树采用( )存储结构。
    A. 三叉链表
    B. 广义表
    C. 二叉链表
    D. 顺序
    正确答案: A
  16. (选择题)任何一棵二叉树的叶子结点在先序、中序和后序遍历序列中的相对次序( )。
    A. 不发生改变
    B. 发生改变
    C. 不能确定
    D. 以上都不对
    正确答案: A
  17. (选择题)根据二叉树的定义可知二叉树共有( )种不同的形态。
    A. 4
    B. 5
    C. 6
    D. 7
    正确答案: B
    在这里插入图片描述
  18. (选择题)设哈夫曼树中的叶子结点总数为m,若用二叉链表作为存储结构,则该哈夫曼树中总共有( )个空指针域。
    A. 2m-1
    B. 2m
    C. 2m+1
    D. 4m
    正确答案: B
  19. (选择题)设某棵二叉树中有2000个结点,则该二叉树的最小高度为( )。
    A. 9
    B. 10
    C. 11
    D. 12
    正确答案: C
  20. (选择题)设一棵m叉树中度数为0的结点数为N0,度数为1的结点数为Nl,……,度数为m的结点数为Nm,则N0=( )。
    A. Nl+N2+……+Nm
    B. l+N2+2N3+3N4+……+(m-1)Nm
    C. N2+2N3+3N4+……+(m-1)Nm
    D. 2Nl+3N2+……+(m+1)Nm
    正确答案: B
    在这里插入图片描述
    在这里插入图片描述

http://www.kler.cn/a/327064.html

相关文章:

  • NXP Zigbee JN5169 开发环境软件 文档和支持资源打包下载
  • 十月末
  • IO流篇(一、File)
  • 苍穹外卖Bug集合
  • ComfyUI和Photoshop相结合,PS内实现:文生图,图生图,高清放大,局部重绘,面部修复,设计师福音
  • C#:强大而优雅的编程语言
  • golang 获取证书的生效及过期时间
  • 【论文笔记】Flamingo: a Visual Language Model for Few-Shot Learning
  • Redis篇(应用案例 - 附近商户)(持续更新迭代)
  • Pgsql 数据库操作
  • 【运动控制】关于GPIO通用输入口是NPN型数字输入
  • Grafana指标汉化
  • 【测试-BUG篇】软件测试的BUG知识你了解多少呢?
  • 自动驾驶系列—DOW(开门预警):让每一次开门都更安心
  • 水囊在消防灭火工作中的作用
  • 机器人的性能指标
  • C++ | Leetcode C++题解之第448题找到所有数组中消失的数字
  • 使用 pypdf 给 PDF 添加目录书签
  • 如何避免IP污染
  • POST与GET有哪些区别?
  • Xcode手动安装SDK模拟器
  • 【Golang】Go语言中如何面向对象?
  • 【Git】Git在Unity中使用时的问题记录
  • 集师专属知识付费小程序搭建 心理咨询小程序搭建
  • 记录|Modbus-TCP产品使用记录【摩通传动】
  • c#代码介绍23种设计模式_11外观模式