数据结构-----树的易错点

这篇具有很好参考价值的文章主要介绍了数据结构-----树的易错点。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

1.树的度和m叉树

•度为m的树(度表示该结点有多少个孩子(分支))

任意结点的度<=m(最多m个孩子)

至少又一个结点度=m(有m个孩子)

一定是非空树,至少有m+1个结点

数据结构-----树的易错点,数据结构,学习日常(考研向),数据结构,考研,笔记,算法

•m叉树

任意结点的度<=m(最多有m个孩子)

允许所有结点的度都<m

可以是空树

数据结构-----树的易错点,数据结构,学习日常(考研向),数据结构,考研,笔记,算法

2.m叉树第i层至多有个结点或度为m的树第i层至多有个结点

二叉树第i层至多有个结点

数据结构-----树的易错点,数据结构,学习日常(考研向),数据结构,考研,笔记,算法

3.高度为h的m叉树至多个结点

高度为h的二叉树至多有个结点

数据结构-----树的易错点,数据结构,学习日常(考研向),数据结构,考研,笔记,算法

注: 

在这里,树的高度和深度可以看作相同的概念,因为这里侧重于树有几层,但是如果侧重于结点,那么高度和深度的概念就不同了

数据结构-----树的易错点,数据结构,学习日常(考研向),数据结构,考研,笔记,算法

树的深度:(从上往下数)

  • 节点 D、E 和 F 的深度都为 2,因为从根节点 A 到节点 D ,E,F需要经过 2 条边。

树的高度:(从下往上数)

  • 节点 D、E 和 F 的高度都为 1,因为它们都到达任意叶子节点的路径长度最短,只需要经过 1 条边。

总的来说:

  • 树的深度是指从根节点到某个节点的路径长度。
  • 树的高度是指从某个节点到达任意叶子节点的最长路径长度。

4.高度为h的m叉树至少有h个结点(高度为h,度为m的树至少有h+m-1个结点)

 数据结构-----树的易错点,数据结构,学习日常(考研向),数据结构,考研,笔记,算法

5.具有n个结点的m叉树的最小高度为

最小高度----每一个结点都有m个孩子

数据结构-----树的易错点,数据结构,学习日常(考研向),数据结构,考研,笔记,算法

数据结构-----树的易错点,数据结构,学习日常(考研向),数据结构,考研,笔记,算法

•=数据结构-----树的易错点,数据结构,学习日常(考研向),数据结构,考研,笔记,算法(向上取整)

6.二叉树

(1).设非空二叉树中度为0,1,和2的结点个数分别为n0,n1,n2,则n0=n2+1(叶子节点的个数要比二分支节点的个数多一个)

假设结点总数为n

①n=n0+n1+n2

②n=n1+2n2+1(树的节点数=总度数+1)

(2).满二叉树

高度为h的二叉树,有个结点

数据结构-----树的易错点,数据结构,学习日常(考研向),数据结构,考研,笔记,算法

1.只有最后一层有叶子结点

2.不存在度为1的结点

3.按层序从1开始编号,结点i的左孩子为2i,右孩子为2i+1,结点i的父节点为i/2(向下取整)

6/2=3,7/2(向下取整)=3,所以6,7的父节点为3

(3).完全二叉树

将叶子节点从大到小删去的,都可以称为完全二叉树,例如

数据结构-----树的易错点,数据结构,学习日常(考研向),数据结构,考研,笔记,算法

右下角的图,6号结点在满二叉树中本来应该为7,所以序号变了,不是完全二叉树

得出结论

完全二叉树不一定是满二叉树,满二叉树一定是完全二叉树

①只有最后两层可以有叶子节点

数据结构-----树的易错点,数据结构,学习日常(考研向),数据结构,考研,笔记,算法

②最多只有1个度为1的结点

③按层序从1开始编号,结点i的左孩子为2i,右孩子为2i+1,结点i的父节点为i/2(向下取整)

④如果一个完全二叉树有n个结点,那么(向下取整)为分支节点,(向下取整)为叶子节点

⑤如果某个节点只有1个结点,那么这个结点只可能是左孩子,不会是右孩子

⑥两个结论均正确

•具有n个(n>0)结点的完全二叉树的高度h(深度)为数据结构-----树的易错点,数据结构,学习日常(考研向),数据结构,考研,笔记,算法(向上取整)

推导过程

高为(h)的满二叉树共有个结点

高为(h-1)的满二叉树共有个结点

数据结构-----树的易错点,数据结构,学习日常(考研向),数据结构,考研,笔记,算法

数据结构-----树的易错点,数据结构,学习日常(考研向),数据结构,考研,笔记,算法

•具有n个(n>0)结点的完全二叉树的高度h(深度)为数据结构-----树的易错点,数据结构,学习日常(考研向),数据结构,考研,笔记,算法(向下取整)

高为h的完全二叉树至少个结点

高为h的完全二叉树至少个结点

 数据结构-----树的易错点,数据结构,学习日常(考研向),数据结构,考研,笔记,算法(向下取整)

⑦对于完全二叉树,可以优结点数n,推出度为0,1和2的结点个数为n0,n1和n2

完全二叉树最多只有一个度为1的结点,即

n1=0或1

n0=n2+1--->n0+n1一定为奇数

若完全二叉树有2k个结点,则必有n1=1,n0=k,n2=k-1

若完全二叉树有2k个结点,则必有n1=0,n0=k,n2=k-1

(4).二叉排序树

1.左子树上所有结点的关键字均小于根结点的关键字;

3.左子树和右子树又各是一棵二叉排序树。

数据结构-----树的易错点,数据结构,学习日常(考研向),数据结构,考研,笔记,算法

(5).平衡二叉树

树上任一结点的左子树和右子树深度(高度)之差不超过1

数据结构-----树的易错点,数据结构,学习日常(考研向),数据结构,考研,笔记,算法

7.在n个结点的二叉链表中,有n+1个空指针域

n个结点中,若每个结点都有左孩子和右孩子,那么最多有2n个指针

反过来,每个结点有且仅有一个父节点,除了头结点以外,所以最少有n-1个指针,那么空指针为2n-(n-1)=n+1文章来源地址https://www.toymoban.com/news/detail-666615.html

到了这里,关于数据结构-----树的易错点的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • torch.nn.functional.grid_sample(F.grid_sample)函数的说明 & 3D空间中的点向图像投影的易错点

    由于二者有一定共通之处,因此放在一篇文章内介绍。   该函数的作用是在图像/体素空间中采样特征。 变量名 数据类型 默认值 含义 备注 input Tensor - 原始图像/体素空间的特征 形状需为 ( B , C , H , W ) (B,C,H,W) ( B , C , H , W ) 或 ( B , C , D , H , W ) (B,C,D,H,W) ( B , C , D , H , W ) ,分

    2023年04月24日
    浏览(48)
  • 【C语言易错点】循环结构

    C语言的循环结构是一种控制结构,用于重复执行一段代码,直到满足某个条件为止。C语言提供了三种主要的循环结构:for循环、while循环和do-while循环。 for循环: for循环具有以下形式: 其中,初始化表达式在循环开始前执行一次,用于初始化循环控制变量;循环条件判断是

    2024年02月04日
    浏览(38)
  • C语言初学习——易错点合集(持续更新中)

    转义字符 例题一 输出: —— n=3 —— 例题二 输出: —— 1 13 14 —— 总结: 八进制值的判断取决于后续是否为合法的八进制。 以开始,最少1位,最多3位,且必须是合法的8进制数字,即0~7,如\\\"\\012\\\"。 例:在\\\"\\08\\\"中,’\\0’为结束符。 自增与自减 例题一 输出: —— 死循环

    2024年03月09日
    浏览(70)
  • 数据结构学习分享之树的介绍

    💓博主CSDN主页:杭电码农-NEO💓   ⏩专栏分类:数据结构学习分享⏪   🚚代码仓库:NEO的学习日记🚚   🌹关注我🫵带你了解更多数据结构的知识   🔝🔝 前面我们学的都是链式结构或数组这种线性结构,今天我们正式开始学习\\\"树\\\"这个结构.树涉及的问题有很多,包括普通树

    2024年02月05日
    浏览(57)
  • Python之数据库操作(连接数据库,增删改查操作,易错点理解)

    文章目录 前言 一、Python之数据库操作 二、 pymysql 安装 三、pymysql 包引入  连接数据库 创建游标 执行sql数据 - 增删改查 要获取查询结果数据 关闭游标,关闭数据库连接 总结 记录:Python操作数据库的步骤,不容易理解的地方。 学习地址: python与各大数据库的连接: http:/

    2023年04月16日
    浏览(57)
  • 【数据结构】时间复杂度(详细解释,例子分析,易错分析,图文并茂)

    🎊专栏【数据结构】 🍔喜欢的诗句:更喜岷山千里雪 三军过后尽开颜。 🎆音乐分享【星辰大海】 大一同学小吉,欢迎并且感谢大家指出我的问题🥰    目录 ⭐时间复杂度分类 🍔 方法 🎈平方阶 🎈立方阶  🎈对数阶 🍔例子 ✨常数时间复杂度 O(1) 🎈数组读取、索引和

    2023年04月20日
    浏览(55)
  • 数据结构和算法学习记录——平衡二叉树(基本介绍、平衡因子、平衡二叉树的定义、平衡二叉树的高度)

    目录 基本介绍 平衡因子 平衡二叉树  平衡二叉树的高度  什么是平衡二叉树? 以一个例子来解释一下: 搜索树结点按不同的插入次序,将会导致不同的深度和平均查找长度ASL   在二叉搜索树中查找一个元素:  (a)要找到Jan,需要查找一次;要找到Feb,需要查找两次;

    2023年04月26日
    浏览(65)
  • C语言-易错点汇总

    指针数组是一个数组。如同 int arr[10],表示arr数组有10个元素,每一个元素都是整型 指针数组 int* arr[10],表示arr数组有10个元素,每一个元素都是指针; 数组指针是指针。 int (*arr)[10] ,arr先与 * 结合,说明arr是一个指针,然后指向一个大小为10个整型的数组。注意:[]的优先级要

    2024年02月06日
    浏览(43)
  • C语言易错点整理

    本文涵盖了博主在平常写C语言题目时经常犯的一些错误,在这里帮大家整理出来,一些易错点会帮大家标识出来,希望大家看完这篇文章后有所得,引以为戒~ 题目: 解答: 首先在这个程序中有两个x,y,一个是在主函数中定义的局部变量,另一个是全局变量。 而在swap函数中

    2024年02月11日
    浏览(34)
  • 数据结构学习记录——平衡二叉树的调整(基本介绍、右单旋、左单旋、左右双旋、右左双旋、平衡因子的计算)

    目录 基本介绍 右单旋 左单旋 左右双旋 右左双旋  平衡因子的计算 首先,平衡二叉树也是一棵二叉搜索树。 当我们在一棵平衡二叉树进行插入或者删除时,可能会把原来的平衡二叉树变得不平衡, 这个时候我们就需要进行调整了。 平衡二叉树的调整主要分为四大类: RR旋

    2023年04月27日
    浏览(38)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包