JAVA 밸 런 스 이 진 트 리 구현

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;

/**
 * @author zhouhang
 */
public class BalenceBinaryTree {
    private int size;
    private Node root;


    public BalenceBinaryTree() {
        this.size = 0;
    }

    public int getSize() {
        return size;
    }

    public Node getRoot() {
        return root;
    }


    /**
     *         
     *
     * @param root
     */
    public void firstTraversal(Node root) {
        System.out.print(root.getValue());
        if (root.getLeft() != null) {
            firstTraversal(root.getLeft());
        }
        if (root.getRight() != null) {
            firstTraversal(root.getRight());
        }
    }

    /**
     *         
     *
     * @param root
     */
    public void midTraversal(Node root) {
        if (root.getLeft() != null) {
            midTraversal(root.getLeft());
        }
        System.out.print(root.getValue());
        if (root.getRight() != null) {
            midTraversal(root.getRight());
        }
    }

    /**
     *         
     *
     * @param root
     */
    public void lastTraversal(Node root) {
        if (root.getLeft() != null) {
            lastTraversal(root.getLeft());
        }
        if (root.getRight() != null) {
            lastTraversal(root.getRight());
        }
        System.out.print(root.getValue());
    }

    /**
     *         
     *
     * @param value      
     * @param node        
     * @return           
     */
    public Node append(int value, Node node) {
        if (size == 0) {
            size++;
            root = new Node(value);
            return root;
        }
        if (node == null) {
            size++;
            return new Node(value);
        }
        if (value < node.getValue()) {
            //       
            node.setLeft(append(value, node.getLeft()));
        } else if (value > node.getValue()) {
            //       
            node.setRight(append(value, node.getRight()));
        } else {//         
            System.out.println("     ，    ");
            return node;
        }
        return rotate(node);
    }

    /**
     *             
     *
     * @param value      
     * @return
     */
    public Node find(int value) {
        Node temp = root;
        if (size == 0) {
            return null;
        }
        while (true) {
            if (value < temp.getValue()) {
                if (temp.getLeft() == null) {
                    return null;
                } else {
                    temp = temp.getLeft();
                }
            } else if (value == temp.getValue()) {
                return temp;
            } else if (value > temp.getValue()) {
                if (temp.getRight() == null) {
                    return null;
                } else {
                    temp = temp.getRight();
                }
            }
        }
    }

    /**
     *        1
     *
     * @return      
     */
    public int depth(int value) {
        if (size == 0) {
            return 0;
        }
        Node temp = root;
        int depth = 1;//          
        while (true) {
            if (value == temp.getValue()) {
                return depth;
            } else if (value < temp.getValue()) {
                if (temp.getLeft() == null) {
                    System.out.println("     ");
                    return 0;
                } else {
                    depth++;
                    temp = temp.getLeft();
                }
            } else if (value > temp.getValue()) {
                if (temp.getRight() == null) {
                    System.out.println("     ");
                    return 0;
                } else {
                    depth++;
                    temp = temp.getRight();
                }
            }
        }
    }

    /**
     *        
     *
     * @param value
     * @return
     */
    public void printTree() {
        ArrayList<Node> list = new ArrayList<Node>();
        if (root == null) {
            System.out.println("     ");
            return;
        }
        Queue<Node> queue = new LinkedList<Node>();
        queue.offer(root);//    
        while (!queue.isEmpty()) {
            Node treeNode = queue.poll();//     
            if (treeNode.getLeft() != null) {
                queue.offer(treeNode.getLeft());//      
            }
            if (treeNode.getRight() != null) {
                queue.offer(treeNode.getRight());//      
            }
            list.add(treeNode);
        }
        for (int i = 0; i < size; i++) {
            System.out.print(list.get(i).getValue());
            System.out.print(" ");
            if (size >= i + 2 && depth(list.get(i).getValue()) != depth(list.get(i + 1).getValue())) {
                System.out.println();
            }
        }
        System.out.println();
    }


    /**
     *              ，    
     *                ，          
     *
     * @return
     */
    public Node leftRotate(Node node) {
        Node right = node.getRight();
        node.setRight(right.getLeft());
        right.setLeft(node);
        node.setHeight(Math.max(height(node.getLeft()), height(node.getRight())) + 1);
        right.setHeight(Math.max(height(right.getLeft()), height(right.getRight())) + 1);
        if(node==root){
            root=right;
        }
        return right;
    }

    /**
     *              ，    
     *                ，          
     *
     * @return
     */
    public Node rightRotate(Node node) {
        Node left = node.getLeft();
        node.setLeft(left.getRight());
        left.setRight(node);
        node.setHeight(Math.max(height(node.getLeft()), height(node.getRight())) + 1);
        left.setHeight(Math.max(height(left.getLeft()), height(left.getRight())) + 1);
        if(node==root){
            root=left;
        }
        return left;
    }


    
    /**
     *   
     *
     * @param node
     * @return
     */
    public Node rotate(Node node) {
        if (node == null) {
            return null;
        }

        //        
        if (height(node.getLeft()) > height(node.getRight()) + 1) {//        
            if (height(node.getLeft().getLeft()) >= height(node.getLeft().getRight())) {//            
                node = rightRotate(node);//     
            } else {//            
                Node temp = leftRotate(node.getLeft());//    
                node.setLeft(temp);//    
                node=rightRotate(node);//     
            }
        } else if (height(node.getRight()) > height(node.getLeft()) + 1) {//        
            if (height(node.getRight().getRight()) >= height(node.getRight().getLeft())) {//            
                node = leftRotate(node);//     
            } else {
                Node temp = rightRotate(node.getRight());//    
                node.setRight(temp);//    
                node=leftRotate(node);//     
            }
        }else{//              
            node.setHeight(Math.max(height(node.getLeft()), height(node.getRight())) + 1);
        }

        return node;
    }


    /**
     *         1
     *
     * @return      
     */
    public int height(Node node) {
        return node == null ? -1 : node.getHeight();
    }

    /**
     *   
     *
     * @param args
     */
    public static void main(String[] args) {
        BalenceBinaryTree bt = new BalenceBinaryTree();
        bt.append(9, null);
        bt.append(8, bt.getRoot());
        bt.append(3, bt.getRoot());
        bt.append(4,bt.getRoot());
        bt.append(5,bt.getRoot());
        bt.append(7,bt.getRoot());
        bt.append(5,bt.getRoot());
        bt.append(5,bt.getRoot());
        bt.append(5,bt.getRoot());
        bt.append(6,bt.getRoot());//BUG
        bt.append(1,bt.getRoot());
        bt.append(2,bt.getRoot());
        bt.append(5,bt.getRoot());
        bt.append(0,bt.getRoot());
        bt.append(10,bt.getRoot());
        bt.append(11,bt.getRoot());
        bt.append(12,bt.getRoot());
        bt.append(13,bt.getRoot());
        bt.append(14,bt.getRoot());
        bt.append(15,bt.getRoot());
        bt.append(16,bt.getRoot());
        bt.append(17,bt.getRoot());
        bt.firstTraversal(bt.getRoot());
        System.out.println();
        bt.midTraversal(bt.getRoot());
        System.out.println();
        bt.lastTraversal(bt.getRoot());
        System.out.println();
        bt.printTree();
        System.out.println("    " + bt.height(bt.getRoot()));

    }
}

/**
 * @author zhouhang
 */
public class Node {

    private Node left;
    private Node right;
    private int value;
    private int height;

    public int getHeight() {
        return height;
    }

    public void setHeight(int height) {
        this.height = height;
    }

    public Node(int value) {
        this.value = value;
    }

    public Node getLeft() {
        return left;
    }

    public void setLeft(Node left) {
        this.left = left;
    }

    public Node getRight() {
        return right;
    }

    public void setRight(Node right) {
        this.right = right;
    }

    public int getValue() {
        return value;
    }

    public void setValue(int value) {
        this.value = value;
    }

}