java操作二叉树

布满荆棘的人生 2023-10-18 14:06 85阅读 0赞

下面聊聊二叉树的使用，二叉树的基本理论想必大家都很明白了，直接上代码，

1、首先是一个节点Node，这个节点有下面几个属性，数据项，以及对左右子节点的引用，

public class Node {
    
    	// 数据项
    	public long data;
    	
    	private String sData;
    	// 左子节点
    	public Node leftChild;
    	// 右子节点
    	public Node rightChild;
    
    	/**
    	 * 构造方法
    	 * 
    	 * @param data
    	 */
    	public Node(long data,String sData) {
    		this.data = data;
    		this.sData = sData;
    	}
    
    }

2、操作二叉树的类，

public class Tree {
    
    	// 定义根节点
    	public Node root;
    
    	/**
    	 * 插入节点
    	 * 
    	 * @param value
    	 */
    	public void insert(long value,String sValue) {
    		
    		// 封装节点
    		Node newNode = new Node(value,sValue);
    		// 引用当前节点
    		Node current = root;
    		// 引用父节点
    		Node parent;
    		// 如果root为null，也就是第一插入的时候
    		if (root == null) {
    			root = newNode;
    			return;
    		} else {
    			while (true) {
    				// 父节点指向当前节点
    				parent = current;
    				// 如果当前指向的节点数据比插入的要大,则向左走
    				if (current.data > value) {
    					current = current.leftChild;
    					if (current == null) {
    						parent.leftChild = newNode;
    						return;
    					}
    				} else {
    					current = current.rightChild;
    					if (current == null) {
    						parent.rightChild = newNode;
    						return;
    					}
    				}
    			}
    		}
    	}
    
    	/**
    	 * 查找一个节点
    	 * @param value
    	 * @return
    	 */
    	public Node find(long value) {
    		Node current = root;
    		while(value != current.data){
    			if(value > current.data){
    				current = current.rightChild;
    			}else{
    				current = current.leftChild;
    			}
    			if(current == null){
    				return null;
    			}
    		}
    		return current;
    	}
    	
    	/**
    	 * 前序遍历，从根节点开始，每次遍历都从左子树开始一直到最后
    	 * @param currNode
    	 */
    	public void frontOrder(Node currNode){
    		if(currNode != null){
    			System.out.println(currNode.data + " ," + currNode.sData);
    			frontOrder(currNode.leftChild);
    			frontOrder(currNode.rightChild);
    		}
    	}
    
    	/**
    	 * 中序遍历    顺序：左子树  ---》 根节点 ---》右子树
    	 * @param currNode
    	 */
    	public void centOrder(Node currNode){
    		if(currNode != null){
    			frontOrder(currNode.leftChild);
    			System.out.println(currNode.data + " ," + currNode.sData);
    			frontOrder(currNode.rightChild);
    		}
    	}
    	
    	/**
    	 * 后序遍历    顺序：左子树  ---》 右子树 ---》根节点
    	 * @param currNode
    	 */
    	public void afterOrder(Node currNode){
    		if(currNode != null){
    			frontOrder(currNode.leftChild);
    			frontOrder(currNode.rightChild);
    			System.out.println(currNode.data + " ," + currNode.sData);
    		}
    	}
    	
    }

测试类：

public class TestTree {
    	public static void main(String[] args) {
    		Tree tree = new Tree();
    		
    		tree.insert(10,"james");
    		tree.insert(20,"kobe");
    		tree.insert(15,"maikeer");
    		tree.insert(3,"maidi");
    		
    		/*System.out.println(tree.root.data);
    		System.out.println(tree.root.leftChild.data);
    		System.out.println(tree.root.rightChild.data);*/
    		
    		System.out.println("=================");
    		Node node = tree.find(3);
    		
    		System.out.println(node.data);
    		
    	}
    }
    
    /**
    	 * 删除一个节点，分为4种情况
    	 * 1、删除的节点为叶子节点
    	 * 2、删除的节点只有左子节点
    	 * 3、删除的节点只有右子节点
    	 * 4、删除的节点左右节点都存在， ----》》需要通过中序后继查找可替换的那个值
    	 * @param value
    	 * @return
    	 */
    	public boolean delete(long value) {
    		//引用当前节点，从根节点开始
    		Node current = root;
    		//当前节点的父节点
    		Node parent = root;
    		boolean isLeftChild = true;
    		while(current.data != value){
    			parent = current;
    			if(current.data > value){ //从当前节点的左子节点开始找
    				current = current.leftChild;
    				isLeftChild = true;
    			}else{
    				current = current.rightChild;
    				isLeftChild = false;
    			}
    			//如果都没有找到
    			if(current == null){
    				return false;
    			}
    		}
    		
    		//执行删除操作，当前没有叶子节点的情况下的删除
    		if(current.leftChild == null && current.rightChild == null){
    			if(current == root){
    				root = null;
    			}else if(isLeftChild){ //如果是左子节点
    				parent.leftChild = null;
    			}else{
    				parent.rightChild = null;
    			}
    		}
    		
    		//如果要删除的节点的左子树节点存在
    		else if(current.leftChild != null && current.rightChild == null ){
    			if(current == root){
    				root = current.leftChild;
    			}else if(isLeftChild){ 
    				parent.leftChild = current.leftChild;
    			}else{
    				parent.rightChild = current.leftChild;
    			}
    		}
    		//如果要删除的节点的右子树节点存在
    		else if(current.leftChild == null && current.rightChild != null){
    			if(current == root){
    				root = current.rightChild;
    			}else if(isLeftChild){
    				parent.leftChild = current.rightChild;
    			}else{
    				parent.rightChild = current.rightChild;
    			}
    			//如果要删除的节点的左右节点都存在
    		}else{
    			Node succesor = deleteNode(current);
    			if(current == root){
    				root = succesor;
    			}else if(isLeftChild){
    				parent.leftChild = succesor;
    			}else{
    				parent.rightChild = succesor;
    			}
    			succesor.leftChild = current.leftChild;
    		}
    		
    		return true;
    
    	}
    
    //通过中序遍历获取可以替换的节点
    	public Node deleteNode(Node deleteNode){
    		
    		Node succesor = deleteNode;
    		Node succesorParent = deleteNode;
    		Node current = deleteNode.rightChild;
    		while(current != null){
    			succesorParent = succesor;
    			succesor = current;
    			current = current.leftChild;
    		}
    		
    		if(succesor != deleteNode.rightChild){
    			succesorParent.leftChild = succesor.rightChild;
    			succesor.rightChild = deleteNode.rightChild;
    		}
    		
    		return succesor;
    	}

未完待续…