package com.data.java.towtree;import java.io.IOException;/** * 二叉树 * @Title: uminton */class Node{    public int iData; //数据用作关键值    public double dData; //其他数据    public Node leftChild; //左子节点    public Node rightChild; //右子节点    public Node() {    }    public Node(int iData, double dData) {        this.iData = iData;        this.dData = dData;    }    public void displayNode(){        System.out.print("{");        System.out.print(iData);        System.out.print(", ");        System.out.print(dData);        System.out.print("} ");    }}public class Tree {    private Node root; //根节点    public Node getRoot() {        return root;    }    /**     * 查找一个数据     * @param key     * @return     */    public Node find(int key){        Node current = root;                 //把跟节点设置为当前节点        while (current.iData != key){        //循环查找            if(key < current.iData){         //如果小于就去当前树的左边子节点                current = current.leftChild; //把子节点赋给当前节点            }else {                          //如果大于就去当前树的右边子节点                current = current.rightChild;//把子节点赋给当前节点            }            if(current == null){             //到达序列的末端没有找到节点，表明他不存在，返回空                return current;            }        }        return current;                      //循环条件相等，循环结束，找到结果。    }    /**     * 添加一个数据     * @param id     * @param dd     */    public void insert(int id, double dd) {        Node newNode = new Node(id, dd);            //先创建一个新节点        if(root == null){                           //如果跟节点为空，表示树，没有数据，直接赋值给根节点            root = newNode;        }else {            Node current = root;                    //根节点赋值给当前节点，用于查找            Node parent;                            //父节点，用来存储遇到的最后一个不是null的节点，因为curent在查找的过程中会变成null，                                                    // 才能发现发现查找过得上一个节点没有子节点            while (true){                           //循环查找                parent = current;                   //用来存储遇到的最后一个不是null的节点                if (id < current.iData){            //如果小于就去当前树的左边子节点                    current = current.leftChild;                    if(current == null){            //到达序列的末端没有找到节点，表明他不存在                        parent.leftChild = newNode; //把新的节点赋值给父节点的左子节点                        return;                     //直接返回，结束循环                    }                }else {                    current = current.rightChild;                    if(current == null){                        parent.rightChild = newNode;                        return;                    }                }            }        }    }    /**     * 删除一个数据     * @param key     * @return     *     * 删除节点要考虑的三种情况     * 1，该节点是叶节点     * 2，该节点有一个子节点     * 3，该节点有二个子节点     */    public boolean delete(int key){        Node current = root;        Node parent = root;        boolean isLeftChild = true;             //记录是左节点还是右节点        while(current.iData != key){            //循环为了找到要删除的节点，循环条件如果相等就是找到了，退出循环            parent = current;                   //保存要删除的父节点            if(key < current.iData){                isLeftChild = true;                current = current.leftChild;            }else {                isLeftChild = false;                current = current.rightChild;            }            if(current == null){                //查找到末端，都没有找到，返回false                return false;            }        }        /**************************情况1开始*********************************/        if(current.leftChild == null && current.rightChild == null) {  //判断是否没有子节点，也就是该节点是叶节点            if (current == root) {              //如果是根节点，直接赋值为null                root = null;            } else if (isLeftChild) {           //判断是否是左节点                parent.leftChild = null;        //用上面保存的父节点找子节点，直接赋值为null            } else {                parent.rightChild = null;            }        /**************************情况1结束*********************************/        /**************************情况2开始*********************************/        }else if (current.rightChild == null){      //判断左边等null或右边等于null            if(current == root){                    //如果是根节点，直接赋值为null                root = current.leftChild;            }else if (isLeftChild){                 //判断是否是左节点                parent.leftChild = current.leftChild;//用上面保存的父节点找子节点，直接赋值为null            }else {                parent.rightChild = current.leftChild;            }        }else if (current.leftChild == null){       //下面同理            if(current == root){                root = current.rightChild;            }else if (isLeftChild){                parent.leftChild = current.rightChild;            }else {                parent.rightChild = current.rightChild;            }        /**************************情况2结束*********************************/        /**************************情况3开始*********************************/        }else {                                     //上面都不成立，表明该节点有两个子节点。            Node successor = getSuccessor(current); //取得后继者            if(current == root){                    //如果是根节点，直接赋值为后继者                root = successor;            }else if (isLeftChild){                 //判断是否是左节点                parent.leftChild = successor;       //用上面保存的父节点找子节点，直接赋值为后继者            }else {                parent.rightChild = successor;            }            successor.leftChild = current.leftChild;        }        /**************************情况3结束*********************************/        return true;    }    /**     * 中序遍历树     * @param localRoot     */    public void inOrder(Node localRoot){        if(localRoot != null){            inOrder(localRoot.leftChild);            System.out.println(localRoot.iData);            inOrder(localRoot.rightChild);        }    }    /**     * 查找最小值     * @return     */    public Node minNumber(){        Node current = root;        Node last = null;        while (current != null){            last = current;            current = current.leftChild;        }        return last;    }    /**     * 获取删除节点的后继者     * @param delNode     * @return     * 算法：程序找到要删除的节点的右子节点，（它的关键字值一定比要删除的节点的值大）然后转到右子节点的左子节点（若果有的话）     * 然后到这个左子节点的左子节点，以此类推，这个路径的最后一个左子节点就是要删除节点的后继者     * 若果删除节点右子节点没有左子节点，它就是后继者     */    private Node getSuccessor(Node delNode) {        Node successorParent = delNode;        Node successor = delNode;        Node current = delNode.rightChild;          //删除节点右子节点        while (current != null){            successorParent = successor;            //保留后继者的父节点            successor = current;                    //后继者            current = current.leftChild;            //循环查找左子节点        }        if(successor != delNode.rightChild){            successorParent.leftChild = successor.rightChild;            successor.rightChild = delNode.rightChild;        }        return successor;    }}class TreeApp{    public static void main(String[] args) throws IOException {        Tree treTree = new Tree();        treTree.insert(38,1.5);        treTree.insert(65,1.5);        treTree.insert(40,1.5);        treTree.insert(50,1.5);        treTree.insert(55,1.5);        treTree.insert(30,1.5);        treTree.insert(90,1.5);        treTree.insert(25,1.6);        treTree.insert(70,1.7);        treTree.insert(20,1.7);        treTree.insert(80,1.7);        treTree.delete(65);    }}

　　

最后删除有点复杂，没怎么搞懂见谅。