基本算法连载（3）－3个基本性质

• 性质1：一颗二叉树（严格的二叉树，即没有度为1的节点），有N个内部节点，那么它将有N＋1个外部节点。

采用归纳法证明：

1. 如果只有一个外部节点，即单独的一个根节点，那么内部节点数为0，结论显然成立。
2. 假设有N－1个内部节点时，结论成立。那么二叉树拥有N个内部节点时，左子树有k个内部节点，右子树有N－k－1个内部节点，此外包括一个根节点。由于左 右子树的节点数都小于N，所以由前面假设可得左子树有k＋1个外部节点，右子树有N－k个节点，总共有k＋1＋(N-k)个节点，即N＋1个节点。
3. 由性质1可得，一颗有N个外部节点的二叉树需要用数组存储，那么需要申请一个拥有2N－1个元素的数组。

• 性质2：在一个已排序的序列中寻找和为给定数值的两个数，可在O(n)时间内完成。

简单示例：
#include <stdio.h>
int main(int argc,char*argv[]){
//排好序的数组序列
int a[10] = {1,2,3,4,5,6,7,8,9,10};
//给定值
int value = 21;
int i = 0,j = 9;
while(1){
if(a[i] + a[j] == value){
break;
}else{
if(i >= j){
printf("%s\n","Not found!");
exit(1);
}
}
if(a[i] + a[j]<value){
i++;
}else{
j--;
}
}
printf("%d\n%d",i,j);
return 0;
}

• 性质3：在一个无序序列中寻找和为给定数值的两个数，可在O(nlgn)时间内完成。

1. 采用快速排序对无序序列进行排序，时间复杂度为O(nlgn)。
2. 由性质2可知，时间复杂度为O(n)。