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

简介: 数据结构-----树的易错点

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个孩子


image.png


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


目录
相关文章
|
2月前
|
存储 算法 C语言
"揭秘C语言中的王者之树——红黑树:一场数据结构与算法的华丽舞蹈,让你的程序效率飙升,直击性能巅峰!"
【8月更文挑战第20天】红黑树是自平衡二叉查找树,通过旋转和重着色保持平衡,确保高效执行插入、删除和查找操作,时间复杂度为O(log n)。本文介绍红黑树的基本属性、存储结构及其C语言实现。红黑树遵循五项基本规则以保持平衡状态。在C语言中,节点包含数据、颜色、父节点和子节点指针。文章提供了一个示例代码框架,用于创建节点、插入节点并执行必要的修复操作以维护红黑树的特性。
68 1
|
4月前
|
存储 算法 Linux
【数据结构和算法】---二叉树(1)--树概念及结构
【数据结构和算法】---二叉树(1)--树概念及结构
42 0
|
8天前
|
JSON 前端开发 JavaScript
一文了解树在前端中的应用,掌握数据结构中树的生命线
该文章详细介绍了树这一数据结构在前端开发中的应用,包括树的基本概念、遍历方法(如深度优先遍历、广度优先遍历)以及二叉树的先序、中序、后序遍历,并通过实例代码展示了如何在JavaScript中实现这些遍历算法。此外,文章还探讨了树结构在处理JSON数据时的应用场景。
一文了解树在前端中的应用,掌握数据结构中树的生命线
|
24天前
|
C语言
数据结构基础详解(C语言):图的基本概念_无向图_有向图_子图_生成树_生成森林_完全图
本文介绍了图的基本概念,包括图的定义、无向图与有向图、简单图与多重图等,并解释了顶点度、路径、连通性等相关术语。此外还讨论了子图、生成树、带权图及几种特殊形态的图,如完全图和树等。通过这些概念,读者可以更好地理解图论的基础知识。
|
26天前
|
存储 算法 C语言
数据结构基础详解(C语言): 二叉树的遍历_线索二叉树_树的存储结构_树与森林详解
本文从二叉树遍历入手,详细介绍了先序、中序和后序遍历方法,并探讨了如何构建二叉树及线索二叉树的概念。接着,文章讲解了树和森林的存储结构,特别是如何将树与森林转换为二叉树形式,以便利用二叉树的遍历方法。最后,讨论了树和森林的遍历算法,包括先根、后根和层次遍历。通过这些内容,读者可以全面了解二叉树及其相关概念。
|
26天前
|
存储 机器学习/深度学习 C语言
数据结构基础详解(C语言): 树与二叉树的基本类型与存储结构详解
本文介绍了树和二叉树的基本概念及性质。树是由节点组成的层次结构,其中节点的度为其分支数量,树的度为树中最大节点度数。二叉树是一种特殊的树,其节点最多有两个子节点,具有多种性质,如叶子节点数与度为2的节点数之间的关系。此外,还介绍了二叉树的不同形态,包括满二叉树、完全二叉树、二叉排序树和平衡二叉树,并探讨了二叉树的顺序存储和链式存储结构。
|
26天前
|
存储 C语言
数据结构基础详解(C语言): 树与二叉树的应用_哈夫曼树与哈夫曼曼编码_并查集_二叉排序树_平衡二叉树
本文详细介绍了树与二叉树的应用,涵盖哈夫曼树与哈夫曼编码、并查集以及二叉排序树等内容。首先讲解了哈夫曼树的构造方法及其在数据压缩中的应用;接着介绍了并查集的基本概念、存储结构及优化方法;随后探讨了二叉排序树的定义、查找、插入和删除操作;最后阐述了平衡二叉树的概念及其在保证树平衡状态下的插入和删除操作。通过本文,读者可以全面了解树与二叉树在实际问题中的应用技巧和优化策略。
|
2月前
|
存储 算法 Linux
【数据结构】树、二叉树与堆(长期维护)(1)
【数据结构】树、二叉树与堆(长期维护)(1)
|
2月前
|
算法
【数据结构】树、二叉树与堆(长期维护)(2)
【数据结构】树、二叉树与堆(长期维护)(2)
【数据结构】树、二叉树与堆(长期维护)(2)
|
3月前
|
存储
【数据结构】树和二叉树的概念及结构
数据结构——树和二叉树的概念及结构
65 3
【数据结构】树和二叉树的概念及结构