我是FE，也是Fe

前端来源于不断的点滴积累。我一直在努力。

统计

留言簿(15)

阅读排行榜

评论排行榜

javascript解析平铺树形数据

在做tree封装的时候，困难的地方往往是怎样显示树形数据，总后台查询的数据通常是List<Map<K,V>>之类的JSON字符串。形如
[{"NODELEVEL":2,"NODENAME":"测试深度节点20","FLAG":"1","HASCHILD":"1","PARENTNODE":"10002","LEVELCODE":"1000200000"}
,{"NODELEVEL":3,"NODENAME":"测试深度节点200","FLAG":"1","HASCHILD":"1","PARENTNODE":"1000200000","LEVELCODE":"100020000000000"}
,{"NODELEVEL":4,"NODENAME":"测试深度节点2000","FLAG":"1","HASCHILD":"1","PARENTNODE":"100020000000000","LEVELCODE":"10002000000000000000"}
,{"NODELEVEL":5,"NODENAME":"测试深度节点20000","FLAG":"1","HASCHILD":"1","PARENTNODE":"10002000000000000000","LEVELCODE":"1000200000000000000000000"}
,{"NODELEVEL":6,"NODENAME":"qwerfga","FLAG":"1","HASCHILD":"0","PARENTNODE":"1000200000000000000000000","LEVELCODE":"100020000000000000000000000001"}
,{"NODELEVEL":2,"NODENAME":"sdfg","FLAG":"1","HASCHILD":"1","PARENTNODE":"10002","LEVELCODE":"1000200001"}
,{"NODELEVEL":3,"NODENAME":"safsdfsadfaaa","FLAG":"1","HASCHILD":"0","PARENTNODE":"1000200001","LEVELCODE":"100020000100001"}
]
通常树需要的数据是有结构层次的，形如：
[
   {
      "NODELEVEL":2,
      "NODENAME":"sdfg",
      "FLAG":"1",
      "HASCHILD":"1",
      "PARENTNODE":"10002",
      "LEVELCODE":"1000200001",
      "children":[
         {
            "NODELEVEL":3,
            "NODENAME":"safsdfsadfaaa",
            "FLAG":"1",
            "HASCHILD":"0",
            "PARENTNODE":"1000200001",
            "LEVELCODE":"100020000100001"
         }
      ],
      "isFolder":true
   },
   {
      "NODELEVEL":2,
      "NODENAME":"测试深度节点20",
      "FLAG":"1",
      "HASCHILD":"1",
      "PARENTNODE":"10002",
      "LEVELCODE":"1000200000",
      "children":[
         {
            "NODELEVEL":3,
            "NODENAME":"测试深度节点200",
            "FLAG":"1",
            "HASCHILD":"1",
            "PARENTNODE":"1000200000",
            "LEVELCODE":"100020000000000",
            "children":[
               {
                  "NODELEVEL":4,
                  "NODENAME":"测试深度节点2000",
                  "FLAG":"1",
                  "HASCHILD":"1",
                  "PARENTNODE":"100020000000000",
                  "LEVELCODE":"10002000000000000000",
                  "children":[
                     {
                        "NODELEVEL":5,
                        "NODENAME":"测试深度节点20000",
                        "FLAG":"1",
                        "HASCHILD":"1",
                        "PARENTNODE":"10002000000000000000",
                        "LEVELCODE":"1000200000000000000000000",
                        "children":[
                           {
                              "NODELEVEL":6,
                              "NODENAME":"qwerfga",
                              "FLAG":"1",
                              "HASCHILD":"0",
                              "PARENTNODE":"1000200000000000000000000",
                              "LEVELCODE":"100020000000000000000000000001"
                           }
                        ],
                        "isFolder":true
                     }
                  ],
                  "isFolder":true
               }
            ],
            "isFolder":true
         }
      ],
      "isFolder":true
   }
]
//ps:感谢 http://jsonformatter.curiousconcept.com/ 在线format json

从平铺的格式转换到层次结构的json我经过多次实践，得出了下面的方法：

最开始，我约定ajax请求能得到树深度遍历结果，推荐之前一篇文件：一种能跨数据库的树形数据表格设计 上面的示例数据就是一个深度遍历结果。深度遍历结果的特点是每条记录的上一条记录要么是兄弟节点，要么是父节点，每条记录的下一条记录要么是兄弟节点，要么是子节点。根据这个特点，可以用如下方法解析:
function parse(arr, option) {
    var treenodes = [];//存放解析结果
    var stack = [];//存放当前节点路径 如果A->B->C-D 遍历到D节点时stack应该是[A,B,C]
    for ( var i = 0; i < arr.length; i++) {
        var mapednode = arr[i];
        if (i == 0) {// 第一个节点
            treenodes.push(mapednode);
            stack.push(mapednode);
        } else {
            var previousnode = arr[i - 1];
            if (parseInt(previousnode.level, 10) + 1 == parseInt(mapednode.level, 10)) {// 深度增加(深度增加1才视为深度增加)
                var parentnode = stack[stack.length - 1];//栈的最后一个节点是父节点
                parentnode.isFolder = true;
                if (!parentnode.children) parentnode.children = [];
                parentnode.children.push(mapednode);
                stack.push(mapednode);
            }
            if (previousnode.level == mapednode.level) {// 与之前节点深度相同
                // 栈中最后一个节点此时是同级节点previousnode
                // 所以此处去父节点时需要取到previousnode的父节点

                // 如果是一级节点，此时父节点应该是根节点
                if (stack.length > 1) {
                    var parentnode = stack[stack.length - 2];
                    parentnode.isFolder = true;
                    if (!parentnode.children)
                        parentnode.children = [];
                    parentnode.children.push(mapednode);
                } else {
                    treenodes.push(mapednode);
                }
                stack[stack.length - 1] = mapednode;// 保证栈中是同级节点的最后一个
            }

            if (previousnode.level > mapednode.level) {// 深度减少 出栈
                for ( var j = 0; j < (previousnode.level - mapednode.level); j++) {
                    stack.pop();
                }
                // 如果回到了一级节点，此时父节点应该是根节点
                if (stack.length > 1) {
                    var parentnode = stack[stack.length - 2];
                    parentnode.isFolder = true;
                    if (!parentnode.children) {
                        parentnode.children = [];
                    }
                    parentnode.children.push(mapednode);
                } else {
                    treenodes.push(mapednode);
                }

                stack[stack.length - 1] = mapednode;// 保证栈中是同级节点的最后一个
            }

        }
    }
    delete stack;
    delete arr;
    return treenodes;

}

var parseoption={
    titlefield:"NODENAME",//显示名称字段
    keyfield:"LEVELCODE",//节点唯一标识字段
    levelfield:"NODELEVEL",//深度字段
    parentfield:"PARENTNODE",//父节点标识字段
    customsiblingsort:"NODENAME"//同级节点排序字段
};

var parsedTreeData = parse(arr,parseoption);

基本思路是将arr循环，然后将节点层级的“塞”到对应的地方。因为总是要跟前一个节点数据比较，所以需要访问到上一个节点。而且总需要获得当前节点的父节点，而且需要判断是不是回到了一级节点，所以需要记录当前节点的访问路径，从整个深度遍历arr的过程看，当前节点的路径刚好是一个先进先出的关系，所以将stack声明为一个堆栈使用。

上面的方法没有实现同级节点排序，使用push方法能保证树的同级显示顺序与深度遍历结果中的出现顺序(这样可以利用ajax数据本身的顺序)。其实可以用插入排序的方法来替换上面的多处push。

//插入排序法
        var cl= parentnode.children.length;
        var insertIndex = 0;
        for ( var j = 0; j < cl; j++) {
            var targetSortValue = arr[parentnode.children[j]][fSIBLINGSORT]||"";
            //字符串比较
            if(isNaN(targetSortValue) && isNaN(sortValue) && targetSortValue.localeCompare(sortValue)>0 ){
                insertIndex= j;
                break;
            }else{
                insertIndex=j+1;
            }
            //数字比较
            if((!isNaN(targetSortValue)) && (!isNaN(sortValue)) && parseFloat(targetSortValue)>parseFloat(sortValue) ){
                insertIndex= j;
                break;
            }else{
                insertIndex=j+1;
            }
        }
        parentnode.children.splice(insertIndex, 0, i);

但是事实上用户老会抱怨为什么一定要深度遍历的结果，虽然，在之前提到的一种跨数据库的数据表设计中比较容易获取到深度遍历结果。

所以我又开始想怎么将无序的平铺树数据解析成层级结构。

function parse(arr,option){
    //有同级排序 拼接同级节点排序函数
    if(option.customsiblingsort){
        if(typeof(window[option.customsiblingsort])!="function"){//不是函数，视为字段名
            var sortfield = option.customsiblingsort;
            option.customsiblingsort= function(node1,node2){
                var v1 =node1[sortfield]||"";
                var v2 =node2[sortfield]||"";
                if((!isNaN(v1)) && (!isNaN(v2))){//数字比较
                    return parseFloat(v1)- parseFloat(v2);
                }else{
                    return v1.localeCompare(v2);//字符串比较
                }
            };
        }else{
            option.customsiblingsort=window[option.customsiblingsort];
        }
        
    }
    //step1:排序，按照节点深度排序，同深度节点按照customsiblingsort排序
    arr.sort(function (node1,node2){
        if((node1[option.levelfield]-node2[option.levelfield])>0){
            return 1;
        }else if ((node1[option.levelfield]-node2[option.levelfield])==0 && node1[option.parentfield].localeCompare(node2[option.parentfield])>0){
            return 1;
        }else if ( option.customsiblingsort  && (node1[option.levelfield]-node2[option.levelfield])==0 && node1[option.parentfield].localeCompare(node2[option.parentfield])==0 && option.customsiblingsort(node1,node2)>0 ){
            return 1;
        }else{
            return 0;
        }
    });
    
    var result  =[];
    var mapnode ={};//key :node key,value:node object reference
    //step2:排序后节点解析成树
    for(var i= 0;i<arr.length;i++){
        var mapednode =arr[i];
        var n  = mapednode;
        //深度为1或者深度与排序后第一个节点的深度一致视为一级节点
        if(n[option.levelfield]==1 ||  n[option.levelfield]==arr[0][option.levelfield]){
            result.push(n);
            mapnode[n[option.keyfield]]= n;
            continue;
        }
        if(n[option.levelfield]>=1){
            //找到父节点
            mapnode[n[option.keyfield]]= n;
            var p= n[option.parentfield];
            var parentNode = mapnode[p];
            //arr是按照深度排序，任何一个节点的父节点都会在子节点之前，所以parentNode!=null
            if(typeof(parentNode.children)=="undefined"){
                parentNode.children=[];
            }
            parentNode.isFolder=true;
            parentNode.children.push(n);
            
        }
    }
    delete arr,mapnode;
    return result;
}

var parseoption ={titlefield:"NODENAME",keyfield:"LEVELCODE",levelfield:"NODELEVEL",parentfield:"PARENTNODE",customsiblingsort:"NODENAME"};

var parsedTreeData = parse(arr,parseoption);

这种方法的循环次数自然比第一种方法要长，先根据深度将数组排序，这样做的目的一个是保证在遍历数组的任何一个节点是能在之前的节点中找到其父节点，第二也附带着将同级节点的排序也实现了。这种方法代码可读性比一种直接，性能慢在第一阶段的排序上。

树的前端显示总是能对前端开发者造成很大的挑战，光解析数据就会费劲心思。为了不至于要使用xtree,dtree那样的传统的tree控件，还是找找jQuery插件。目前发现了两个不错的jQuery tree插件jsTree 和dynatree 。不过都版本还是比较低，都不是很稳定，经常会有bug。jsTree就支持无序的数组数据源，dynatree必须是层次数据源。dynatree的性能显然要比jsTree要好，支持lazyLoad。所以选定dynatree。只是需要自己解析数据。

大家在树方面有什么建议和经验不妨分享分享。 相关的代码下载

posted on 2011-01-13 16:40 衡锋 阅读(2910) 评论(1)  编辑  收藏 所属分类: javascript 、Web开发

评论

# re: javascript解析平铺树形数据 2011-09-16 08:26 tb

有点困难啊   回复  更多评论   


只有注册用户登录后才能发表评论。
网站导航: