두 갈래 찾기 트 리

private class TreeNode {  
        private int key;  
        private TreeNode leftChild;
        private TreeNode rightChild;
        private TreeNode parent;
        public TreeNode(int key, TreeNode leftChild, TreeNode rightChild,  
                TreeNode parent) {  
            this.key = key;  
            this.leftChild = leftChild;  
            this.rightChild = rightChild;  
            this.parent = parent;  
        }
        public int getKey() {  
            return key;  
        }
        public String toString() {  
            String leftkey = (leftChild == null ? "" : String  
                    .valueOf(leftChild.key));  
            String rightkey = (rightChild == null ? "" : String  
                    .valueOf(rightChild.key));  
            return "(" + leftkey + " , " + key + " , " + rightkey + ")";  
        }
    } 

    /**
     *         
     * */
    public TreeNode search(int key) {
        TreeNode pNode = root;
        while(pNode != null && pNode.key != key) {
            if(pNode.key > key) {
                pNode = pNode.leftChild;
            } else {
                pNode = pNode.rightChild;
            }
        }
        return pNode;
    }
    /**
     *          
     * @throws Exception 
     * */
    public TreeNode minKeyTreeNode(TreeNode node) throws Exception {
        if(node == null) {
            throw new Exception("   ");
        }
        TreeNode pNode = node;
        while(pNode.leftChild != null) {
            pNode = pNode.leftChild;
        }
        return pNode;
    }
    /**
     *           
     * @throws Exception 
     * */
    public TreeNode maxKeyTreeNode(TreeNode node) throws Exception {
        if(node == null) {
            throw new Exception("   ");
        }
        TreeNode pNode = node;
        while(pNode.rightChild != null) {
            pNode = pNode.rightChild;
        }
        return pNode;
    }
    /**
     *                      
     *      ：1)          ，            
     * 2)        ，               ，        
     * 3)        ，          ，         ，                ，                  。
     *           ，             ，     。
     * */
    public TreeNode successorInOrder(TreeNode node) throws Exception {
        if(node == null) {
            return null;
        }
        //             ，                    
        if(node.rightChild != null) {
            return minKeyTreeNode(node.rightChild);
        }
        TreeNode parentNode = node.parent;
        while (parentNode != null && node == parentNode.rightChild) {  
            node = parentNode;  
            parentNode = parentNode.parent;  
        }  
        return parentNode;
    }
    /**
     *                  
     *   x    ，                 
     * x    ， x         ， x           
     * x    ，x         ， x      x             ，                 
     * */
    public TreeNode presuccessor(TreeNode node) {
        if(node == null) {
            return null;
        }
        if(node.leftChild != null) {
            return maxKeyTreeNode(node.leftChild);
        }
        TreeNode parentNode = node.parent;
        while(parentNode != null && node == parentNode.leftChild) {
            node = parentNode;
            parentNode = parentNode.parent;
        }
        return parentNode;
    }

    /**
     *                 
     * */
    public void insert(int key) {
        TreeNode parentNode = null;
        TreeNode newNode =  new TreeNode(key, null, null, null);
        TreeNode pNode = root;
        if (root == null) {
            root = newNode;
            return ;
        }
        while(pNode != null) {
            parentNode = pNode;
            if(key < pNode.key) {
                pNode = pNode.leftChild;
            } else if(key > pNode.key) {
                pNode = pNode.rightChild;
            } else {
                return ; //                  ，  
            }
        }
        if(key < parentNode.key) {
            parentNode.leftChild = newNode;
            newNode.parent = parentNode;
        } else {
            parentNode.rightChild = newNode;
            newNode.parent = parentNode;
        }
    }

    /**
     *     
     * @throws Exception 
     * */
    public void delete(int key) throws Exception {
        TreeNode pNode = search(key);
        if(pNode == null) {
            throw new Exception("            ");
        }
        delete(pNode);
    }
    /**
     *               
     *     ：               
     * @throws Exception 
     * */
    public void delete(TreeNode pNode) throws Exception {
        if(pNode == null) {
            return ;
        }
        if(pNode.leftChild == null && pNode.rightChild == null) {
            TreeNode parentNode = pNode.parent;
            if(parentNode == parentNode.leftChild) {
                parentNode.leftChild = null;
            } else {
                parentNode.rightChild = null;
            }
            return ;
        }
        if(pNode.leftChild == null && pNode.rightChild != null) {
            TreeNode parentNode = pNode.parent;
            if(pNode == parentNode.leftChild) {
                parentNode.leftChild = parentNode.rightChild;
                pNode.rightChild.parent = parentNode;
            } else {
                parentNode.rightChild = pNode.rightChild;
                pNode.rightChild.parent = parentNode;
            }
            return ;
        }
        if(pNode.leftChild != null && pNode.rightChild == null) {
            TreeNode parentNode = pNode.parent;
            if(pNode == parentNode.leftChild) {
                parentNode.leftChild = pNode.leftChild;
                pNode.leftChild.parent = parentNode;
            } else {
                parentNode.rightChild = pNode.leftChild;  
                pNode.rightChild.parent = parentNode;
            }
            return ;
        }
        //             ，           ，              
        TreeNode successorNode = successorInOrder(pNode);//          
        delete(successorNode);
        pNode.key = successorNode.key;
    }