參照著《數(shù)據(jù)結(jié)構(gòu)java語(yǔ)言描述》的偽碼牵寺，自己實(shí)現(xiàn)的方法細(xì)節(jié)耙考，最復(fù)雜的一個(gè)方法是remove()

package DataStructure.Tree;

public class IntTreeBag implements Cloneable {

    private Node root;

    public class Node {
        Node(int element, Node left, Node right) {
            this.element = element;
            this.left = left;
            this.right = right;
        }
        public Node getLeft() {
            return left;
        }
        public Node getRight() {
            return right;
        }
        private int element;
        private Node left;
        private Node right;

        @Override
        public String toString() {
            return String.valueOf(element);
        }
    }

    public IntTreeBag() {
        this(0);
    }

    public IntTreeBag(int rootValue) {
        root = new Node(rootValue, null, null);
    }

    public int size() {
        return size(root);
    }

    private int size(Node node) {
        if (node == null) {
            return 0;
        } else {
            return 1 + size(node.left) + size(node.right);
        }
    }
    public Node getRoot() {
        return root;
    }


    public void add(int target) {
        boolean done = false;
        Node cursor = root;

        while (!done) {
            if (target < cursor.element) {
                if (cursor.left == null) {
                    cursor.left = new Node(target, null, null);
                    done = true;
                } else {
                    cursor = cursor.left;
                }
            } else if (target > cursor.element) {
                if (cursor.right == null) {
                    cursor.right = new Node(target, null, null);
                    done = true;
                } else {
                    cursor = cursor.right;
                }
            } else {//target==cursor.element
                //查找二叉樹(shù)還是暫時(shí)不做有相同結(jié)點(diǎn)的處理。
//                if (cursor.left == null) {
//                    cursor.left = new Node(target, null, null);
//                    done = true;
//                } else {
//                    cursor = cursor.left;
//                }
                done=true;
            }
        }
    }

    /**
     * 刪除值為target的目標(biāo)結(jié)點(diǎn)抖格，巧妙地記錄下游標(biāo)結(jié)點(diǎn)的父結(jié)點(diǎn)沮协，并判斷
     * 當(dāng)前游標(biāo)在左子樹(shù)還是右子樹(shù)，然后操作游標(biāo)結(jié)點(diǎn)的父結(jié)點(diǎn)即可容易刪除目標(biāo)耘成。
     *
     * 刪除操作將目標(biāo)分成5種類(lèi)型來(lái)操作，分別是：
     * 目標(biāo)是根節(jié)點(diǎn)荷辕，目標(biāo)左右結(jié)點(diǎn)為空凿跳，目標(biāo)僅左結(jié)點(diǎn)為空，
     * 目標(biāo)僅右結(jié)點(diǎn)為空疮方，目標(biāo)左右結(jié)點(diǎn)非空
     *
     * @param target 目標(biāo)
     * @return 如果成功刪除返回true控嗜，否則返回false
     */
    public boolean remove(int target) {
        if (isEmpty()) {
            return true;
        }

        Node parentOfCursor = null;//cursor的父結(jié)點(diǎn)
        Node cursor = root;
        boolean inLeft=false;//記錄cursor是在左結(jié)點(diǎn)還是在右結(jié)點(diǎn)
        boolean done = false;

        while (!done) {
            if (cursor==null){//沒(méi)有找到target
                return false;
            }
            if (target < cursor.element) {
                parentOfCursor = cursor;
                cursor = cursor.left;
                inLeft=true;
            } else if (target > cursor.element) {
                parentOfCursor = cursor;
                cursor = cursor.right;
                inLeft=false;
            } else {//target == cursor.element
                if (cursor == root) {//cursor就是根結(jié)點(diǎn), cursor沒(méi)有向下搜索過(guò), inLeft和parentOfCursor都還是初始值
                    if (cursor.left == null) {
                        root = root.right;
                        done=true;
                    } else {//root.left!=null
                        if (root.left.right == null) {
                            root.left.right = root.right;
                            root = root.left;
                            done=true;
                        } else {
                            root.element = getRightMostNode(root.left).element;
                            removeRightMostNode(root.left);
                            done=true;
                        }
                    }
                } else if (cursor.left == null && cursor.right == null) {//左右結(jié)點(diǎn)都為空
                    if (inLeft){
                        parentOfCursor.left=null;
                        done=true;
                    }else {
                        parentOfCursor.right=null;
                        done=true;
                    }
                }else if (cursor.left == null){//左結(jié)點(diǎn)為空，右結(jié)點(diǎn)不為空
                    if (inLeft){
                        parentOfCursor.left=cursor.right;
                        done=true;
                    }else {
                        parentOfCursor.right=cursor.right;
                        done=true;
                    }
                }else if (cursor.right == null){//右結(jié)點(diǎn)為空骡显，左結(jié)點(diǎn)不為空
                    if (inLeft){
                        parentOfCursor.left=cursor.left;
                        done=true;
                    }else {
                        parentOfCursor.right=cursor.left;
                        done=true;
                    }
                }else {//左右兩個(gè)子結(jié)點(diǎn)都不為空
                    if (cursor.left.right==null){
                        cursor.left.right=cursor.right;
                        if (inLeft){
                            parentOfCursor.left=cursor.left;
                            done=true;
                        }else {
                            parentOfCursor.right=cursor.left;
                            done=true;
                        }
                    }else {
                        cursor.element=getRightMostNode(cursor.left).element;
                        removeRightMostNode(cursor.left);
                        done=true;
                    }
                }
            }
        }
        return true;//能跳出while循環(huán)就是done=true疆栏，成功刪除了曾掂。

    }

    public boolean isEmpty() {
        return root == null;
    }

    /**
     * remove the most left node of the rootNode
     *
     * @param rootNode .
     * @return return true if remove target. return
     * false if the left of rootNode is null.
     */
    public boolean removeLeftMostNode(Node rootNode) {
        Node c = rootNode;
        Node parentOfc = null;
        while (c.left != null) {
            parentOfc = c;
            c = c.left;
        }
        if (parentOfc != null) {//rootNode.left!=null
            parentOfc.left = null;
            return true;
        } else {
            //rootNode.left==null.
            return false;
        }
    }

    public boolean removeRightMostNode(Node rootNode) {
        Node c = rootNode;
        Node parentOfc = null;
        while (c.left != null) {
            parentOfc = c;
            c = c.right;
        }
        if (parentOfc != null) {
            parentOfc.right = null;
            return true;
        } else {
            return false;
        }
    }

    public Node getLeftMostNode(Node rootNode) {
        Node cursor = rootNode;
        while (cursor.left != null) {
            cursor = cursor.left;
        }
        return cursor;
    }

    public Node getRightMostNode(Node rootNode) {
        Node cursor = rootNode;
        while (cursor.right != null) {
            cursor = cursor.right;
        }
        return cursor;
    }

    public int countOccurences(int target) {
        int count = 0;
        Node cursor = root;
        while (cursor != null) {
            if (target < cursor.element) {
                cursor = cursor.left;
            } else if (target > cursor.element) {
                cursor = cursor.right;
            } else if (target == cursor.element) {
                cursor = cursor.left;
                count++;
            }
        }
        return count;
    }

    @Override
    protected Object clone() throws CloneNotSupportedException {
        super.clone();
        return treeCopy(root);
    }

    //深度拷貝一個(gè)樹(shù)，返回拷貝的全新的樹(shù)的根節(jié)點(diǎn)壁顶。
    private Node treeCopy(Node node) {
        Node left, right;
        if (node == null) {
            return null;
        } else {
            left = treeCopy(node.left);
            right = treeCopy(node.right);
            return new Node(node.element, left, right);
        }
    }

    /**
     * 先序遍歷打印
     * @param node 根節(jié)點(diǎn)
     */
    public void preorderPrint(Node node){
        if (node!=null){
            System.out.println(node.element);
            if (node.left!=null){
                preorderPrint(node.left);
            }
            if (node.right!=null){
                preorderPrint(node.right);
            }
        }
    }

    /**
     * 添加一棵樹(shù)珠洗，傳入根結(jié)點(diǎn)即可
     * 因?yàn)閮?nèi)部調(diào)用了add()，因此會(huì)過(guò)濾掉相同element的結(jié)點(diǎn)若专。
     * @param node root of the tree to be added
     */
    public void addAll(Node node){
        if (node!=null){
            this.add(node.element);
            if (node.left!=null){
                addAll(node.left);
            }
            if (node.right!=null){
                addAll(node.right);
            }
        }
    }
    public void addMany(int...elements){
        for (int i=0;i<elements.length;i++){
            add(elements[i]);
        }
    }

    /**
     * 按從小到大的順序打印许蓖，其實(shí)是中序遍歷
     * @param node 根節(jié)點(diǎn)
     */
    public void printInSequence(Node node){
        if (node!=null){
            if (node.left!=null){
                printInSequence(node.left);
            }
            System.out.print(node.element+" ");
            if (node.right!=null){
                printInSequence(node.right);
            }
        }
    }

    /**
     * 倒序打印，即從大到小打印樹(shù)调衰，也是中序遍歷膊爪，
     * 不過(guò)是先右結(jié)點(diǎn)，根節(jié)點(diǎn)嚎莉，再左結(jié)點(diǎn)
     * @param node
     */
    public void printInReverseSequence(Node node){
        if (node!=null){
            if (node.right!=null){
                printInReverseSequence(node.right);
            }
            System.out.print(node.element+" ");
            if (node.left!=null){
                printInReverseSequence(node.left);
            }
        }
    }



}