0


《Java数据结构》这些树和二叉树的性质你还记得吗?

✅作者简介:大家好,我是小鱼儿,大家可以叫我鱼儿

📒博客首页:是小鱼儿哈

🔥系列专栏:Java数据结构

🌻每日一句:对轻易得到的东西需要心存戒心,真正有价值的东西都是需要付出代价的

💖博主也在学习阶段,如发现问题请告知,非常感谢💖

一、树

树的概念

🍑这是现实世界的树

🍑而我们这里所说的树,其实是一直特殊的数据结构

之前我们学习的不管是顺序表还是链表、队列、栈,都是一对一的线性结构。但在数据生活中还有很多一对多的情况,所有我们就要用到这种一对多的数据结构——树

📝树(Tree)是n(n≥0)个结点的有限集。n=0时称为空树。 在任意一颗非空树中
(1)有且仅有一个特定的称为根(root)的结点
(2)当n>1时,其余结点可分为m(m>0)个互不相交的有限集 T 1 , T 2 , . . . , T m ,

     **其中每一个集合本身又是一棵树,并且称为根的子树(SubTree)**

有两个点需要注意一下:

  1. 树是递归定义的——也就是说树的定义之中还用到了树的定义
  2. 树形结构中,子树之间不能有交集,否则就不是树形结构

下面来解释一下这两点:

🌰比如这是一个树

下图的子树T1和T2就是根结点A的子树。当然,D,G,H,I组成的树又是B为结点的子树,E、J组成的树是C为结点的树的子树。

🌰一些非树的例子

上面三个就不是树结构,只有右下角的那个称为树型结构


树的结点分类

📝树的结点包含一个数据元素及若干指向其子树的分支。结点拥有的子树数称为结点的度(Degree) 。

📝度为0的结点称为叶结点(Leaf)或终端结点;度不为0的结点称为非终端结点或分支结点。除根结点之外,分支结点也称为内部结点。树的度是树内各结点的度的最大值。

🌰如下图,因为这棵树结点的度的最大值是结点D的度,为3,所以树的度为3.


结点之间的关系

  1. 双亲节点或父节点:若一个节点含有子节点,则这个节点称为其子节点的父节点
  2. 孩子结点或子结点:一个结点含有的子树的根结点称为该结点的子结点
  3. 兄弟节点:具有相同父节点的节点互称为兄弟节点

节点的祖先:从根到该节点所经分支上的所有节点,如上图对于结点H来说,D、B、A都是他的祖先

子孙:以某节点为根的子树中任一节点都称为该节点的子孙。如上图:B的子孙有D、G、H、I


树的存储结构

📝树结构相对线性表就比较复杂了,要存储表示起来就比较麻烦了,实际中树有很多种表示方式,如:双亲表示法,孩子表示法、孩子双亲表示法、孩子兄弟表示法等等。我们这里就简单的了解其中最常用的孩子兄弟表示法。(关于其他几种表示法,大话数据结构这本书里有详细的介绍)

我们观察后发现,任意一棵树,它的结点的第一个孩子如果存在就是唯一的。因此,我们设置两个结点引用,分别指向该结点的第一个孩子和该结点的右兄弟

结点结构如表所示:
datefristchildrightbrother

** class TreeNode {**

** int date; // 数据域**

** TreeNode firstchild; // 该结点的第一个孩子**

** TreeNode rightbrother; // 该结点的右兄弟**

}

** 那么下面的树:**

就可以表示成:

这种表示其实就是把一棵复杂的树变成了一棵二叉树

至于二叉树是什么?这也是咱们接下来要重点聊的内容😁


其他相关概念

📝结点的层次:从一棵树的树根开始,树根所在层为第一层,根的孩子结点所在的层为第二层,依次类推

📝树的高度或深度:树中节点的最大层次

📝堂兄弟节点:双亲在同一层的节点互为堂兄弟

🌻森林:由m(m>0)棵互不相交的树的集合称为森林;

** 🌻有序树和无序树**:如果树中结点的子树从左到右看,谁在左边,谁在右边,是有规定的,这棵树称为有序树;反之称为无序树。

在有序树中,一个结点最左边的子树称为"第一个孩子",最右边的称为"最后一个孩子"。

二、 二叉树

二叉树的概念

🌻简单地理解,满足以下两个条件的树就是二叉树:

  1. 本身是有序树;
  2. 树中包含的各个节点的度不能超过 2,即只能是 0、1 或者 2;

🌰例如,图 1a) 就是一棵二叉树,而图 1b) 则不是。

再深入的理解就是:

📝 一棵二叉树是结点的一个有限集合,该集合:
1. 或者为空
2. 或者是由一个根节点加上两棵别称为左子树和右子树的二叉树组成

🍑 从上图可以看出:
1. 二叉树不存在度大于2的结点
2. 二叉树的子树有左右之分,次序不能颠倒,因此二叉树是有序树

注意:对于任意的二叉树都是由以下几种情况复合而成的:

🍑 自然界的二叉树:

** 🍑我们数据结构要研究的二叉树:**

📝特殊的二叉树

🍑如果二叉树中除了叶子结点,每个结点的度都为 2,则此二叉树称为满二叉树

**🍑如果二叉树中除去最后一层节点为满二叉树,且最后一层的结点依次从左到右分布,则此二叉树被称为完全二叉树 **

如图 3a) 所示是一棵完全二叉树,图 3b) 由于最后一层的节点没有按照从左向右分布,因此只能算作是普通的二叉树。

其实完全二叉树类似这下面这种情况

** 从中我们也可以发现一些规律,如果一个完全二叉树的某一个结点没有右子树,那么该结点一定没有左子树,有右子树就一定得有左子树。它从左到右一定是连续的,中间不能出现空的。**

🔔同时我们需要注意一个慢二叉树一定是一棵完全二叉树,但完全二叉树不一定是满二叉树。


二叉树的性质

性质一、若规定根结点的层数为1,则一棵非空二叉树的第i层上最多有2^(i-1) 个结点.

我们来观察下面的图形

经过归纳分析,我们很容易得出这个结论

性质2:若规定根节点的层数为1,则深度为k的二叉树的最大结点数是2^k - 1 .(深度为k意思就是有k层的二叉树)

我们前面已经知道,一棵非空二叉树的第i层上2^(i-1) 个结点,那么k层的二叉树的结点树不就是首项是1、公比是2的等比数列求和吗?

性质3:对任何一棵非空二叉树, 如果度为0其叶结点个数为n0 , 度为2的分支结点个数为n2 ,则有n0 =n2 +1

📝对于二叉树来说,我们会发现(除了根节点)对于每一个结点来说,都有其对应父结点分支指向它,假设树中分枝数为 B,那么总的结点数就是B+1

设总结点数为n,度为0的结点(即叶子结点)个数为n0、度为1的结点个数为n1、度为2的结点个数为n2,那么就有n = n0 + n1 + n2

同时分支数B = n1 + 2 * n2,B + 1 == n

所以就有n0 = n2 + 1

下面我们就用这个性质来做几道题目练练手

🌰第一题

该二叉树的结点数是奇数,而对于结点数是奇数的二叉树,像这样:

你会发现,该二叉树中度为1的结点数一个都没有,这不是偶然,你观察其他的的二叉树,会发现也有这样一个规律。

而对于结点数是偶数的二叉树呢?


** 你会发现结点数为偶数的二叉树,有且仅有一个度为1的结点**

那么这样我们就可以开始算了: 设叶子结点即——度为0的结点数为n0,度为1的结点数为n1(n1 == 0),度为2的结点数为n2(n2 = n0 -1)

399 = n0 + n1 + n2 = 2 n0 - 1 --->n0 = 200*

** 🌰第二题**

2n说明结点数是偶数个,度为1的结点个数为1,**2n **= n0 + n1 + n2 = 1 + n0 + (n0 - 1)

**即n0 == n,叶子结点个数为n **

**🌰第三题 **

**答案是:B **

** 🌰第四题**

对于这个题目就要用到我们的性质四了

性质四:具有n个结点的完全二叉树的深度k为 log2(n+1)上取整

2^9 == 512,即log2(531 + 1) == 9.xx向上取整即为10,所以答案就是B

性质五:对于具有n个结点的完全二叉树,如果按照从上至下从左至右的数组顺序对所有节点从0开始编号,则对于序号为i的结点有:

1. 若i>0,i位置节点的双亲序号:(i-1)/2;i=0,i为根节点编号,无双亲节点
2. 若2i+1<n,左孩子序号:2i+1,2i+1>=n否则无左孩子
3. 若2i+2<n,右孩子序号:2i+2,2i+2>=n否则无右孩子


本文转载自: https://blog.csdn.net/weixin_61061381/article/details/124766506
版权归原作者 是小鱼儿哈 所有, 如有侵权,请联系我们删除。

“《Java数据结构》这些树和二叉树的性质你还记得吗?”的评论:

还没有评论