//今天分享平衡二叉树的代码（java），这个代码里主要是递归的用法重要，代码如下：

package src;

import java.util.ArrayList;
import java.util.Collection;
import java.util.NoSuchElementException;

class Binary_search_tree<E extends Comparable<E>>{
    public static class Node<E>{
        E item;
        Node<E> left;
        Node<E> right;
        Node(Node<E> left,E item,Node<E> right){
            this.left = left;
            this.item = item;
            this.right = right;
        }
    }
    public int size;
    Node<E> root;
    public int leaf;
    public int Lheight;
    public int Rheight;
    Binary_search_tree(){
        this.root = null;
        this.size = 0;
        this.leaf = 0;
        this.Lheight = 0;
        this.Rheight = 0;
    }
    public void add(E element){
        if(root==null){
            root = new Node<E>(null, element, null);
        }
        else{
            addNode(root,element);
        }
        size++;
    }
    public void addNode(Node<E> current,E element){
        if(element.compareTo(current.item)<=0){
            if(current.left==null){
                current.left = new Node<E>(null, element, null);
                this.Lheight++;
            }
            else{
                addNode(current.left,element);
            }
        }
        else{
            if(current.right==null){
                current.right = new Node<E>(null, element, null);
                this.Rheight++;
            }
            else{
                addNode(current.right,element);
            }
        }
    }
    public Node<E> getNode(Node<E> root,E element){
        if(root == null){
            return null;
        }
        if(element.equals(root.item)){
            return root;
        }
        else if(element.compareTo(root.item)<=0){
            return getNode(root.left,element);
        }
        else{
            return getNode(root.right,element);
        }
    }
    public Node<E> getParent(Node<E> current,E element){
        if (element.equals(root.item)) {
            return null;
        }
        if(element.compareTo(current.item)<=0){
            if(current.left==null){
                return null;
            }
            else if(element.equals(current.left.item)){
                return current;
            }
            else{
                return getParent(current.left,element);
            }
        }
        else{
            if(current.right==null){
                return null;
            }
            else if(element.equals(current.right.item)){
                return current;
            }
            else{
                return getParent(current.right,element);
            }
        }
    }
    public void remove(E element) {
        Node<E> node = getNode(root, element);
        if(node == null) {
            throw new NoSuchElementException();
        }
        Node<E> parent = getParent(root, element);
        if(size == 1) {
            root = null;
        } else if(node.left == null && node.right == null) {
            removeLeaf(parent, node);
        } else if(node.left == null && node.right != null) {
            if(element.compareTo(parent.item) < 0) {
                parent.left = node.right;
            } else {
                parent.right = node.right;
            }
        } else if(node.left != null && node.right == null) {
            if(element.compareTo(parent.item) < 0) {
                parent.left = node.left;
            } else {
                parent.right = node.left;
            }
        } else {
            Node<E> largest = node.left;
            if(largest.right == null) {
                node.item = largest.item;
                node.left = largest.left;
                largest = null;
            } else {
                while(largest.right != null) {
                    largest = largest.right;
                }
                Node<E> largestParent = getParent(node, largest.item);
                largestParent.right = null;
                node.item = largest.item;
            }
        }
        size--;
    }
    public void removeLeaf(Node<E> parent, Node<E> leaf) {
        E element = leaf.item;
        if(element.compareTo(parent.item) < 0) {
            parent.left = null;
        } else {
            parent.right = null;
        }
    }
    public int getLeaf(Node<E> root){
        if(root.left!=null&&root.right!=null){
            getLeaf(root.left);
            getLeaf(root.right);
        }
        else if(root.left!=null&&root.right==null){
            getLeaf(root.left);
        }
        else if(root.right!=null&&root.left==null){
            getLeaf(root.right);
        }
        else{
            this.leaf++;
        }
        return this.leaf;
    }
    public void preOrder(Collection<E> container){
        preOrderNode(root,container);
    }
    public void preOrderNode(Node<E> root,Collection<E> container){
        if(root!=null){
            container.add(root.item);
            preOrderNode(root.left,container);
            preOrderNode(root.right,container);
        }
    }
    public void inOrder(Collection<E> container) {
        inOrderNode(root, container);
    }
    public void inOrderNode(Node<E> root, Collection<E> container) {
        if(root != null) {
            inOrderNode(root.left, container);
            container.add(root.item);
            inOrderNode(root.right, container);
        }
    }
    public void postOrder(Collection<E> container) {
        postOrderNode(root, container);
    }
    public void postOrderNode(Node<E> root, Collection<E> container) {
        if(root != null) {
            postOrderNode(root.left, container);
            postOrderNode(root.right, container);
            container.add(root.item);
        }
    }
    public int getHeight(){
        return Math.max(this.Rheight, this.Lheight)+1;
    }
    public int getNodes(){
        return this.size;
    }
}

//测试类

public class Exp41 {
    public static void main(String[] args) {
        Binary_search_tree<Integer> bs = new Binary_search_tree<Integer>();
        bs.add(5);
        bs.add(1);
        bs.add(3);
        bs.add(7);
        bs.add(8);
        bs.add(2);
        System.out.println(bs.getLeaf(bs.root));
        ArrayList<Integer> ar1 = new ArrayList<>();
        bs.preOrder(ar1);
        for(int i:ar1){
            System.out.print(i);
        }
        System.out.println();
        ArrayList<Integer> ar2 = new ArrayList<>();
        bs.inOrder(ar2);
        for(int i:ar2){
            System.out.print(i);
        }
        System.out.println();
        ArrayList<Integer> ar3 = new ArrayList<>();
        bs.postOrder(ar3);
        for(int i:ar3){
            System.out.print(i);
        }
        System.out.println();
        System.out.println(bs.getHeight());
        System.out.println(bs.getNodes());
    }
}