二叉树的性质
由于二叉树结构特殊,我们可以总结出以下的五个性质:
性质一:对于一棵二叉树,第i层的最大结点数量为 2i−1 个,比如二叉树的第一层只有一个根结点,也就是 20 = 1 ,而二叉树的第三层可以有 22 = 4个结点。
性质二:对于一棵深度为k的二叉树,可以具有的最大结点数量为: n = 20 + 21 + 22 + . . . + 2k − 1 我们发现,实际上每一层的结点数量,组成了一个等比数列,公比q为2,结合等比数列求和公式,我们可以将其简化为:
![](/i/l/?n=23&i=blog/2845511/202302/2845511-20230221231541997-1856586472.png)
性质三:假设一棵二叉树中度为0、1、2的结点数量分别为 n0、 n1、 n2,由于一棵二叉树中只有这三种类型的结点,那么可以直接得到结点总数: n = n0+n1+n2 我们不妨换一个思路,我们从二叉树的边数上考虑,因为每个结点有且仅有一条边与其父结点相连,那么边数之和就可以表示为: E = n1+2n2 度为1的结点有一条边,度为2的结点有两条边,度为0的结点没有,加在一起就是整棵二叉树的边数之和,结合我们在性质二中推导的结果,可以得到另一种计算结点总数的方式: E = n−1=n1+2n2 n = n1+2n2+1
再结合我们第一个公式: n = n0+n1+n2=n1+2n2+1 综上,对于任何一棵二叉树,如果其叶子结点个数为 n 0 n_0 n0 ,度为2的结点个数为 n 2 n_2 n2 ,那么两者满足以下公式: n0 = n2+1 (性质三的推导过程比较复杂,如果觉得麻烦推荐直接记忆)
性质四:完全二叉树除了最后一层有空缺外,其他层数都是饱满的,假设这棵二叉树为满二叉树,那么根据我们前面得到的性质,假设层数为k,那么结点数量为:n=2k−1 ,根据完全二叉树的性质,最后一层可以满可以不满,那么一棵完全二叉树结点数n满足: 2k−1−1 < n <= 2k−1 因为n肯定是一个整数,那么可以写为: 2k−1 <= n <= 2k−1 现在我们只看左边的不等式,我们对不等式两边同时取对数,得到: k−1 <= log2 n
综上所述,一棵具有n个结点的完全二叉树深度为 k=⌊log2 n⌋ + 1 。
(性质四的推导过程比较复杂,如果觉得麻烦推荐直接记忆)
性质五:一颗有n个结点的完全二叉树,由性质四得到深度为 k=⌊log2 n⌋+1 现在对于任意一个结点i,结点的顺序为从上往下,从左往右:
对于一个拥有左右孩子的结点来说,其左孩子为2i,右孩子为2i + 1。
如果i = 1,那么此结点为二叉树的根结点,如果i > 1,那么其父结点就是 ⌊ i / 2 ⌋ \lfloor i/2 \rfloor ⌊i/2⌋,比如第3个结点的父结点为第1个节点,也就是根结点。
如果2i > n,则结点i没有左孩子,比如下面图中的二叉树,n为5,假设此时i = 3,那么2i = 6 > n = 5 说明第三个结点没有左子树。
如果2i + 1 > n,则结点i没有右孩子。
标签:结点,数学,二叉树,一棵,n1,2i,性质 From: https://www.cnblogs.com/Ragnaros-Y/p/17142891.html