二叉查找树(Binary Search Tree),(又:二叉搜索树,二叉排序树)它或者是一棵空树,或者是具有下列性质的二叉树:
若它的左子树不空,则左子树上所有结点的值均小于它的根结点的值; 若它的右子树不空,则右子树上所有结点的值均大于它的根结点的值;
它的左、右子树也分别为二叉排序树。
其实说白点就是一颗二叉树满足了左子节点小于根节点元素,右子节点大于根节点元素,这样的二叉树就是二叉搜索树,二叉搜索树实现符号表,具有插入、查找的高效性,对其优化可以生成平衡二叉树,红黑树等更高效的查找和插入数据结构,是一个优秀的基础算法。
看下其数据的结构
这是一个简单的二叉搜索树结构,满足了基本的需求
class Node{
int key;
int value;
Node left,right;
// int N;
Node(int key,int value){
this.key=key;
this.value=value;
}
}
看下树中方法涉及到插入、查找、删除基本操作
class Tree{
Node root; //储存根节点
//查找指定key元素返回节点
public Node find(int key){
return null;
}
//插入元素
public void insert(int key,int value){
}
//删除元素
public void delete(int key){
}
//返回node下最小节点
public Node min(Node node){
}
//删除该节点下的最小节点
public void deleteMin(Node node){
}
//删除该节点下最大节点
public void deleteMax(Node node){
}
}
查找操作和二分查找类似,将key和节点的key比较,如果小于,那么就在Left Node节点查找,如果大于,则在Right Node节点查找,如果相等,直接返回Value。
public Node find(int key){
// 查找也是从根元素出发,找不到返回null
Node currentNode=root;
while(currentNode!=null&¤tNode.key!=key){
if(key<currentNode.key)
{
currentNode=currentNode.left;
}else
{
currentNode=currentNode.right;
}
}
return currentNode;
}
插入过程非常简单,很类似与二叉树搜索树的查找过程。当需要插入一个新结点时,从根节点开始,迭代或者递归向下移动,直到遇到一个空的指针NIL,需要插入的值即被存储在该结点位置。二叉排序树 删除
public void insert(int key,int value){
//如果根节点没有元素,此节点便为根节点
if(root==null){
root=new Node(key,value);
return;
}
//比较左右节点元素,从root开始
Node parentNode=root;//当前元素父元素
Node currentNode=root;//当前元素
while(currentNode!=null){ //一直遍历找到一个空元素为止
parentNode=currentNode;
if(key<currentNode.key){ //如果key小于该元素值,往左找,相反则往右
currentNode=currentNode.left;
}else{
currentNode=currentNode.right;
}
}
if(key<parentNode.key){ //插入元素
System.out.println(parentNode.key+"的左边可以插入"+key);
parentNode.left=new Node(key,value);
}else{
System.out.println(parentNode.key+"的右边可以插入"+key);
parentNode.right=new Node(key,value);
}
}
本文来自电脑杂谈,转载请注明本文网址:
http://www.pc-fly.com/a/jisuanjixue/article-68005-1.html
反腐倡廉支持
今天用了十几个小时就没电了