두 갈래 검색 트 리 구현 및 깊이 우선 옮 기기 및 넓이 우선 옮 기기

public class BinarySearchTree<T> {
    private TreeNode root;
    /**
     *     
     * @param key
     * @param value
     */
    public void insert(int key,T value){
        if(root == null){
            root = new TreeNode(key,value);
        }else{
            insert(root,key,value);
        }

    }

    /**
     *             
     * @param node
     * @param key
     * @param value
     */
    private void insert(TreeNode node,int key,T value){
        //                
        if(key < node.key){
            //               ，         ，                
            if(node.leftChild == null){
                TreeNode treeNode = new TreeNode(key,value);
                node.leftChild = treeNode;
            }else{
                //           
                insert(node.leftChild, key, value);
            }
        }else{
            //  
            if(node.rightChild == null){
                TreeNode treeNode = new TreeNode(key,value);
                node.rightChild = treeNode;
            }else{
                insert(node.rightChild, key, value);
            }
        }
    }
    /**
     *         
     * @param node
     * @return
     */
    private TreeNode min(TreeNode node){
        if(node == null){
            return null;
        }else if(node.leftChild == null){
            return node;
        }
        return min(node.leftChild);
    }
    /**
     *          
     * @param node
     * @return
     */
    private TreeNode max(TreeNode node){
        if(node == null){
            return null;
        }else if(node.rightChild == null){
            return node;
        }
        return max(node.rightChild);
    }
    /**
     *     
     * @param key
     */
    public void remove(int key){
        remove(root, key);
    }
    /**
     *   
     * @param node
     * @param key
     */
    private void remove(TreeNode node,int key){
        if(node == null ){
            return ;
        }
        //                    
        if(key < node.key){
            remove(node.leftChild, key);
        //                   
        }else if(key > node.key){
            remove(node.rightChild, key);
        //*         ，             ，       
        }else if(node.leftChild != null && node.rightChild != null){
            //             ，            ，      
            TreeNode min = min(node.rightChild);
            //                       
            node.key = min.key;
            node.data = min.data;
            //                   
            remove(node.rightChild,min.key);
        }else{
            //                  ，                        
            node = node.leftChild == null ? node.rightChild:node.leftChild;
        }
    }
    /**
     *     ,  
     */
    public void firstOrder(TreeNode node){
        if(node == null){
            return ;
        }
        show(node);
        firstOrder(node.leftChild);
        firstOrder(node.rightChild);
    }
    /**
     *     
     * @param node
     */
    public void middleOrder(TreeNode node){
        if(node == null){
            return ;
        }
        middleOrder(node.leftChild);
        show(node);
        middleOrder(node.rightChild);
    }
    /**
     *     
     * @param node
     */
    public void lastOrder(TreeNode node){
        if(node == null){
            return ;
        }
        lastOrder(node.leftChild);
        lastOrder(node.rightChild);
        show(node);
    }
    /**
     *     ，   
     * @param node
     */
    public void firstOrderStack(TreeNode node){
        if(node == null){
            throw new RuntimeException("     ");
        }
        //           
        Stack stack = new Stack<>();
        //         
        stack.push(node);
        //        ，           
        while(node != null && !stack.isEmpty()){
            //     
            show(node);
            //             ，        
            if(node.rightChild != null){
                stack.push(node.rightChild);
            }
            //        ，        
            if(node.leftChild != null){
                stack.push(node.leftChild);
            }
            //  ，             ，           
            node = stack.pop();
        }
    }
    /**
     *     ，   2，    
     * @param node
     */
    public void firstOrderStack2(TreeNode node){
        if(node == null){
            throw new RuntimeException("     ");
        }
        Stack stack = new Stack<>();
        //
        while(node != null || !stack.isEmpty()){
            //        ，        
            while(node != null){
                show(node);
                stack.push(node);
                node = node.leftChild;
            }
            //        （     ）    
            node = stack.pop().rightChild;
        }

    }
    /**
     *     ，   
     * @param node
     */
    public void middleOrderStack(TreeNode node){
        if(node == null){
            throw new RuntimeException("     ");
        }

        Stack stack = new Stack<>();
        //                 
        while(node != null || !stack.isEmpty()){
            //    ，           ，        
            while(node != null){
                stack.push(node);
                node = node.leftChild;
            }
            //      ，   ，           
            node =stack.pop();
            show(node);
            node = node.rightChild;

        }
    }
    /**
     *     ,   
     * @param node
     */
    public void lastOrderStack(TreeNode node){
        if(node == null){
            throw new RuntimeException("     ");
        }
        //         
        TreeNode last = null;
        Stack stack = new Stack<>();
        while(node != null ){
            //      ,    
            while(node != null){
                stack.push(node);
                node = node.leftChild;
            }
            //           
            node = stack.pop();
            //        ，             ，            。                 ，         
            while(node.rightChild == null || node.rightChild == last){
                //    
                show(node);
                //                ，                            
                last = node;
                if(stack.isEmpty()){
                    return;
                }
                //            
                node = stack.pop();
            }
                //      ，          ，      
                stack.push(node);
                //             ，     ，           ，           ，           
                node = node.rightChild;
        }
    }
    /**
     *       
     * @param node
     */
    public void OrderQueue(TreeNode node){
        Queue queue = new LinkedList<>();
        queue.offer(node);
        //       ，     
        while(!queue.isEmpty()){
            //  
            node = queue.poll();
            //    
            show(node);
            //             ，       
            if(node.leftChild != null){
                queue.offer(node.leftChild);
            }
            //             ，       
            if(node.rightChild != null){
                queue.offer(node.rightChild);
            }
        }
    }
    public void show(TreeNode node){
        System.err.println("key:"+node.key+",vlaue:"+node.data);
    }
    /**
     *    
     * @author yuli
     *
     */
    private  class TreeNode{
        int key;
        T data;
        TreeNode leftChild;
        TreeNode rightChild;
        TreeNode(int key,T data){
            this.key = key;
            this.data = data;
        }
    }
}