java二叉查找树的实现代码

2023-09-26 18:04:05 229

本文实例为大家分享了java二叉查找树的具体代码，供大家参考，具体内容如下

package查找;

importedu.princeton.cs.algs4.Queue;
importedu.princeton.cs.algs4.StdOut;

publicclassBST,Value>{
privateclassNode{
privateKeykey;//键
privateValuevalue;//值
privateNodeleft,right;//指向子树的链接
privateintn;//以该节点为根的子树中的节点总数

publicNode(Keykey,Valueval,intn){
this.key=key;
this.value=val;
this.n=n;
}
}

privateNoderoot;

publicintsize(){
returnsize(root);
}

privateintsize(Nodex){
if(x==null)
return0;
else
returnx.n;
}

/**
*如果树是空的，则查找未命中如果被查找的键小于根节点，则在左子树中继续查找如果被查找的键大于根节点，则在右子树中继续查找
*如果被查找的键和根节点的键相等，查找命中
*
*@paramkey
*@return
*/
publicValueget(Keykey){
returnget(root,key);
}

privateValueget(Nodex,Keykey){
if(x==null)
returnnull;
intcmp=key.compareTo(x.key);
if(cmp<0)
returnget(x.left,key);
elseif(cmp>0)
returnget(x.right,key);
else
returnx.value;
}

/**
*二叉查找树的一个很重要的特性就是插入的实现难度和查找差不多。当查找到一个不存在与树中的节点（null）时，new新节点，并将上一路径指向该节点
*
*@paramkey
*@paramval
*/
publicvoidput(Keykey,Valueval){
root=put(root,key,val);
}

privateNodeput(Nodex,Keykey,Valueval){
if(x==null)
returnnewNode(key,val,1);
intcmp=key.compareTo(x.key);
if(cmp<0)
x.left=put(x.left,key,val);
elseif(cmp>0)
x.right=put(x.right,key,val);
else
x.value=val;
x.n=size(x.left)+size(x.right);//要及时更新节点的子树数量
returnx;
}

publicKeymin(){
returnmin(root).key;
}

privateNodemin(Nodex){
if(x.left==null)
returnx;
returnmin(x.left);
}

publicKeymax(){
returnmax(root).key;
}

privateNodemax(Nodex){
if(x.right==null)
returnx;
returnmin(x.right);
}

/**
*向下取整：找出小于等于该键的最大键
*
*@paramkey
*@return
*/
publicKeyfloor(Keykey){
Nodex=floor(root,key);
if(x==null)
returnnull;
else
returnx.key;
}

/**
*如果给定的键key小于二叉查找树的根节点的键，那么小于等于key的最大键一定出现在根节点的左子树中
*如果给定的键key大于二叉查找树的根节点，那么只有当根节点右子树中存在大于等于key的节点时，
*小于等于key的最大键才会出现在右子树中，否则根节点就是小于等于key的最大键
*
*@paramx
*@paramkey
*@return
*/
privateNodefloor(Nodex,Keykey){
if(x==null)
returnnull;
intcmp=key.compareTo(x.key);
if(cmp==0)
returnx;
elseif(cmp<0)
returnfloor(x.left,key);
else{
Nodet=floor(x.right,key);
if(t==null)
returnx;
else
returnt;
}
}

/**
*向上取整：找出大于等于该键的最小键
*
*@paramkey
*@return
*/
publicKeyceiling(Keykey){
Nodex=ceiling(root,key);
if(x==null)
returnnull;
else
returnx.key;
}

/**
*如果给定的键key大于二叉查找树的根节点的键，那么大于等于key的最小键一定出现在根节点的右子树中
*如果给定的键key小于二叉查找树的根节点，那么只有当根节点左子树中存在大于等于key的节点时，
*大于等于key的最小键才会出现在左子树中，否则根节点就是大于等于key的最小键
*
*@paramx
*@paramkey
*@return
*/
privateNodeceiling(Nodex,Keykey){
if(x==null)
returnnull;
intcmp=key.compareTo(x.key);
if(cmp==0)
returnx;
elseif(cmp>0){
returnceiling(x.right,key);
}else{
Nodet=floor(x.left,key);
if(t==null)
returnx;
else
returnt;
}
}

/**
*选择排名为k的节点
*
*@paramk
*@return
*/
publicKeyselect(intk){
returnselect(root,k).key;
}

privateNodeselect(Nodex,intk){
if(x==null)
returnnull;
intt=size(x.left);
if(t>k)
returnselect(x.left,k);
elseif(t0)
return1+size(x.left)+rank(key,x.right);
else
returnsize(x.left);
}
/**
*删除最小键值对
*/
publicvoiddeleteMin(){
root=deleteMin(root);
}
/**
*不断深入根节点的左子树直到遇见一个空链接，然后将指向该节点的链接指向该结点的右子树
*此时已经没有任何链接指向要被删除的结点，因此它会被垃圾收集器清理掉
*@paramx
*@return
*/
privateNodedeleteMin(Nodex){
if(x.left==null)returnx.right;
x.left=deleteMin(x.left);
x.n=size(x.left)+size(x.right)+1;
returnx;
}

publicvoiddeleteMax(){
root=deleteMax(root);
}
privateNodedeleteMax(Nodex){
if(x.right==null)returnx.left;
x.right=deleteMax(x.right);
x.n=size(x.left)+size(x.right)+1;
returnx;
}

publicvoiddelete(Keykey){
root=delete(root,key);
}
privateNodedelete(Nodex,Keykey){
if(x==null)returnnull;
intcmp=key.compareTo(x.key);
if(cmp<0)x.left=delete(x.left,key);
elseif(cmp>0)x.right=delete(x.right,key);
else{
if(x.right==null)returnx.left;
if(x.left==null)returnx.right;
/**
*如果被删除节点有两个子树，将被删除节点暂记为t
*从t的右子树中选取最小的节点x，将这个节点x的左子树设为t的左子树
*这个节点x的右子树设为t的右子树中删除了最小节点的子树，这样就成功替换了t的位置
*/
Nodet=x;
x=min(t.right);
x.left=t.left;
x.right=deleteMin(t.right);
}
x.n=size(x.left)+size(x.right)+1;
returnx;
}

publicvoidprint(){
print(root);
}
privatevoidprint(Nodex){
if(x==null)return;
print(x.left);
StdOut.println(x.key);
print(x.right);
}

publicIterablekeys(){
returnkeys(min(),max());
}
publicIterablekeys(Keylo,Keyhi){
Queuequeue=newQueue();
keys(root,queue,lo,hi);
returnqueue;
}
privatevoidkeys(Nodex,Queuequeue,Keylo,Keyhi){
if(x==null)return;
intcmplo=lo.compareTo(x.key);
intcmphi=lo.compareTo(x.key);
if(cmplo<0)keys(x.left,queue,lo,hi);
if(cmplo<=0&&cmphi>=0)queue.enqueue(x.key);
if(cmphi>0)keys(x.right,queue,lo,hi);
}
}

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持毛票票。

声明：本文内容来源于网络，版权归原作者所有，内容由互联网用户自发贡献自行上传，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任。如果您发现有涉嫌版权的内容，欢迎发送邮件至：czq8825#qq.com（发邮件时，请将#更换为@）进行举报，并提供相关证据，一经查实，本站将立刻删除涉嫌侵权内容。

java二叉查找树的实现代码

热门推荐

随机推荐