商品分类以及统计

     在卓越网首页的左边,或者当当网的左边，都有商品分类列表，并会显示旗下的商品有多少种。如何在计算机中描述？那可定是用树来表示。但要高效地完成这个功能会面临哪些问题？

    1、怎么统计某一分类的商品种类

    2、如果更改某一分类商品种类数量，怎么通知其他节点

    3、对于非叶子节，是否要记录商品数，

    4、如果增加新的商品类型，又怎么做

 

    对于这些问题，我认为关键的一点是：一旦有数据变化，就要通知双亲，直到根节点。这样一来，每当获取某一中分类的商品种类数时，它会检测是否收到通知，如果收到，则重新计算；否则直接返回数量。

    废话不多说，直接贴代码，欢迎拍砖。

import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Stack;

/**商品分类*/
public class CommodityClassify {
    /**该分类名称*/
    private String name;
    /**编码*/
    private String code;
    /**该分类下的商品种类数*/
    private int amount = 0;
    /**是否要改变*/
    private boolean change  = true;
    /**双亲结点*/
    private CommodityClassify parent;
    /**孩子结点*/
    private List<CommodityClassify> children = new LinkedList<CommodityClassify>();

    public CommodityClassify(String name){
        this(name,null,0);
    }
    public CommodityClassify(String name,String code){
        this(name,code,0);
    }
    public CommodityClassify(String name,int amount){
        this(name,null,amount);
    }
    CommodityClassify(String name,String code,int amount){
        this.name = name;
        this.code = code;
        this.amount = amount;
    }
          
    //*************************  getter/setter  ******************************
    public boolean isChange() {
        return change;
    }
    public void setChange(boolean change) {
       this.change = change;
    }
    public CommodityClassify getParent() {
       return parent;
    }
    public void setParent(CommodityClassify parent) {
       this.parent = parent;
    }
    public String getName(){
       return name;
    }
    public void setName(String name){
       this.name = name;
    }
    public String getCode() {
       return code;
    }
    public void setCode(String code) {
       this.code = code;
    }

    public List<CommodityClassify> getChildren() {
       return children;
    }
    //********************* 节点操作 **********************

        /** 
         * 增加孩子结点 
         * @param cc 
         */  
        public void addChild(CommodityClassify cc){
            //1、设置双亲节点  
            cc.setParent(this);  
            //2、增加叶子节点  
            this.children.add(cc);
            notifyParentChange();  
            //3、如果不是叶子节点，则重置amount为0;  
            if(!isLeafy()) {  
                this.amount = 0;  
            }
        }
        public void removeChild(CommodityClassify cc){
            //1、待删除的节点清空双亲
            cc.setParent(null);
            //2、删除节点
            this.children.remove(cc);
            //3、通知变化
            notifyParentChange();
        }

    /**
     * 把 当前树 从 整棵树中 剥离出来；
     */
     public void remove() throws Exception {
         if(this.getParent() == null) throw new Exception("根节点不能删除");
         //1、找到双亲
         parent = this.getParent();
         //2、删除当前树
         parent.removeChild(this);
     }
     public void remove(CommodityClassify cc) throws Exception {
           if(this.getParent() == null) throw new Exception("根节点不能删除");
           if(this.equals(cc)) throw new Exception("不能删除自身");
           removeChild(cc);
     }

          
      //**************  商品分类  数目 ******************

         /**
         * 返回根节点
         */
      public CommodityClassify getRoot(){
            CommodityClassify root = this;
            while(root.parent!= null){
                root = root.parent;
            }
            return root;
      }

        /**
         * 判断是否为叶子节点
         */
        public boolean isLeafy(){
            return 0 == children.size() ;
      }

        /**
         * 通知双亲结点:数据已经改变
         */
        public void notifyParentChange(){
            //通知当前当前结点数据变化
            this.setChange(true);
            //通知双亲结点数据已经变化
            CommodityClassify parents = this.parent;
            while(parents!= null){
                parents.setChange(true);
                parents = parents.parent;
            }

        }
        /** 
         * 更新整棵树的Amount; 
         */  
        public void updateTreeAmount(){  
            this.getRoot().getAmount();  
        }  
        /** 
         * 调整节点的amount 
         * @param amount 
         */  
        public void setAmount(int amount){  
        //1、如果是叶子节点，则传入amount，否则跳过  
            if(isLeafy() && this.amount != amount) {  
                this.amount = amount;  
                notifyParentChange();  
            }  
              
        }
        /** 
         * 返回某类商品下的所有数量  
         */  
        public int getAmount(){  
            //如果数据改变,则重新历遍子树  
            if( change ){  
                if(!isLeafy()) amount = 0;  
                for(CommodityClassify cc: children){
                    amount+= cc.getAmount();  
                }  
                change = false;  
              
            }     
            //如果数据没有改变，则直接返回  
            return amount;  
        }
        /**
         * 添加子分类
         * @param name
         * @param amount
         * @return   新的分类
         */

    //*************************  遍历 **************************
    /**
     * 广度遍历，使用队列，利用队列来实现
     */
    public void levelVisit(){
        Queue<CommodityClassify> queue = new LinkedList<CommodityClassify>();
        queue.add(this);
        while(!queue.isEmpty()){
            CommodityClassify c = queue.poll();
            System.out.println(c.getName());
            queue.addAll(c.getChildren());
        }
    }

    /**
     * 返回广度遍历的的 链表
     * @return
     */
    public List<CommodityClassify> levelList(){
       List<CommodityClassify> list  = new LinkedList<CommodityClassify>();
       int currentIndex = 0;
       list.add(this);
       while(currentIndex <list.size()){
           if(!list.get(currentIndex).isLeafy()){
               list.addAll(list.get(currentIndex).getChildren());    ///将子节点添加的list中
           }
           currentIndex++;
       }
        return list;
    }


    /**
     * 深度遍历 的递归算法  方向：从左道右
     */
    public void deepRecursiveVisit(){
       System.out.println(getName());
       for(CommodityClassify c:children){
           c.deepRecursiveVisit();
       }
    }

    /**
     * 深度遍历的 非递归算法   方向 ：从右到左
     */
    public void deepIterativeVisit(){
            Stack<CommodityClassify> stack = new Stack<CommodityClassify>();
            stack.push(this);
            while(!stack.isEmpty()){
                CommodityClassify c = stack.pop();
                System.out.println(c.getName());
                if(!c.isLeafy()){
                    stack.addAll(c.getChildren());
                }
            }
        }




    //***************************  辅助 函数*******************************
    public CommodityClassify addChild(String name,String code,int amount){
        CommodityClassify c = new CommodityClassify(name,code,amount);
        this.addChild(c);
        return c;
    }
    public CommodityClassify addChild(String name,String code){
        CommodityClassify c = new CommodityClassify(name,code);
        this.addChild(c);
        return c;
    }

    /**
     * 根据code查找节点 ，使用广度遍历
     * @param code
     * @return
     */
    public CommodityClassify levelVisit(String code){
        Queue<CommodityClassify> queue = new LinkedList<CommodityClassify>();
        queue.add(this);
        while(!queue.isEmpty()){
            CommodityClassify c = queue.poll();
            if(c.getCode().equals(code)){
                return c;
            }
            queue.addAll(c.getChildren());
        }
        return null;
    }

     public CommodityClassify deepVisit(String code){
        if(getCode().equals(code)){
            return this;
        }
        for(CommodityClassify c:children){
            CommodityClassify c1  =c.deepVisit(code);
                if(c1 != null){
                    return c1;
                }
        }
         return null;
    }
    //************************  其他 ********************************************
    public boolean equals(Object obj){
        if(obj == null) return false;
        if(obj.getClass() != this.getClass()) return false;
        CommodityClassify c = (CommodityClassify)obj;
        return c.getCode().equals(this.getCode());
    }
}

 

 

public class CommodityClassifyTest {
    private CommodityClassify root;
    private CommodityClassify jisuanji;
    @Before
    public void setUp() throws Exception {
          root = new CommodityClassify("根","root");

         CommodityClassify tushu = root.addChild("图书","tushu");
         CommodityClassify zhongwentushu = tushu.addChild("中文图书","zhongwentushu");
         CommodityClassify wenxue = zhongwentushu.addChild("文学","wenxue");
         CommodityClassify shige = wenxue.addChild("诗歌","shige");
         shige.addChild("唐诗","tangshi",100);
         shige.addChild("宋词","songci",100);

          jisuanji =tushu.addChild("计算机","jisuanji");
         jisuanji.addChild("java","java",100);
         jisuanji.addChild("数据库","database",100);
         jisuanji.addChild(".NET",".net", 100);

         CommodityClassify jiaocai = tushu.addChild("教材","jiaocai");
         jiaocai.addChild("小学","xiaoxue", 100);
         jiaocai.addChild("初中","gaozhong",100);
         jiaocai.addChild("高中","chuzong",100);
         jiaocai.addChild("大学","daxue",100);
         jiaocai.addChild("研究生","yanjiusheng",100);
         jiaocai.addChild("博士生","boshisheng",100);



    }

    @After
    public void tearDown() throws Exception {
        root = null;
    }
    @Test
    public void testCountAll(){
        assertEquals(1100,root.getAmount());
    }
    @Test
    public void AddChildInLinkdWays(){
        root.addChild("数码产品","shuma").addChild("掌上设备","zhangshangshebei").addChild("手机","shouji",100);
        assertEquals(1200,root.getAmount());
    }
    @Test
    public void levelVisit(){
       root.levelVisit();

    }
    @Test
    public void levelVisitCode(){
       assertEquals("xiaoxue", root.levelVisit("xiaoxue").getCode());
    }
    @Test
    public void deepVisitCode(){
        assertEquals("xiaoxue",root.deepVisit("xiaoxue").getCode());
    }
    @Test
    public void levelList(){
        assertEquals(18,root.levelList().size());
    }

     @Test
     public void recursiveVisit(){
         System.out.println("--------recursive--------");
         root.deepRecursiveVisit();
     }

    @Test
    public void testDeepIterativeVisit(){
        System.out.println("----------Iterative-------------");
        root.deepIterativeVisit();
    }
    @Test
    public void removeCommodity() throws Exception {
        jisuanji.remove();
        assertEquals(800,root.getAmount());
    }

}