Prerequisites
等比数列前n项求和
- <a href=http://baike.baidu.com/link?url=Q6x4OJn-CpvvLpZospWan8uWSQEUmPY-06G7E-nSlYjY9HfHFJV2xxfD4-2tb6koTXt177MOljgYRV6daMuZ3q>log运算法则</a>
满二叉树 vs 完全二叉树
- 深度为k的满二叉树的节点总数：
2^0 + 2^1 + 2^2 + ... + 2 ^(k-1) = 2^k - 1 - 完全二叉树（除最后一层的右边一些节点缺失外，其余的每层节点数均为最大）.
- 满二叉树的节点总数:
| 树高 | 节点总数 |
|---|---|
| 1 | 1 |
| 2 | 3 |
| 3 | 7 |
| k | 2^k - 1 |
- exam 01 随手搜到的一个题目帮助理解。
解析见<a href= "http://www.zybang.com/question/5f55865c4c1c01b67857f9708e29f65b.html">这里</a>
一个完全二叉树共有699个节点，则该二叉树的叶子节点数目是： B
A. 349 B.350 C.255 D.351
- exam 02
完全二叉树有2*n-1 的节点,则它的叶子节点数为?（这题完全跟上面一样）
答案为n.
设树高为k，最后一层节点数目为m。 则该树的节点总数2^(k-1) - 1 + m = 2n-1 >> 2^(k-1) + m = 2n >>2^(k-1)/2 + m/2 = n
该树的叶子节点总数为m + 2^(k-2) - m/2 = 2^(k-1)/2 + m/2 = n.
疑问 - exam 02反之也成立吗？
- exam 03
完全二叉树有n个叶子节点,则它的节点总数为?
答案确实可以，按上面的思路设一个树高k，设最后一层点的数目m，最后确实可以化简为只与n相关的节点总数(2n-1)。
- exam 04
04.1 给定一完全二叉树root，求其节点总数.
04.2 给定一二叉树root，判断其是否为完全二叉树.
- exam 05
对于普通二叉树，给定2个节点Node0,Node1,求这个两个节点的距离.所谓的距离即连接这俩节点的边数.
网友评论