二叉树的添加、删除、查询操作

柔情只为你懂 2022-12-08 04:15 90阅读 0赞

BinaryTree类

package tree;
    
    public class BinaryTree<Key extends Comparable<Key>,Value> {
    
    	//记录根节点
    	private Node root;
    	//记录树中元素的个数
    	private int N;
    	
    	private class Node{
    		//存储键
    		public Key key;
    		//存储值
    		private Value value;
    		//记录左子节点
    		public Node left;
    		//记录右子节点
    		public Node right;
    		
    		public Node(Key key, Value value,Node left,Node right) {
    			this.key = key;
    			this.value = value;
    			this.left = left;
    			this.right = right;
    		}
    		
    	}
    	
    	//获取树中元素的个数
    	public int size() {
    		return N;
    	}
    	
    	//向树中添加元素key-value
    	public void put(Key key, Value value) {
    		root = put(root, key, value);
    	}
    	
    	//向指定的树x中添加key-value，并返回添加元素后新的树
    	private Node put(Node x, Key key, Value value) {
    		//如果x子树为空
    		if(x == null) {
    			N++;
    			return new Node(key, value, null, null);
    		}
    		
    		//如果x子树不为空
    		//比较x节点的键key的大小：
    		
    		int cmp = key.compareTo(x.key);
    		if(cmp > 0) {
    			//如果key大于x节点的键，则继续找x节点的右子树
    			x.right = put(x.right, key,value);
    		}else if(cmp < 0) {
    			//如果key小于x节点的键，则继续找x节点的左子树
    			x.left = put(x.left, key,value);
    		}else {
    			//如果key等于x节点的键，则替换x节点的值为value即可
    			x.value = value;
    		}
    		
    		
    		return x;
    	}
    	
    	//查询树中指定key对应的value
    	public Value get(Key key) {
    		
    		return get(root,key);
    	}
    	
    	//从指定的树x中，查找key对应的值
    	public Value get(Node x, Key key) {
    		//x树为null
    		if(x == null) {
    			return null;
    		}
    		//x树不为null
    		//比较key和x节点的键的大小
    		int cmp = key.compareTo(x.key);
    		if(cmp > 0) {
    			//如果key大于x节点的键，则继续找x节点的右子树
    			return get(x.right,key);
    		}else if(cmp < 0) {
    			//如果key小于x节点的键，则继续找x节点的左子树
    			return get(x.left,key);
    			
    		}else {
    			//如果key等于x节点的键，就找到了键为key的节点，只需要返回x节点的键即可
    			return x.value;
    			
    		}
    		
    	}
    	
    	//删除树中key对应的value
    	public void delete(Key key) {
    		delete(root,key);
    	}
    	
    	//删除指定树x中的ekey 对应的value，并返回删除后的新树
    	public Node delete(Node x, Key key) {
    		
    		//x树为null
    		if(x == null) {
    			return null;
    		}
    		//x树不为null
    		int cmp = key.compareTo(x.key);
    		if(cmp > 0) {
    			//如果key大于x节点的键，则继续找x节点的右子树
    			x.right = delete(x.right,key);
    		}else if(cmp < 0) {
    			//如果key小于x节点的键，则继续找x节点的左子树
    			x.left = delete(x.left,key);
    		}else {
    			//让元素个数 -1
    			N--;
    			
    			//如果key等于x节点的键，完成真正的删除节点动作，要删除节点就是x
    			
    			//得找到右子树中最小的节点
    			if(x.right == null) { 
    				
    				return x.left;
    			}
    			if(x.left == null) {
    				
    				return x.right;
    			}
    			Node minNode = x.right;
    			while(minNode.left != null) {
    				minNode = minNode.left;
    			}
    			
    			//删除右子树中最小的节点
    			Node n = x.right;
    			//一直在右子树往左找最小的节点
    			while(n.left != null) {
    				//确认是没有子节点了，就置空
    				if(n.left.left == null) {
    					n.left = null;
    				}else {
    					n = n.left;
    				}
    			}
    			
    			//让x节点的左子树为minNode的左子树
    			minNode.left = x.left;
    			
    			//让x节点的右子树为minNode的右子树
    			minNode.right = x.right;
    			
    			//让x节点的父节点指向minNode
    			x = minNode;
    			
    			
    		}
    		return x;
    	}
    	
    	
    }

测试类：

package test;
    
    import tree.BinaryTree;
    
    public class BinaryTreeTest {
    	public static void main(String[] args) {
    		//创建二叉查找对象
    		BinaryTree<Integer, String> tree = new BinaryTree<>();
    		//测试插入
    		tree.put(20, "张三");
    		tree.put(10, "李四");
    		tree.put(8, "王五");
    		tree.put(9, "赵六");
    		tree.put(6, "小贝");
    		tree.put(16, "小黑");
    		tree.put(14, "田七");
    		tree.put(12, "刘备");
    		tree.put(17, "诸葛亮");
    		tree.put(25, "孔明");
    		tree.put(23, "孔子");
    		tree.put(26, "颜回");
    		System.out.println("插入完毕后元素的个数："+tree.size());
    		
    		//测试获取
    		System.out.println("键26对应的元素是："+tree.get(26));
    		System.out.println("键10对应的元素是："+tree.get(10));
    		
    		//测试删除
    		tree.delete(10);
    		System.out.println("删除后的元素个数："+tree.size());
    		System.out.println("删除后键10对应的元素："+tree.get(10));
    		
    		
    		
    	
    		
    	}
    	
    }

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1hlb25fQ0M_size_16_color_FFFFFF_t_70][]![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1hlb25fQ0M_size_16_color_FFFFFF_t_70 1][]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1hlb25fQ0M_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200917151727277.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1hlb25fQ0M=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1hlb25fQ0M_size_16_color_FFFFFF_t_70 1]: /images/20221123/6b0527e15bd642c89689393814f8b064.png