20210919
恋词强化3 | 高数强化-C5-3(完)| 数据结构强化C5-2
恋词强化3
- 已完成
高数强化-C5-3(完)
- 海伦公式: $S=\sqrt{p (p-a) (p-b) (p-c)}$
公式描述:公式中a,b,c分别为三角形三边长,p为半周长,S为三角形的面积。
数据结构强化C5-2
二叉树的性质
- “在任意一棵非空二叉排序树中,删除某结点又将其插入,则所得二叉排序树与删除前原二叉排序树相同”
只有被删除结点时叶子结点这句话才成立
- “在完全二叉树中,叶子结点的双亲的左兄弟(若存在)一定不是叶子结点”
在完全二叉树中,叶子结点的双亲的左兄弟的孩子一定在其前面(且一定存在),故双亲的左兄弟(若存在)一定不是叶结点
- 设高度为 h 的二叉树上只有度为 0 和 度为 2 的结点,则此类二叉树中所包含的结点数至少为?
- 设二叉树只有度为 0 和 2 的结点,其结点个数为15,则二叉树的最大深度为?
- 记录这两道题。这两道题用的思想是一样的,怎么考虑一个“只有度为 0 和 2 的结点的二叉树”“?如下图所示,非常容易想到的是第一幅图,再往下画会想到第二幅图,但是再仔细想想,我只是局限在了完全二叉树中,题目并没有说完全二叉树,所以再往下画应该是图三并非图二,而一般情况就是图四即:除根结点层只有一个结点外,其他 h-1 层均有两个结点。所以结点总数为
2(h-1)+1 = 2h-1
。- 那么还有一个需要想清楚的点就是,在高度固定情况下,这类二叉树所包含的结点数其实是最少的,而图2则是满足这类二叉树条件下最大结点数情况其实就是满二叉树;而在结点固定情况下,要使高度/深度最多,这类二叉树则是满足条件的最大深度,可以想象一下如果是图二的情况,每一层结点数会很多,那么在结点数固定情况下,这种是最小深度。所以第二问也就迎刃而解了,
2h-1=15
,h=8
。