「java二叉查找算法」java二叉查找算法的难点
本篇文章给大家谈谈java二叉查找算法，以及java二叉查找算法的难点对应的知识点，希望对各位有所帮助，不要忘了收藏本站喔。
本文目录一览：
- 1、用JAVA语言实现二叉树的层次遍历的非递归算法及查找算法。
- 2、设计一个读入一串整数构成一棵二叉排序树的算法
- 3、急急，设计一个“二叉”查找算法，将集合分成1/3和2/3大小的两个集合
- 4、设计一个非递归算法，从一棵二叉树中查找出所有节点的最大值并返回。
- 5、java根据一个数字 怎么能快速的查询到 他在哪个A B 之间？
用JAVA语言实现二叉树的层次遍历的非递归算法及查找算法。
分块查找
typedef struct
{ int key;
int link;
}SD;
typedef struct
{ int key;
float info;
}JD;
int blocksrch(JD r[],SD nd[],int b,int k,int n)
{ int i=1,j;
while((knd[i].key)(i=b) i++;
if(ib) { printf("\nNot found");
return(0);
}
j=nd[i].link;
while((jn)(k!=r[j].key)(r[j].key=nd[i].key))
j++;
if(k!=r[j].key) { j=0; printf("\nNot found"); }
return(j);
}
哈希查找算法实现
#define M 100
int h(int k)
{ return(k%97);
}
int slbxxcz(int t[],int k)
{ int i,j=0;
i=h(k);
while((jM)(t[(i+j)%M]!=k)(t[(i+j}%M]!=0))
j++;
i=(i+j)%M;
if(t[i]==k) return(i);
else return(-1);
}
int slbxxcr(int t[],int k)
{ int i,j=0;
i=h(k);
while((jM)(t[(i+j)%M]!=k)(t[(i+j}%M]0))
j++;
if(j==M) return(0);
i=(i+j)%M;
if(t[i]=0)
{ t[i]=k; return(1); }
if(t[i]==k) return(1);
}
int slbxxsc(int t[],int k)
{ int i,j=0;
i=h(k);
while((jM)(t[(i+j)%M]!=k)(t[(i+j}%M]!=0))
j++;
i=(i+j)%M;
if(t[i]==k)
{ t[i]=-1; return(1); }
return(0);
}
顺序查找
#define M 500
typedef struct
{ int key;
float info;
}JD;
int seqsrch(JD r[],int n,int k)
{ int i=n;
r[0].key=k;
while(r[i].key!=k)
i--;
return(i);
}
折半查找
int binsrch(JD r[],int n,int k)
{ int low,high,mid,found;
low=1; high=n; found=0;
while((low=high)(found==0))
{ mid=(low+high)/2;
if(kr[mid].key) low=mid+1;
else if(k==r[mid].key) found=1;
else high=mid-1;
}
if(found==1)
return(mid);
else
return(0);
}
虽然都是C++写的，万变不离其中，JAVA我现在 刚学习，就不献丑了
设计一个读入一串整数构成一棵二叉排序树的算法
此定义为递归式定义。
二叉排序树又称二叉查找树，它可以是一棵空树，若非空时具有下述性质：
1、若根结点的左子树非空，则左子树上所有结点的关键字值均小于等于根结点的关键字值。
2、若根结点的右子树非空，则右子树上所有结点的关键字值均大于等于根结点的关键字值。
3、根结点的左、右子树也分别为二叉排序树。
二叉排序树建立说明：
当需要插入一个节点到二叉排序树时，需要先找到它的父节点。
其实 它就是用插入的节点不断的和每一个节点比较（第一次当然是和根节点比较啦），如果小于等于则进入左边子树，再与左边子树的根节点比较，直到找到它要放的位置，否则进入右子树，进行上述操作。
下面是我写的程序，是控制台下的程序：
#includestdio.h
#includestdlib.h
using namespace std;
typedef struct node
{
int element;
struct node* left;
struct node* right;
}Node,*NodePtr;
void insertNode(NodePtr *head,int data)//插入节点，注意这用了指向指针的指针，很有意思
{
if (*head==NULL)
{
*head=new Node;
(*head)-element=data;
(*head)-left=NULL;
(*head)-right=NULL;
}
else
{
if (data=(*head)-element)
{
insertNode(((*head)-left),data);
}
else
{
insertNode(((*head)-right),data);
}
}
}
NodePtr creatTree()//构造二叉排序树，控制台下输入整数，0表示结束输入
{
NodePtr head=NULL;
int data;
scanf("%d",data);
while(data!=0)
{
insertNode(head,data);
scanf("%d",data);
}
return head;
}
void printTree(NodePtr head)//中序遍历二叉排序树，得到有序序列
{
if(head!=NULL)
{
printTree(head-left);
printf("%d ",head-element);
printTree(head-right);
}
}
int main()
{
NodePtr head;
printf("请输入一串整数，空格隔开，0表示输入结束\n");
head=creatTree();
printf("中序遍历二叉排序树\n");
printTree(head);
printf("\n");
return 0;
}
运行结果：
不知道符合你要求没，有问题可以hi我。
急急，设计一个“二叉”查找算法，将集合分成1/3和2/3大小的两个集合
这个问题很简单，排序，然后找到分割点，分。
就这样。你说什么二叉查找算法，是不是说要对已经排序好的二叉树进行分割？
题目也表达的比较乱。
设计一个非递归算法，从一棵二叉树中查找出所有节点的最大值并返回。
给个思路：
找最大值的关键是树的遍历，而递归的遍历方式，就是利用函数调用，参数的入栈出栈，来达到回溯的目的，同理，不用递归调用，我们也可以采用这个思想
创建一个栈式的数据结构
将根节点指针压入栈中，访问其值，假如我们采用广度优先的遍历方式，就遍历其子节点
在访问子节点的同时，依次将访问过的节点指针压入栈中，而最上面的节点就是最后访问的节点
如最上面的节点是叶子节点，则弹栈，否则继续遍历其子节点，并如3步所说，依访问顺序压栈
对于所有子节点都已遍历（压栈）的父节点，做标记，则当弹栈后，栈的最上面是一个带有标记的非叶子节点，亦将其弹出栈
循环3-5步，直到栈空为止
深度优先搜索，也可以用类似的方式实现
java根据一个数字 怎么能快速的查询到 他在哪个A B 之间？
首先要确定你的地域信息是怎么判定的，需要IP的哪些位？
IP分为4段，每段3位。从头到尾，不足不零。
可以形成。最大不超过12位的IP整数。要追求速度，首先需要将12位完整的IP中的某一部分脱离开。现在只需要除开IP段中的某一个段。即能取到9位的整数。这时，java中int类型支持的数字大小是20亿，即10位数，那仅取三段的IP满足int【Integer】的条件。当然，如果像LZ说的，取startIP和endIP，是否就是只二段？这样也可。我说的三段，是需要舍去一段。
现在将刚才我们得到的int型做为Map的key。
为什么要用Integer？下面分析。
首先查询最快的，肯定是HashMap。这里不得不说下HashMap的原理。
1、HashMap里添加一个元素。hashMap.put(key,value);是取Key值的hashCode，经过HashMap的hash(int)的运算，直接得到在HashMap中键数组中应该位于的下标。再将Key和Value的Entry【含Key，Value】放到HashMap里。注意。。是没有明显的遍历操作的。
2、从HashMap中取值，是怎么做的呢？同样，hashMap.get(key)是直接由key值的hashCode得key在键数组中的下标，再取出对应Entry【含Key，Value】。。同样。。没有明显的遍历操作的。
上面2步可以统称为：HashMap的hash算法。具体的实现。你可以去看jdk的源码。
现在就可以回到最开始的，为什么要用Integer类型做key，因为。。Integer重写了hashCode方法。他是直接返回Integer的value字段的，而Integer的eqauls方法甚至直接用的==操作符，这两点决定了高效性，。而String的eqauls和hashCode也重写了，但运算量远大于Integer的。对于HashMap来说，hashCode()和equals()方法，是取值，添加值都会用的。以下会把相关JDK代码贴出来。------如果实在不能用Integer，建议用Long。long的equals用的也是==，hashCode只是对value值进行了无符号右移32位再与原value值取“异或运算”。return (int)(value ^ (value 32));
为什么不用TreeMap呢。我分析了TreeMap的实现。他是这样做的。
1、TreeMap里添加元素。put(key,value)，是首先，TreeMap,需要一个对Key的比较器，因为TreeMap是有序的，他的添加是由Key，先找到Key在键数组的位置，再将key，value的Entry放到对应位置。同时设置Entry的前一个和后一个Entry。形成有序Map。在查找Key的位置时，用的是树查找【二叉查找】，从根节点，依次查找。
2、TreeMap里取元素：同样的。用二叉查询方法，找到Key对应的Entry。从而得到Key，Value值。
我做了实验。分别在
1、HashMap里添加1000000条Integer键，String值的随机元素。用时，2500左右毫秒，然后再循环查询10000条随机数据，用时70毫秒左右。
2、TreeMap里做相同的操作，耗时分别为：2800毫秒和95毫秒。
可以认证上述观点。
综上所述。你应该用HashMap做为容器，用Integer做为键。能达到最快查询速度。
下面贴出相关代码。是在JDK1.6的源码里贴出来的。有兴趣的话，可以看一下。
HashMap：
public V put(K key, V value) {
if (key == null)
return putForNullKey(value);
int hash = hash(key.hashCode());
int i = indexFor(hash, table.length);
for (EntryK,V e = table[i]; e != null; e = e.next) {
Object k;
if (e.hash == hash ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
addEntry(hash, key, value, i);
return null;
}
static int indexFor(int h, int length) {
return h (length-1);
}
public V get(Object key) {
if (key == null)
return getForNullKey();
int hash = hash(key.hashCode());
for (EntryK,V e = table[indexFor(hash, table.length)];
e != null;
e = e.next) {
Object k;
if (e.hash == hash ((k = e.key) == key || key.equals(k)))
return e.value;
}
return null;
}
TreeMap：
public V put(K key, V value) {
EntryK,V t = root;
if (t == null) {
// TBD:
// 5045147: (coll) Adding null to an empty TreeSet should
// throw NullPointerException
//
// compare(key, key); // type check
root = new EntryK,V(key, value, null);
size = 1;
modCount++;
return null;
}
int cmp;
EntryK,V parent;
// split comparator and comparable paths
Comparator? super K cpr = comparator;
if (cpr != null) {
do {
parent = t;
cmp = cpr.compare(key, t.key);
if (cmp 0)
t = t.left;
else if (cmp 0)
t = t.right;
else
return t.setValue(value);
} while (t != null);
}
else {
if (key == null)
throw new NullPointerException();
Comparable? super K k = (Comparable? super K) key;
do {
parent = t;
cmp = k.compareTo(t.key);
if (cmp 0)
t = t.left;
else if (cmp 0)
t = t.right;
else
return t.setValue(value);
} while (t != null);
}
EntryK,V e = new EntryK,V(key, value, parent);
if (cmp 0)
parent.left = e;
else
parent.right = e;
fixAfterInsertion(e);
size++;
modCount++;
return null;
}
public V get(Object key) {
EntryK,V p = getEntry(key);
return (p==null ? null : p.value);
}
final EntryK,V getEntry(Object key) {
// Offload comparator-based version for sake of performance
if (comparator != null)
return getEntryUsingComparator(key);
if (key == null)
throw new NullPointerException();
Comparable? super K k = (Comparable? super K) key;
EntryK,V p = root;
while (p != null) {
int cmp = k.compareTo(p.key);
if (cmp 0)
p = p.left;
else if (cmp 0)
p = p.right;
else
return p;
}
return null;
}
Integer 的hashCode 和 equals方法：
public int hashCode() {
return value;
}
public boolean equals(Object obj) {
if (obj instanceof Integer) {
return value == ((Integer)obj).intValue();
}
return false;
}
String：的hashCode 和 equals方法：
public int hashCode() {
int h = hash;
int len = count;
if (h == 0 len 0) {
int off = offset;
char val[] = value;
for (int i = 0; i len; i++) {
h = 31*h + val[off++];
}
hash = h;
}
return h;
}
public boolean equals(Object anObject) {
if (this == anObject) {
return true;
}
if (anObject instanceof String) {
String anotherString = (String)anObject;
int n = count;
if (n == anotherString.count) {
char v1[] = value;
char v2[] = anotherString.value;
int i = offset;
int j = anotherString.offset;
while (n-- != 0) {
if (v1[i++] != v2[j++])
return false;
}
return true;
}
}
return false;
}
关于java二叉查找算法和java二叉查找算法的难点的介绍到此就结束了，不知道你从中找到你需要的信息了吗 ？如果你还想了解更多这方面的信息，记得收藏关注本站。
发布于：2022-11-28，除非注明，否则均为原创文章，转载请注明出处。