一、树
树的概念
🍑这是现实世界的树
🍑而我们这里所说的树,其实是一直特殊的数据结构
之前我们学习的不管是顺序表还是链表、队列、栈,都是一对一的线性结构。但在数据生活中还有很多一对多的情况,所有我们就要用到这种一对多的数据结构——树
📝树(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
树的存储结构
📝树结构相对线性表就比较复杂了,要存储表示起来就比较麻烦了,实际中树有很多种表示方式,如:双亲表示法,孩子表示法、孩子双亲表示法、孩子兄弟表示法等等。我们这里就简单的了解其中最常用的孩子兄弟表示法。(关于其他几种表示法,大话数据结构这本书里有详细的介绍)
我们观察后发现,任意一棵树,它的结点的第一个孩子如果存在就是唯一的。因此,我们设置两个结点引用,分别指向该结点的第一个孩子和该结点的右兄弟。
结点结构如表所示:
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) 由于最后一层的节点没有按照从左向右分布,因此只能算作是普通的二叉树。
其实完全二叉树类似这下面这种情况
从中我们也可以发现一些规律,如果一个完全二叉树的某一个结点没有右子树,那么该结点一定没有左子树,有右子树就一定得有左子树。它从左到右一定是连续的,中间不能出现空的。
🔔同时我们需要注意一个慢二叉树一定是一棵完全二叉树,但完全二叉树不一定是满二叉树。
从中我们也可以发现一些规律,如果一个完全二叉树的某一个结点没有右子树,那么该结点一定没有左子树,有右子树就一定得有左子树。它从左到右一定是连续的,中间不能出现空的。
🔔同时我们需要注意一个慢二叉树一定是一棵完全二叉树,但完全二叉树不一定是满二叉树。
我们来观察下面的图形
经过归纳分析,我们很容易得出这个结论
性质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否则无右孩子