你想要算法还是回答这个问题?
本题答案为
10
8 16
5 12 20
7 19
算法为:
步骤:如果根点的关键字值等于搜索的关键字,则成功.
否则,如果关键字值小于根结点,递归检查左子树.
如果大于根结点的关键字值,递归检查右子树.
若子树为空,发现不成功.
平均分析(在成功搜索两种情况下)
一般情况下,设置 P(n,i)而且它的左子树的结点数是 i时的平均搜索长度。如图所示的结点数为 n= 6且 i= 3;则 P(n,i)= P(6,3)= [ 1 ( P(3) 1)* 3 ( P(2) 1)* 2 ]/ 6
= [ 1 ( 5/3 1)* 3 ( 3/2 1)* 2 ]/ 6
注意:这里 P(3)、P(2)是具有 二叉分类树的平均搜索长度为3个结点和2个结点。P(i)为具有 一个结点二叉分类树的平均搜索长度.P(3)=(1 2 2)/ 3= 5/3
P(2)=(1 2)/ 2= 3/2
∴ P(n,i)= [ 1 ( P(i) 1)* i ( P(n-i-1) 1)*(n-i-1) ]/ n
n
二叉树
-1
∴ P(n)=∑ P(n,i)/ n
package com.test;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Clections;
import java.util.List;
/**
*
*在两个list中找出不同的元素
*@author leiwei 2011-12-14
*
*/
public class NoEqualsElement{
public static void main(String[] args){
List<String> list1= new ArrayList<String>();
List<String> list2= new ArrayList<String>();
list1.add("1");
list1.add("3");
list1.add("8");
list1.add("9");
list2.add("2");
list2.add("3");
list2.add("7");
for(String s2:list1){
boean flag= false;
for(String s1:list2){
if(s2.equals(s1)){
flag= true;
break;
}
}
if(!flag){
System.out.println(s2);
}
}
}
}
[java] view plain copy
package com.test;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Set;
import com.model.Student;
/**
列表元素求和
*重写对象Studentequals方法
*只要age相等对象相等
*
*在两个集合中删除相同的对象只保留一个
*@author leiwei 2011-12-19
*
*/
public class ListOBJ{
public static void main(String[] args){
Set<Student> setStudent= new HashSet<Student>();
List<Student> list1= new ArrayList<Student>();
List<Student> list2= new ArrayList<Student>();
Student s1= new Student();
s1.setAge("10");
list1.add(s1);
Student s2= new Student();
s2.setAge("20");
list1.add(s2);
Student s3= new Student();
s3.setAge("20");
list2.add(s3);
Student s4= new Student();
s4.setAge("30");
list2.add(s4);
/**
*我们知道set集合中的元素不会重复
*
*将连接对象集合放入,自然会排出重复
*
*对象(前提是Student对象重写equals方法)
*/
setStudent.addAll(list1);
setStudent.addAll(list2);
///输出测试是否成功排放
System.out.println(setStudent.size());
Iterator<Student> iterator= setStudent.iterator();
while(iterator.hasNext()){
Student s= iterator.next();
System.out.println(s.getAge());
}
}
}
[java] view plain copy
package com.model;
public class Student{
private String age;
public String getAge(){
return age;
}
public void setAge(String age){
this.age= age;
}
///重写equals方法,只要age相等,我们就认为两个对象相等
@Override
public boean equals(Object obj){
if(obj instanceof Student){
Student st=(Student) obj;
return(age.equals(st.age));
}else{
return super.equals(obj);
}
}
@Override
public int hashCode(){
return age.hashCode();
}
}