public class Tree {
    
    TreeNode last = null;
    TreeNode root = null;
    
    
    public Tree(int value){
        root = createNode(value);
    }
        
    //结构
     static class TreeNode{
         int data;
         TreeNode left;
         TreeNode right; 
     }
     
     //查找结点
     public TreeNode searchTreeNode(int key,TreeNode tree){
         TreeNode keyNode = null;
         if(tree == null){
             return tree;
         }
         if(tree.data =http://www.mamicode.com/= key){
             return tree;
         }else if(key < tree.data ){
             last = tree;
             keyNode = searchTreeNode(key,tree.left);
         }else if(key > tree.data){
             last = tree;
             keyNode = searchTreeNode(key,tree.right);
         }
         return keyNode;
     }
     
     
     //添加节点
     public void addTreeNode(int key){
         if(searchTreeNode(key,root) == null){
             TreeNode tree = createNode(key);
             if(key < last.data){
                 last.left = tree;
             }else if(key > last.data){
                 last.right = tree;
             }
         }
         last = null;
     }
     
     //遍历
     public void iterate(TreeNode node){
        if(node ==null){
            return;
        }
        System.out.println(node.data);
        iterate(node.left);
        iterate(node.right);
     }
    
     public TreeNode createNode(int key){
        TreeNode tree = new TreeNode();
        tree.data = key;
        return tree;
     }
     
     public void removeNode(int key){
         TreeNode tree = searchTreeNode(key,root);
         if(tree.left == null && tree.right == null){
             
         }
         //如果右节点为空       当前节点取代左节点
         else if(tree.right == null){
             tree.data = tree.left.data;        // 把当前的左节点指向需要删除的左节点的左节点
             tree.right = tree.left.right;        // 把删除节点的右节点指向删除节点的左节点右节点
             tree.data = http://www.mamicode.com/tree.left.data;        // SET删除节点的值
         }else if(tree.left  == null){
             tree.right = tree.right.right;
             tree.left = tree.right.left;
             tree.data = tree.right.data;
         }else{
             //如果左右都不为空
             //获得右树最小的一个
             TreeNode nodeRight = tree.right;
             TreeNode lastLeftParent = null;
             while(nodeRight.left != null){
                 lastLeftParent = nodeRight;
                 nodeRight = nodeRight.left;
             }
             
            
             tree.data = nodeRight.data;    
             if(lastLeftParent != null)
                 lastLeftParent.left = nodeRight.right;    // 链接右子树
             else
                 tree.right = nodeRight.right;            // 链接右子树
         }
     }
     
     public static void main(String[] args){
         Tree tree = new Tree(4);
         tree.addTreeNode(5);
         tree.addTreeNode(6);
         tree.addTreeNode(3);
         tree.addTreeNode(7);
         tree.addTreeNode(8);
         tree.addTreeNode(9);
        

//         System.out.println(tree.searchTreeNode(7, tree.root).data);
         System.out.println("---");
         tree.iterate(tree.root);
     }
     
}