二叉树算法习题

学习了二叉树的概念，针对学习结果做一些习题。

1. 某二叉树中有n个度为2的节点，则该二叉树的叶子节点数为？
   解析：
   二叉树的叶子节点个数公式：度数为2的节点加一，故答案为n+1。

2. 深度为5的满二叉树有多少个叶子节点？
   解析：
   度为0的结点(即叶子节点)总比度为2的结点多一个。
   因为是满二叉树，可以先算出深度为4的节点个数，2^4-1=15，如果深度为5，则15 +1 = 16；

3. 下列二叉树前序遍历的结果是？

       A  
     /   \
    B     C
   / \   / \
  D   E F   G
   \       /
    H     I

前序遍历是从根节点，至左子树，再至右子树。
所以结果是ABDHECFGI

4. 对长度为n的线性表排序，最坏情况下，比较次数不是n(n-1)/2的排序方式是？
   解析：快速排序、冒泡排序、简单插入排序法最坏排序方式都是n(n-1)/2。
   堆排序法的最坏排序法是n*log2n。
   所以答案为堆排序法。

5. 设一颗完全二叉树共有700个节点，则该完全二叉树中的叶子节点数为？
   解析：我们知道叶子节点的个数一定比度为2的节点多一个，故我们可以设置：
   度为2的节点：n，
   叶子节点：n + 1，
   度为1节点：x
   2n + x = 699
   结果为奇数故x为1，最终我们可以得出2n = 698 n = 349。
   所以叶子节点的个数为350。

6. 对长度为n的线性表中查找最大项，在最坏情况下所需要的比较次数为？
   解析：线性表最坏比较次数与它的长度是相等，所以答案为n。

7. 某二叉树共有7个节点，其中叶子节点只有1个，则该二叉树的深度为？（假设根节点在第一层）
   解析：我们知道如果叶子节点只有一个说明没有度为2的节点。一共7个节点，可以顺序往下排，故深度为7。
   举例图片：

        A  
       /   
      B   
     / 
    C
     \      
      D
     / 
    E   
     \      
      F 
     / 
    G