目录
二叉搜索的定义:
节点类:
查找关键词对应的值:
非递归
递归:
查找最小关键词对应的值:
方法一:
方法二:
查找最大关键词对应的值:
方法一:
方法二:
存贮关键词对应的值:
查找关键词的前驱值:
查找关键词对应的后继值:
删除节点:
非递归:
递归:
范围
1.小于某值的范围
2.大于某值的范围
3.在区间的值
二叉搜索的定义:
1.key属性值不能重复
2.左子树所有节点的key值都小于根节点的key值
3.右子树所有节点的key值都要大于根节点的key值
节点类:
static class BSTNode{int key;//key必须能够进行大小比较 创建一个接口comparableObject value;BSTNode left;BSTNode right;public BSTNode(int key) {this.key = key;}public BSTNode(int key, Object value) {this.key = key;this.value = value;}public BSTNode(int key, Object value, BSTNode left, BSTNode right) {this.key = key;this.value = value;this.left = left;this.right = right;}}查找关键词对应的值:
非递归
public Object get(int key){BSTNode node=root;while(node!=null){if(key<node.key){node=node.left;}else if(key>node.key){node=node.right;}else{return node.value;}}return null;}递归:
public Object get(int key){return doGet(root,key);}private Object doGet(BSTNode node, int key) {if (node == null) {return null;//没找到}if (key < node.key) {return doGet(node.left, key);//向左找} else if (key > node.key) {return doGet(node.right, key);}else {return node.value;}}查找最小关键词对应的值:
由于搜索二叉树的定义可知,左子树的值比根节点小,所以找到左子树中对应的最小关键词即可。
方法一:
public Object min() {if (root == null) {return null;}BSTNode node = root;while (node.left != null) {node = node.left;}return node.value;}方法二:
public Object min() {return doMin(root);}public Object doMin(BSTNode node){if(node==null){return null;}if(node.left==null){return node.value;}return doMin(node.left);}查找最大关键词对应的值:
由于搜索二叉树的定义可知,右子树的值比根节点大,所以找到右子树中对应的最大关键词即可。
方法一:
public Object max(){return doMax(root);}public Object doMax(BSTNode node){if(node==null){return null;}if(node.right==null){return node.value;}return doMax(node.right);}方法二:
public Object max(){BSTNode node=root;while(node.right!=null){node=node.right;}return node.value;}存贮关键词对应的值:
在二叉树中能到的,进行覆盖;找不到的,进行插入
public void put(int key, Object value){BSTNode node=root;BSTNode parent = null;while(node!=null){parent=node;if(key<node.key){node=node.left;}else if(key>node.key){node=node.right;}else{//更新node.value=value;System.out.println("Updated key: " + key + ", value: " + value);return;}}//没有 插入//1.根节点if(parent==null){root=new BSTNode(key,value);System.out.println("Inserted root key: " + key + ", value: " + value);return;}//2.新节点key小于父节点的keyif(key<parent.key){parent.left=new BSTNode(key,value);System.out.println("Inserted left child of key: " + parent.key + ", key: " + key + ", value: " + value);} if(key>parent.key){//3.新节点key大于父节点的keyparent.right=new BSTNode(key,value);System.out.println("Inserted right child of key: " + parent.key + ", key: " + key + ", value: " + value);}}查找关键词的前驱值:
不是中的紧挨的那种前驱值,而是key的前驱,5的前驱是4之类的
4/ \2 7/\ / \ 1 3 6 8/5
找到的情况: 情况1.节点有左子树,此时前任是左子树的最大值 4的前驱是3 情况2.节点没有左子树,若离他最近的,自左而来的祖先是前任 ,自左而来的会执行p=p.right;ch
public Object successor(int key){BSTNode p=root;BSTNode ancestorFromLeft=null;while(p!=null){if(key<p.key){p=p.left;}else if(key>p.key){//向右找意味着自左而来ancestorFromLeft=p;p=p.right;}else{break;}}//没找都if(p==null){return null;}//找到了//情况1.节点有左子树,此时前任是左子树的最大值 4的前驱是3if(p.left!=null){return doMax(p.left); //找左子树的最大值}//情况2.节点没有左子树,若离他最近的,自左而来的祖先是前任return ancestorFromLeft!=null?ancestorFromLeft.value:null;}查找关键词对应的后继值:
public Object predecessor(int key){BSTNode p=root;BSTNode ancestorFromRight=null;while(p!=null){if(key<p.key){ancestorFromRight = p;p=p.left;}else if(key>p.key){p=p.right;}else{break;}}if(p==null){return null;}//找到了//情况1.节点有右子树,此时后任是右子树的最小值//4的后任是5if(p.right!=null){return doMin(p.right);}//情况2.节点没有右子树,若离他最近的,自右而来的祖先是后任return ancestorFromRight!=null?ancestorFromRight.value:null;}删除节点:
* 1.删除节点没有左孩子,将右孩子托给parent * 2.删除节点没有右孩子,将左孩子托给parent *3.删除节点没有左右孩子,已经被覆盖在1中,情况2中,把null托给parent * 4.删除节点有左右孩子,可以把他的后继节点(s)托给parent(sp) * 1. sp就是被删除节点,此时d与s紧绷,只需要将s托付给parent * 2.s不是被删除节点,此时d与s不相邻,此时需要将s的后代托给s,再将s托给parent*
非递归:
public void delete(int key){BSTNode p=root;BSTNode parent=null;//1.找到被删除节点while(p!=null){if(key<p.key){parent=p;p=p.left;}else if(key>p.key){parent=p;p=p.right;}else{break;}}if(p.left==null){//情况1shift(parent,p,p.right);}else if(p.right==null){//情况2shift(parent,p,p.left);}else{//情况4 能进到这,说明有左右字数//4.1 找到后继节点 后继节点要遵循二叉搜索的规则,左子树小,右子树大BSTNode s=p.right;BSTNode sParent=p;//后继父亲//找最小值while(s.left!=null){sParent=s;s=s.left;}if(sParent!=p){//4.2 删除节点与后继不相邻,处理后继的后事shift(sParent,s,s.right);//不可能有左孩子,因为要找到后继的最小值s.right=p.right;}//4.3 将后继托给被删除节点shift(parent,p,s);s.left=p.left;}}//托孤private void shift(BSTNode parent,BSTNode delete,BSTNode child){if(parent==null){root=child;}else if(delete==parent.left){parent.left=child;}else {parent.right=child;}}递归:
public Object delete(int key){ArrayList<Object> result=new ArrayList<>();//被删除节点的值root=doDelete(root,key,result);return result.isEmpty() ? null : result.get(0);}//返回剩下的孩子private BSTNode doDelete(BSTNode node, int key, ArrayList<Object> result){//起点,要删除的keyif(node==null){return null;}if(key<node.key){node.left=doDelete(node.left,key, result);return node;}if(key>node.key){node.right=doDelete(node.right,key, result);return node;}//找到了result.add(node.value);//情况1没有左孩子if(node.left==null){return node.right;}//情况2没有右孩子if(node.right==null){return node.left;}//情况3有左右孩子//1.相邻的BSTNode s=node.right;while(s.left!=null){s=s.left;}s.right=doDelete(node.right,s.key, new ArrayList<>());//起点,要删除的key 这个值不需要存入s.left=node.left;return s;}范围
1.小于某值的范围
public List<Object> less(int key){ArrayList<Object> result=new ArrayList<>();LinkedList<BSTNode> stack=new LinkedList<>();BSTNode p=root;while(p!=null||!stack.isEmpty()){if(p!=null){stack.push(p);p=p.left;}else {BSTNode pop=stack.pop();if(pop.key<key){result.add(pop.value);}else{break;}p=pop.right;}}return result;}2.大于某值的范围
public List<Object> greater(int key){ArrayList<Object> result=new ArrayList<>();LinkedList<BSTNode> stack=new LinkedList<>();BSTNode p=root;while(p!=null||!stack.isEmpty()){if(p!=null){stack.push(p);p=p.right;//先往右找的}else {BSTNode pop=stack.pop();if(pop.key>key){result.add(pop.value);}else{break;}p=pop.left;}}return result;}3.在区间的值
public List<Object> between(int min,int max){ArrayList<Object> result=new ArrayList<>();LinkedList<BSTNode> stack=new LinkedList<>();BSTNode p=root;while(p!=null||!stack.isEmpty()){if(p!=null){stack.push(p);p=p.left;}else {BSTNode pop=stack.pop();if(pop.key>=min&&pop.key<=max){result.add(pop.value);}else if(pop.key>max){ //这个是重要的结束条件break;}p=pop.right;}}return result;}
