二分算法描述 s int Search_Bin(SST ST, KT key)t 结 low=l: high-ST length; 构 while(ow<=high) mid=(+high)/2 if(key==STelem(mid. key) return mid; else if(key<sTelem mid). key) high=mid-1 else low=mid+1; return 0 时间复杂度:Oogn) 二叉树的性质 数1、在二叉树的第层上至多有2个结点(>=1); 站2、深度为k的二叉树至多有2-1个结点(k>=1); 构3、对任何一棵二叉树T,如果其终端结点数为 n0,度为2的结点数为n,则n=n2+1。 4、具有n个结点的完全二叉树的深度为 t Llog:n+4 数 据 结 构 之 查 找 7 ¾ 二分算法描述 int Search_Bin(SST ST, KT key){ low=1 ; high=ST. length; while(low<=high){ mid=(low+high)/2; if(key==ST.elem[mid].key) return mid; else if(key<ST.elem[mid].key) high=mid-1; else low=mid+1; } return 0; }//时间复杂度：O(log2 n) 数 据 结 构 之 查 找 8 ¾ 二叉树的性质 1、在二叉树的第 i 层上至多有2 个结点(i>=1); 2、深度为k的二叉树至多有2 -1个结点(k>=1); 3、对任何一棵二叉树T，如果其终端结点数为 n0，度为2的结点数为n2，则n0=n2+1。 4、具有n个结点的完全二叉树的深度为: log2 n +1 k i-1