赞
踩
终于搞出来了!!!等以后有时间再来写详细过程。。。
import java.util.*; public class AVLTree { private TreeNode root; private class TreeNode{ int val; int height; int balance; TreeNode parent; TreeNode left; TreeNode right; public TreeNode(){} public TreeNode(int val){ this.val = val; height = 1; } } private int getHeight(TreeNode p){ if(p==null){ return 0; }else{ return p.height; } } private void left_rotate(TreeNode p){ if(p!=null){ TreeNode r = p.right; p.right = r.left; if(r.left!=null) r.left.parent = p; r.parent = p.parent; if(p.parent==null) root = r; else if(p.parent.left == p) p.parent.left = r; else p.parent.right = r; r.left = p; p.parent = r; updateNode(p); updateNode(r); } } private void right_rotate(TreeNode p){ if(p!=null){ TreeNode l = p.left; p.left = l.right; if(l.right!=null) l.right.parent=p; l.parent = p.parent; if(p.parent==null) root = l; else if(p.parent.left == p) p.parent.left = l; else p.parent.right = l; l.right = p; p.parent = l; updateNode(p); updateNode(l); } } //更新父子节点关系 private void updateChild(TreeNode parent,TreeNode root,TreeNode p){ if(parent==null){ this.root = p; }else if(parent.left == root){ parent.left = p; }else{ parent.right = p; } } //更新节点的高度和平衡因子 private void updateNode(TreeNode p){ p.height = Math.max(getHeight(p.left),getHeight(p.right))+1; p.balance = getHeight(p.left)-getHeight(p.right); } //添加一个节点 public void add(int val){ if(this.root==null){ this.root = new TreeNode(val); }else{ TreeNode p = new TreeNode(val); insert(this.root,p); } } //删除一个节点 public void delete(int val){ remove(this.root,val); } private void remove(TreeNode root,int val){ if(root==null) return ; TreeNode parent; while(root!=null){ if(root.val==val){ //如果当前节点即为要删除的节点 parent = root.parent; if(parent==null){ //首先根据parent是否为空判断是否是根节点 if(root.left == null){ //根的左儿子为空,将右儿子赋值为根节点 this.root = root.right; }else if(root.right == null){ //根的右儿子为空,将左儿子赋值为根节点 this.root = root.left; }else{ //左右子树均不为空,指定右儿子为根节点,将左子树加入到右子树中 this.root = root.right; this.root.parent = null; insert(this.root,root.left); } }else{ //如果不是根节点 if(root.left==null){ //左儿子为空,将右儿子与父节点关联 updateChild(parent,root,root.right); balance(parent); }else if(root.right==null){//右儿子为空,将左儿子与父节点关联 updateChild(parent,root,root.left); balance(parent); }else{ //左右儿子均不为空,将右儿子与父节点关联,并将左子树插入到右子树中 updateChild(parent,root,root.right); insert(root.right,root.left); balance(root.left); } } return ; }else if(val<root.val){ root = root.left; }else{ root = root.right; } } } private void insert(TreeNode root,TreeNode newNode){ if(newNode.val<root.val){ //新节点值小于root节点值,向左子树查找 if(root.left==null){ root.left = newNode; newNode.parent = root; balance(root); }else{ insert(root.left,newNode); } }else if(newNode.val>root.val){ //新节点值大于root节点值,向右子树查找 if(root.right==null){ root.right = newNode; newNode.parent = root; balance(root); }else{ insert(root.right,newNode); } } } //平衡该二叉树 private void balance(TreeNode root){ while(root!=null){ updateNode(root); if(root.balance<=-2){ if(root.right.balance==1){ //如果是右左不平衡,则先右旋 right_rotate(root.right); } left_rotate(root); }else if(root.balance>=2){ if(root.left.balance==-1){ //如果是左右不平衡,则先左旋 left_rotate(root.left); } right_rotate(root); } root = root.parent; } } public void print(){ System.out.print("Print Tree: "); levelOrder(this.root); System.out.println(); } //层次遍历算法 private void levelOrder(TreeNode root){ LinkedList<TreeNode> queue = new LinkedList<>(); queue.add(root); while(!queue.isEmpty()){ TreeNode p = queue.removeFirst(); if(p==null){ System.out.print(" @ "); }else{ System.out.print(" " + p.val + " "); queue.add(p.left); queue.add(p.right); } } } public static void main(String[] args) { AVLTree t = new AVLTree(); int arr[] = {10,20,18,5,8}; // for(int i=0;i<arr.length;i++) // { // t.add(arr[i]); // } for(int i=0;i<30;i++) { t.add(i); } t.delete(1); t.print(); } }
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。