[树] 二叉树的复习

Prerequisites

---

等比数列前n项求和

2. <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,求这个两个节点的距离.所谓的距离即连接这俩节点的边数.