Java实现平衡二叉树AVL

超、凢脫俗 2023-05-28 11:26 4阅读 0赞

[*点击进入尚硅谷数据结构和算法Java代码导航*][Java]

import java.util.Stack;
    
    class Node{
        
    	int data;
    	Node left;
    	Node right;
    	public Node(int data) {
        
    		this.data = data;
    	}
    }
    public class AVL {
        
    
    	Node root;
    	//添加节点
    	public void add(int value) {
        
    		this.add(value, this.root);
    	}
    	public void add(int value, Node node) {
        
    		if(this.root == null) {
        
    			this.root = new Node(value);
    		}else {
        
    			//大于放在右边
    			if(value > node.data) {
        
    				if(node.right == null) {
        
    					node.right = new Node(value);
    				}else {
        
    					add(value, node.right);
    				}
    			}else {
        //小于等于放在左边
    				if(node.left == null) {
        
    					node.left = new Node(value);
    				}else {
        
    					add(value, node.left);
    				}
    			}
    		}
    		//在添加节点时刻就进行判断旋转，注意双旋转，因为每次添加节点时都进行判断，所以双旋转只需要进行一次。
    		if(getHeight(root.right) - getHeight(root.left) > 1) {
        
    			if(getHeight(root.right.left) > getHeight(root.right.right)) {
        
    				rightRotate(root.right);
    			}
    			leftRotate(root);
    			return;
    		}
    		if(getHeight(root.left) - getHeight(root.right) > 1) {
        
    			if(getHeight(root.left.right) > getHeight(root.left.left)) {
        
    				leftRotate(root.left);
    			}
    			rightRotate(root);
    		}
    	}
    	//获取树的高度
    	public int getHeight(Node node) {
        
    		if(node == null) {
        
    			return 0;
    		}else {
        
    			//妙啊
    			return Math.max(node.left == null ? 0 : getHeight(node.left), node.right == null ? 0 : getHeight(node.right)) + 1;
    		} 
    	}
    	//左旋转
    	public void leftRotate(Node node) {
        
    		Node temp = node.right;
    		node.right = temp.left;
    		temp.left = node;
    		this.root = temp;
    	}
    	//右旋转
    	public void rightRotate(Node node) {
        
    		Node temp = node.left;
    		node.left = temp.right;
    		temp.right = node;
    		this.root = temp;
    	}
    	//中序遍历
    	public void inOrder() {
        
    		Node temp = this.root;
    		Stack<Node> stack = new Stack<Node>();
    		while(!stack.isEmpty() || temp != null) {
        
    			if(temp != null) {
        
    				stack.push(temp);
    				temp = temp.left;
    			}else {
        
    				temp = stack.pop();
    				System.out.print(temp.data + " ");
    				temp = temp.right;
    			}
    		}
    	}
    	public static void main(String[] args) {
        
    		// TODO Auto-generated method stub
    
    		int[] arr = {
        10,12,8,9,7,6};
    		AVL avl = new AVL();
    		for(int i=0; i<arr.length; i++) {
        
    			avl.add(arr[i]);
    		}
    		avl.inOrder();System.out.println();
    		System.out.println(avl.getHeight(avl.root));
    		
    		System.out.println(avl.root.data);
    	}
    }

[Java]: https://blog.csdn.net/weixin_44963741/article/details/105228982