若一棵完全二叉树有768 个结点,则该二叉树中叶结点的个数是( )。
设:
有两个孩子的节点个数为a;
有一个孩子的节点个数为b;
没有孩子(即叶子结点)的节点个数为c;
由条件知:
1. a + b + c = 768;
2. 由完全二叉树定义,可以知道只有一个孩子的节点b个数为0或1,由于总节点个数为768,所以可以知道b=1;
3. 除了叶子结点,所有节点的个数都对应一条边的个数,而边的个数,又是 两个孩子的节点个数×2+一个孩子的节点个数×1,即为 768-1 = a * 2 + b;
所以: