树

二叉树

每个节点都不能有多于两个的儿子。

二叉树的五个性质

1.在二叉树的第i层上最多有2^i-1 个节点。（i>=1）

2.二叉树中如果深度为k,那么最多有2^k-1个节点。(k>=1）

3.n₀=n₂+1 n₀表示度数为0的节点 n₂表示度数为2的节点

4.在完全二叉树中，具有n个节点的完全二叉树的深度为[log₂n]+1，其中[log₂n]+1是向下取整。

5.若对含 n 个结点的完全二叉树从上到下且从左至右进行 1 至 n 的编号，则对完全二叉树中任意一个编号为 i 的结点：

(1) 若 i=1，则该结点是二叉树的根，无双亲, 否则，编号为 [i/2] 的结点为其双亲结点;

(2) 若 2i>n，则该结点无左孩子，否则，编号为 2i 的结点为其左孩子结点；

(3) 若 2i+1>n，则该结点无右孩子结点，否则，编号为2i+1 的结点为其右孩子结点。

二叉查找树

二叉查找树的性质是：对于树中的x节点，其左子树的所有项都小于x节点的值，右子树的所有项都大于x节点的值。

二叉查找树的平均深度为O(logN)

代码表示

节点类

package tree;

/**
 * Created by wuchao on 17-4-7.
 */
//定义二叉树的节点对象
public class BinaryNode implements Comparable<BinaryNode>{
    BinaryNode(int element){
        this.element = element;
    }
    BinaryNode(int element, BinaryNode nodeLeft, BinaryNode nodeRight){
        this.element = element;
        this.left = nodeLeft;
        this.right = nodeRight;
    }
    int element;
    BinaryNode left;
    BinaryNode right;
    @Override
    public int compareTo(BinaryNode node) {
        return this.element-node.element;
    }
}

查找树

package tree;

/**
 * Created by wuchao on 17-4-7.
 */
//二叉查找树
public class BinarySearchTree {
    private BinaryNode root;

    //构造方法
    public BinarySearchTree(){
        root=null;
    }
    //清空二叉树
    public void makeEmpty(){
        root=null;
    }
    //判断二叉树是否为空
    public boolean isEmpty(){
        return root==null;
    }
    //判断是否包含某个值
    public boolean contains(int value){
        return contains(value,root);
    }
    //查找最小值
    public int findMin()throws Exception{
        if(root==null)  throw new Exception("树为空！");
        return findMin(root).element;
    }
    //查找最大值
    public int findMax()throws Exception{
        if(root==null)  throw new Exception("树为空！");
        return findMax(root).element;
    }
    //插入
    public void insert(int x){
        root = insert(root,x);
    }
    //移除
    public void remove(int x){
        root = remove(root,x);
    }

    private boolean contains(int value,BinaryNode root){
        if(root==null) return false;

        if(root.element>value){
            return contains(value,root.left);
        }else if(root.element<value){
            return contains(value,root.right);
        }else{
            return true;
        }
    }

    private BinaryNode findMin(BinaryNode root){
        if(root == null) return null;
        if(root.left == null) return root;
        return findMin(root.left);
    }

    private BinaryNode findMax(BinaryNode root){
        if(root == null) return null;
        if(root.right == null) return root;
        return findMin(root.right);
    }

    private BinaryNode insert(BinaryNode root,int x){
        if(root == null) return new BinaryNode(x,null,null);

        if(x<root.element){
            root.left = insert(root.left,x);
        }else if(x>root.element){
            root.right = insert(root.right,x);
        }else{
            //如果树中有重复的值，则不操作
        }
        return root;
    }

    /*
    删除分为三种情况
    1）删除的节点是叶子
    2）删除的节点只有一个子节点
    3）删除的节点有两个子节点
    第三种情况较为复杂，删除策略是用其右子树的最小数据代替该节点的数据，并递归删除那个节点（最小数据）。
     */
    private BinaryNode remove(BinaryNode root,int x){
        if(root == null) return root;

        if(x<root.element){
            root.left = remove(root.left,x);
        }else if(x>root.element){
            root.right = remove(root.right,x);
        }else if(root.left != null && root.right !=null){
            root.element = findMin(root.right).element;
            root.right = remove(root.right,root.element);
        }else{
            root = (root.left != null)? root.left:root.right;
        }
        return root;
    }
}

AVL树（平衡树）

一棵AVL树是其每个节点的左子树和右子树的高度最多差1的二叉查找树。