package avlTree;
import java.util.LinkedList;
/**
* avl树（平衡二叉树）
* @author Administrator
*
*/
public class AvlTree {
private Node<Integer> head=null;
/**
* 返回较大的值
* @param l
* @param r
* @return
*/
public int max(int l, int r){
return (l > r ? l : r);
}
/**
* 获取树高度
* @param n
* @return
*/
public int hight(Node<Integer> n) {
if(n==null)
return -1;
else
return n.high;
}
/**
* 整个树是右旋的单旋转
* @param head
* @return
*/
public Node<Integer> singleRotateRight(Node<Integer> head){
Node<Integer> tmp = head.left;
head.left = tmp.right;
tmp.right = head; //旋转后深度随之变化，需要修改深度
head.high = max(hight(head.left), hight(head.right)) + 1;
tmp.high = max(hight(tmp.left), hight(tmp.right)) + 1;
return tmp;//返回新的子树根节点
}
/**
* 整个树是左旋的单旋转
* @param head
* @return
*/
public Node<Integer> singleRotateLeft(Node<Integer> head){
Node<Integer> tmp = head.right;
head.right = tmp.left;
tmp.left = head;
head.high = max(hight(head.left), hight(head.right)) + 1;
tmp.high = max(hight(tmp.left), hight(tmp.right)) + 1;
return tmp;
}
/**
* 整个树是右旋的双旋转
* @param head
* @return
*/
public Node<Integer> doubleRotateRight(Node<Integer> head){
head.left = singleRotateLeft(head.left);
return singleRotateRight(head);//再将整个树左旋
}
/**
* 整个树是左旋的双旋转
* @param head
* @return
*/
public Node<Integer> doubleRotateLeft(Node<Integer> head){
head.right = singleRotateRight(head.right);
return singleRotateLeft(head);//再将整个树右旋
}
/**
* 先根据二叉排序树规则插入，插完后进行平衡判断（递归法）
* @param head
* @param newnode
* @return
*/
private Node<Integer> insert_node(Node<Integer> head, Node<Integer> newnode){
Node<Integer> tmp = head;
if(head==null){
head=newnode;
return newnode;
}else{
if(tmp.getE() > newnode.getE()){
tmp.left = insert_node(tmp.left, newnode);//递归向左子树插入
//旋转
if(hight(tmp.left) - hight(tmp.right) == 2){
if(tmp.left.getE() > newnode.getE())//插到左子树左边，右旋(单旋转)
tmp = singleRotateRight(tmp);
else//插到左子树右边，左子树先左旋整个树再右旋(双旋转)
tmp = doubleRotateRight(tmp);
}
}else if(tmp.getE() < newnode.getE()){
tmp.right = insert_node(tmp.right, newnode);//递归向右子树中插入
//旋转
if(hight(tmp.right) - hight(tmp.left) == 2){
if(tmp.right.getE() < newnode.getE())//插到右子树右边，左旋(单旋转)
tmp = singleRotateLeft(tmp);
else//插到右子树左边，右子树先右旋整个树再左旋(双旋转)
tmp = doubleRotateLeft(tmp);
}
}
}
tmp.high = max(hight(tmp.left), hight(tmp.right)) + 1;
return tmp;
}
/**
* 添加节点
* @param data
*/
public void add(int data){
Node<Integer> n=new Node<Integer>(data);
if(head==null){
head=n;
}else{
head=insert_node(head,n);
}
}
/**
* 先序遍历（递归法）
*/
public void preErgodic(){
pre(head);
System.out.println();
}
private void pre(Node<Integer> n){
if(n==null){
return;
}
System.out.print(n.getE()+" ");
pre(n.left);
pre(n.right);
}
/**
* 层级遍历
*/
public void cengDis() {
Node<Integer> p=this.head;
LinkedList<Node<Integer>> stack=new LinkedList<>();
LinkedList<Node<Integer>> dui=new LinkedList<>();
PrintfTree tree = null;
dui.add(p);
while(true){
Node<Integer> f=null;
if(dui.size()>0) {
f=dui.removeFirst();
}
if(f==null) {
Node<Integer> d=null;
if(stack.size()>0) {
d=stack.removeFirst();
}
if(d==null) {
tree.show();
return ;
}else {
dui.addLast(d);
while(true) {
d=null;
if(stack.size()>0) {
d=stack.removeFirst();
}
if(d==null) {
break;
}else {
dui.addLast(d);
}
}
}
}else {
if(tree==null) {
tree=new PrintfTree(""+f.getE()+"("+f.high+")");
}else {
tree.add(new PrintfTree(""+f.getE()+"("+f.high+")"));
}
Node<Integer> left=f.left;
if(left!=null) {
stack.addLast(left);
}
Node<Integer> right=f.right;
if(right!=null) {
stack.addLast(right);
}
}
}
}
/**
* 删除节点
* @param data
*/
public void del(int data){
Node<Integer> n=new Node<Integer>(data);
if(head!=null){
head=remove(head,n);
}
}
/**
* 删除节点（递归）
* @param tree
* @param z
* @return
*/
private Node<Integer> remove(Node<Integer> tree, Node<Integer> z) {
// 根为空 或者 没有要删除的节点，直接返回null。
if (tree==null || z==null)
return null;
int cmp = z.getE()-tree.getE();
if (cmp < 0) { // 待删除的节点在"tree的左子树"中
tree.left = remove(tree.left, z);
// 删除节点后，若AVL树失去平衡，则进行相应的调节。
if (hight(tree.right) - hight(tree.left) == 2) {
Node<Integer> r = tree.right;
if (hight(r.left) > hight(r.right))
tree = doubleRotateLeft(tree);
else
tree = singleRotateLeft(tree);
}
} else if (cmp > 0) { // 待删除的节点在"tree的右子树"中
tree.right = remove(tree.right, z);
// 删除节点后，若AVL树失去平衡，则进行相应的调节。
if (hight(tree.left) - hight(tree.right) == 2) {
Node<Integer> l = tree.left;
if (hight(l.right) > hight(l.left))
tree = doubleRotateRight(tree);
else
tree = singleRotateRight(tree);
}
} else { // tree是对应要删除的节点。
// tree的左右孩子都非空
if ((tree.left!=null) && (tree.right!=null)) {
if (hight(tree.left) > hight(tree.right)) {
// 如果tree的左子树比右子树高；
// 则(01)找出tree的左子树中的最大节点
// (02)将该最大节点的值赋值给tree。
// (03)删除该最大节点。
// 这类似于用"tree的左子树中最大节点"做"tree"的替身；
// 采用这种方式的好处是：删除"tree的左子树中最大节点"之后，AVL树仍然是平衡的。
Node<Integer> max = maximum(tree.left);
tree.setE(max.getE());
tree.left = remove(tree.left, max);
} else {
// 如果tree的左子树不比右子树高(即它们相等，或右子树比左子树高1)
// 则(01)找出tree的右子树中的最小节点
// (02)将该最小节点的值赋值给tree。
// (03)删除该最小节点。
// 这类似于用"tree的右子树中最小节点"做"tree"的替身；
// 采用这种方式的好处是：删除"tree的右子树中最小节点"之后，AVL树仍然是平衡的。
Node<Integer> min = minimum(tree.right);
tree.setE(min.getE());
tree.right = remove(tree.right, min);
}
} else {
Node<Integer> tmp = tree;
tree = (tree.left!=null) ? tree.left : tree.right;
tmp = null;
}
}
return tree;
}
/*
* 查找最小结点：前驱节点
*/
private Node<Integer> minimum(Node<Integer> tree) {
if (tree == null)
return null;
while(tree.left != null)
tree = tree.left;
return tree;
}
public Integer minimum() {
Node<Integer> p = minimum(head);
if (p != null)
return p.getE();
return null;
}
/*
* 查找最大结点：后继节点
*/
private Node<Integer> maximum(Node<Integer> tree) {
if (tree == null)
return null;
while(tree.right != null)
tree = tree.right;
return tree;
}
public Integer maximum() {
Node<Integer> p = maximum(head);
if (p != null)
return p.getE();
return null;
}
}
package avlTree;
public class PrintfTree
{
private String v;
private PrintfTree l;
private PrintfTree r;
public PrintfTree(String v){
this.v = v;
}
public void add(PrintfTree the){
if(new Integer(the.v.substring(0,the.v.lastIndexOf("("))) < new Integer(v.substring(0,v.lastIndexOf("(")))){
if(l==null) l = the;
else l.add(the);
}
else{
if(r==null) r = the;
else r.add(the);
}
}
public int getHeight(){
int h = 2;
int hl = l==null? 0 : l.getHeight();
int hr = r==null? 0 : r.getHeight();
return h + Math.max(hl,hr);
}
public int getWidth(){
int w = (""+v).length();
if(l!=null) w += l.getWidth();
if(r!=null) w += r.getWidth();
return w;
}
public void show(){
char[][] buf = new char[getHeight()][getWidth()];
printInBuf(buf, 0, 0);
showBuf(buf);
}
private void showBuf(char[][] x){
for(int i=0; i<x.length; i++){
for(int j=0; j<x[i].length; j++)
System.out.print(x[i][j]==0? ' ':x[i][j]);
System.out.println();
}
}
private void printInBuf(char[][] buf, int x, int y){
String sv = "" + v;
int p1 = l==null? x : l.getRootPos(x);
int p2 = getRootPos(x);
int p3 = r==null? p2 : r.getRootPos(p2+sv.length());
buf[y][p2] = '|';
for(int i=p1; i<=p3; i++) buf[y+1][i]='-';
for(int i=0; i<sv.length(); i++) buf[y+1][p2+i]=sv.charAt(i);
if(p1<p2) buf[y+1][p1] = '/';
if(p3>p2) buf[y+1][p3] = '\\';
if(l!=null) l.printInBuf(buf,x,y+2);
if(r!=null) r.printInBuf(buf,p2+sv.length(),y+2);
}
private int getRootPos(int x){
return l==null? x : x + l.getWidth();
}
}
package avlTree;
public class Node<E> {
private E e;//数据
public Node<E> left;//左子树
public Node<E> right;//右子树
public int high;//树高度
public E getE() {
return e;
}
public void setE(E e) {
this.e = e;
}
public Node<E> getLeft() {
return left;
}
public void setLeft(Node<E> left) {
this.left = left;
}
public Node<E> getRight() {
return right;
}
public void setRight(Node<E> right) {
this.right = right;
}
public int getHigh() {
return high;
}
public void setHigh(int high) {
this.high = high;
}
public Node(E e) {
super();
this.e = e;
this.high=0;
}
public Node() {
super();
// TODO Auto-generated constructor stub
this.high=0;
}
}
package avlTree;
public class TestMain {
public static void main(String[] args) {
AvlTree avl=new AvlTree();
avl.add(1);
avl.add(2);
avl.add(3);
avl.add(4);
avl.add(5);
avl.add(6);
avl.add(7);
avl.add(8);
avl.add(9);
avl.cengDis();
avl.del(4);
avl.cengDis();
}
}
