数据表结构
function make_tree($list,$pk='id',$pid='pid',$child='_child',$root=0){
　　$tree=array();
　　$packData=array();
　　//转换数组的结构
　　foreach ($list as
　　　　$packData[$data[$pk]] = $
　　foreach ($packData as $key =&$val){
　　　　if($val[$pid]==$root){//代表跟节点
　　　　　　$tree[]=& $packData[$key];
　　　　}else{
　　　　　　//找到其父类
　　　　　　$packData[$val[$pid]][$child][]=& $packData[$key];
　　return $}
$arr = make_tree($list, 'cat_id', "parent_id", "son", 0);
var_dump($arr);
array(5) {
[0] =& array(6) {
["cat_id"] =& string(1) "1"
["cat_name"] =& string(6) "女装"
["parent_id"] =& string(1) "0"
["sort_order"] =& string(2) "50"
["is_show"] =& string(1) "1"
["son"] =& array(3) {
[0] =& array(6) {
["cat_id"] =& string(1) "6"
["cat_name"] =& string(9) "连衣裙"
["parent_id"] =& string(1) "1"
["sort_order"] =& string(2) "50"
["is_show"] =& string(1) "1"
["son"] =& array(1) {
[0] =& array(5) {
["cat_id"] =& string(2) "31"
["cat_name"] =& string(12) "我的最爱"
["parent_id"] =& string(1) "6"
["sort_order"] =& string(2) "50"
["is_show"] =& string(1) "1"
阅读(...) 评论()1458人阅读
无限极树形菜单
树形结构（1）
利用多叉树实现Ext JS中的无限级树形菜单（一种构建多级有序树形结构JSON的方法）&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&
一、问题研究的背景和意义
目前在Web应用程序开发领域，Ext JS框架已经逐渐被广泛使用，它是富客户端开发中出类拔萃的框架之一。在Ext的UI控件中，树形控件无疑是最为常用的控件之一，它用来实现树形结构的菜单。TreeNode用来实现静态的树形菜单，AsyncTreeNode用来实现动态的异步加载树形菜单，后者最为常用，它通过接收服务器端返回来的JSON格式的数据，动态生成树形菜单节点。动态生成树有两种思路：一种是一次性生成全部树节点，另一种是逐级加载树节点（利用AJAX，每次点击节点时查询下一级节点）。对于大数据量的菜单节点来说，逐级加载是比较合适的选择，但是对于小数据量的菜单来说，一次性生成全部节点应该是最为合理的方案。在实际应用开发中，一般不会遇到特别大数据量的场景，所以一次性生成全部菜单节点是我们重点研究的技术点，本文就是介绍基于Ext
JS的应用系统中如何将数据库中的无限级层次数据一次性在界面中生成全部菜单节点（例如在界面中以树形方式一次性展示出银行所有分支机构的信息），同时对每一个层次的菜单节点按照某一属性和规则排序，展示出有序的菜单树。
解决Ext JS无限级树形菜单的问题，可以拓展出更多的应用场景，例如树形结构表格TreeGrid，一次性生成树形表格，对树形表格进行完整分页，对表格列进行全排序；或者可以利用本文的思路扩展出其他的更复杂的应用场景。
先看两个图例，有个直观上的认识：
图一，银行分支机构树形结构菜单
图二，树形结构表格
二、详细设计方案
让我们先看一段代码片段：
文件一，branchTree.html （Ext树形控件页面）
Ext.onReady(&&&function(){&&&&&&var&&tree&=&new&Ext.tree.TreePanel({&&&&&&&&&height:&300,&&&&&&&&&width:&400,&&&&&&&&&animate:true,&&&&&&&&&enableDD:true,&&&&&&&&&containerScroll:&true,&&&&&&&&&rootVisible:&false,&&&&&&&&&frame:&true,&&&&&&&&&//&getBranch.do请求服务器返回多级树形结构的JSON字符串&&&&&&&loader:&new&Ext.tree.TreeLoader({dataUrl:'getBranch.do'}),&&&&&&&&&&root&:&new&Ext.tree.AsyncTreeNode({id:'0',text:'根结点'})&&&&&&&&&&});&&&&&&&&&&&&&&tree.expandAll();&&&&}&&);&&
文件二，branchTreeJSON.jsp （接收getBranch.do请求，返回无限级JSON字符串）
Java代码&&
&%&&//&读取银行分支机构的层次数据&&List&result&=&DataAccess.getBankInfoList();&&//&将层次数据转换为多叉树对象（本文下面会详细介绍该数据结构的实现方法）&&Node&root&=&ExtTreeHelper.createExtTree(result);&&&%&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&[&&&%=root.toString()%&&&!--&以JSON的形式返回响应数据，Ext.tree.TreeLoader会根据此数据生成树形菜单&--&&&]&&
以上两个程序文件是一次性生成无限级树形菜单所必须的，其中最为关键的部分就是如何生成一个无限级的JSON字符串，返回给客户端的Ext树形控件。对于银行分支机构来说，需要返回类似如下的JSON串：
{&&&&id:&'100000',&&&&text:&'廊坊银行总行',&&&&children:&[&&&&&&{&&&&&&&&id:&'110000',&&&&&&&&text:&'廊坊分行',&&&&&&&&children:&[&&&&&&&&&&{&&&&&&&&&&&&id:&'113000',&&&&&&&&&&&&text:&'廊坊银行开发区支行',&&&&&&&&&&&&leaf:&true&&&&&&&&&&},&&&&&&&&&&{&&&&&&&&&&&&id:&'112000',&&&&&&&&&&&&text:&'廊坊银行解放道支行',&&&&&&&&&&&&children:&[&&&&&&&&&&&&&&{&&&&&&&&&&&&&&&&id:&'112200',&&&&&&&&&&&&&&&&text:&'廊坊银行三大街支行',&&&&&&&&&&&&&&&&leaf:&true&&&&&&&&&&&&&&},&&&&&&&&&&&&&&{&&&&&&&&&&&&&&&&id:&'112100',&&&&&&&&&&&&&&&&text:&'廊坊银行广阳道支行',&&&&&&&&&&&&&&&&leaf:&true&&&&&&&&&&&&&&}&&&&&&&&&&&&]&&&&&&&&&&},&&&&&&&&&&{&&&&&&&&&&&&id:&'111000',&&&&&&&&&&&&text:&'廊坊银行金光道支行',&&&&&&&&&&&&leaf:&true&&&&&&&&&&}&&&&&&&&]&&&&&&}&&&&]&&}&&
同时还可能需要对树中每一个层次的节点按照某一属性（比如分支机构编号）进行排序，以展示出有序的树形菜单。
现在可以把问题概括为：
1、 把数据库中的层次数据转换成JSON格式的字符串
2、 对树中每一个层次的节点按照某一属性（比如分支机构编号）进行排序
下面介绍解决问题的思路：
在数据结构这门课中，我们都学过树，无限级树形菜单就可以抽象成一种多叉树结构，即每个节点下包含多个子节点的树形结构，首先就需要把数据库中的层次数据转换成多叉树结构的对象树，也就是构造出一棵多叉树。
有了数据结构，还要实现相应的算法，我们需要实现两种算法：
1、兄弟节点横向排序算法，对隶属于同一个父节点下面的所有直接子节点按照某一节点属性和规则进行排序，保持兄弟节点横向有序；
2、先序遍历算法，递归打印出无限级JSON字符串。
概括起来分为三步：
1、&构造无序的多叉树结构
2、&实现兄弟节点横向排序方法
3、&实现先序遍历方法，打印出JSON字符串
如图所示：
三、源代码实现（Java语言版）
实现这样一颗树，需要设计三个类：树类（MultipleTree.java）、节点类（Node.java）、孩子列表类（Children.java）；为了方便演示，还需要构造一些假的层次数据，因此还需要建一个构造假数据的类（VirtualDataGenerator.java），以下代码拷贝出来之后可直接运行测试：
Java代码&&
package&&&&&import&java.util.ArrayL&&import&&&import&java.util.HashM&&import&java.util.I&&import&java.util.L&&import&java.util.M&&import&java.util.S&&import&java.util.C&&&&/**&&*&多叉树类&*/&&public&class&MultipleTree&{&&&public&static&void&main(String[]&args)&{&&&&//&读取层次数据结果集列表&&&&&List&dataList&=&VirtualDataGenerator.getVirtualResult();&&&&&&&&&&//&节点列表（散列表，用于临时存储节点对象）&&&&HashMap&nodeList&=&new&HashMap();&&&&//&根节点&&&&Node&root&=&null;&&&&//&根据结果集构造节点列表（存入散列表）&&&&for&(Iterator&it&=&dataList.iterator();&it.hasNext();)&{&&&&&Map&dataRecord&=&(Map)&it.next();&&&&&Node&node&=&new&Node();&&&&&node.id&=&(String)&dataRecord.get(&id&);&&&&&node.text&=&(String)&dataRecord.get(&text&);&&&&&node.parentId&=&(String)&dataRecord.get(&parentId&);&&&&&nodeList.put(node.id,&node);&&&&}&&&&//&构造无序的多叉树&&&&Set&entrySet&=&nodeList.entrySet();&&&&for&(Iterator&it&=&entrySet.iterator();&it.hasNext();)&{&&&&&Node&node&=&(Node)&((Map.Entry)&it.next()).getValue();&&&&&if&(node.parentId&==&null&||&node.parentId.equals(&&))&{&&&&&&root&=&&&&&&}&else&{&&&&&&((Node)&nodeList.get(node.parentId)).addChild(node);&&&&&}&&&&}&&&&//&输出无序的树形菜单的JSON字符串&&&&System.out.println(root.toString());&&&&&&&//&对多叉树进行横向排序&&&&root.sortChildren();&&&&//&输出有序的树形菜单的JSON字符串&&&&System.out.println(root.toString());&&&&&&&&&//&程序输出结果如下（无序的树形菜单）（格式化后的结果）：&&&&&&//&&{&&&&//&&&id&:&'100000',&&&&&//&&&text&:&'廊坊银行总行',&&&&&//&&&children&:&[&&&&//&&&&&{&&&&//&&&&&id&:&'110000',&&&&&//&&&&&text&:&'廊坊分行',&&&&&//&&&&&children&:&[&&&&//&&&&&&&{&&&&//&&&&&&&id&:&'113000',&&&&&//&&&&&&&text&:&'廊坊银行开发区支行',&&&&&//&&&&&&&leaf&:&true&&&&//&&&&&&&},&&&&//&&&&&&&{&&&&//&&&&&&&id&:&'111000',&&&&&//&&&&&&&text&:&'廊坊银行金光道支行',&&&&&//&&&&&&&leaf&:&true&&&&//&&&&&&&},&&&&//&&&&&&&{&&&&//&&&&&&&id&:&'112000',&&&&&//&&&&&&&text&:&'廊坊银行解放道支行',&&&&&//&&&&&&&children&:&[&&&&//&&&&&&&&&{&&&&//&&&&&&&&&id&:&'112200',&&&&&//&&&&&&&&&text&:&'廊坊银行三大街支行',&&&&&//&&&&&&&&&leaf&:&true&&&&//&&&&&&&&&},&&&&//&&&&&&&&&{&&&&//&&&&&&&&&id&:&'112100',&&&&&//&&&&&&&&&text&:&'廊坊银行广阳道支行',&&&&&//&&&&&&&&&leaf&:&true&&&&//&&&&&&&&&}&&&&//&&&&&&&]&&&&//&&&&&&&}&&&&//&&&&&]&&&&//&&&&&}&&&&//&&&]&&&&//&&}&&&&&&//&程序输出结果如下（有序的树形菜单）（格式化后的结果）：&&&&//&&{&&&&//&&&id&:&'100000',&&&&&//&&&text&:&'廊坊银行总行',&&&&&//&&&children&:&[&&&&//&&&&&{&&&&//&&&&&id&:&'110000',&&&&&//&&&&&text&:&'廊坊分行',&&&&&//&&&&&children&:&[&&&&//&&&&&&&{&&&&//&&&&&&&id&:&'111000',&&&&&//&&&&&&&text&:&'廊坊银行金光道支行',&&&&&//&&&&&&&leaf&:&true&&&&//&&&&&&&},&&&&//&&&&&&&{&&&&//&&&&&&&id&:&'112000',&&&&&//&&&&&&&text&:&'廊坊银行解放道支行',&&&&&//&&&&&&&children&:&[&&&&//&&&&&&&&&{&&&&//&&&&&&&&&id&:&'112100',&&&&&//&&&&&&&&&text&:&'廊坊银行广阳道支行',&&&&&//&&&&&&&&&leaf&:&true&&&&//&&&&&&&&&},&&&&//&&&&&&&&&{&&&&//&&&&&&&&&id&:&'112200',&&&&&//&&&&&&&&&text&:&'廊坊银行三大街支行',&&&&&//&&&&&&&&&leaf&:&true&&&&//&&&&&&&&&}&&&&//&&&&&&&]&&&&//&&&&&&&},&&&&//&&&&&&&{&&&&//&&&&&&&id&:&'113000',&&&&&//&&&&&&&text&:&'廊坊银行开发区支行',&&&&&//&&&&&&&leaf&:&true&&&&//&&&&&&&}&&&&//&&&&&]&&&&//&&&&&}&&&&//&&&]&&&&//&&}&&&&&&&&&}&&&&&&&}&&&&&&/**&*&节点类&*/&&class&Node&{&&&/**&&&*&节点编号&&&*/&&&public&String&&&&/**&&&*&节点内容&&&*/&&&public&String&&&&/**&&&*&父节点编号&&&*/&&&public&String&parentId;&&&/**&&&*&孩子节点列表&&&*/&&&private&Children&children&=&new&Children();&&&&&&//&先序遍历，拼接JSON字符串&&&public&String&toString()&{&&&&&&String&result&=&&{&&&&&&+&&id&:&'&&+&id&+&&'&&&&&&+&&,&text&:&'&&+&text&+&&'&;&&&&&&&&if&(children&!=&null&&&&children.getSize()&!=&0)&{&&&&&result&+=&&,&children&:&&&+&children.toString();&&&&}&else&{&&&&&result&+=&&,&leaf&:&true&;&&&&}&&&&&&&&&&return&result&+&&}&;&&&}&&&&&&//&兄弟节点横向排序&&&public&void&sortChildren()&{&&&&if&(children&!=&null&&&&children.getSize()&!=&0)&{&&&&&children.sortChildren();&&&&}&&&}&&&&&&//&添加孩子节点&&&public&void&addChild(Node&node)&{&&&&this.children.addChild(node);&&&}&&}&&&&/**&*&孩子列表类&*/&&class&Children&{&&&private&List&list&=&new&ArrayList();&&&&&&public&int&getSize()&{&&&&return&list.size();&&&}&&&&&&public&void&addChild(Node&node)&{&&&&list.add(node);&&&}&&&&&&//&拼接孩子节点的JSON字符串&&&public&String&toString()&{&&&&String&result&=&&[&;&&&&&&for&(Iterator&it&=&list.iterator();&it.hasNext();)&{&&&&&result&+=&((Node)&it.next()).toString();&&&&&result&+=&&,&;&&&&}&&&&result&=&result.substring(0,&result.length()&-&1);&&&&result&+=&&]&;&&&&return&&&&}&&&&&&//&孩子节点排序&&&public&void&sortChildren()&{&&&&//&对本层节点进行排序&&&&//&可根据不同的排序属性，传入不同的比较器，这里传入ID比较器&&&&Collections.sort(list,&new&NodeIDComparator());&&&&//&对每个节点的下一层节点进行排序&&&&for&(Iterator&it&=&list.iterator();&it.hasNext();)&{&&&&&((Node)&it.next()).sortChildren();&&&&}&&&}&&}&&&&/**&&*&节点比较器&&*/&&class&NodeIDComparator&implements&Comparator&{&&&//&按照节点编号比较&&&public&int&compare(Object&o1,&Object&o2)&{&&&&int&j1&=&Integer.parseInt(((Node)o1).id);&&&&&&&int&j2&=&Integer.parseInt(((Node)o2).id);&&&&&&&return&(j1&&&j2&?&-1&:&(j1&==&j2&?&0&:&1));&&&}&&&}&&&&/**&&*&构造虚拟的层次数据&&*/&&class&VirtualDataGenerator&{&&&//&构造无序的结果集列表，实际应用中，该数据应该从数据库中查询获得；&&&public&static&List&getVirtualResult()&{&&&&&&&&List&dataList&=&new&ArrayList();&&&&&&&&HashMap&dataRecord1&=&new&HashMap();&&&&dataRecord1.put(&id&,&&112000&);&&&&dataRecord1.put(&text&,&&廊坊银行解放道支行&);&&&&dataRecord1.put(&parentId&,&&110000&);&&&&&&&&HashMap&dataRecord2&=&new&HashMap();&&&&dataRecord2.put(&id&,&&112200&);&&&&dataRecord2.put(&text&,&&廊坊银行三大街支行&);&&&&dataRecord2.put(&parentId&,&&112000&);&&&&&&&&HashMap&dataRecord3&=&new&HashMap();&&&&dataRecord3.put(&id&,&&112100&);&&&&dataRecord3.put(&text&,&&廊坊银行广阳道支行&);&&&&dataRecord3.put(&parentId&,&&112000&);&&&&&&&&&&&&HashMap&dataRecord4&=&new&HashMap();&&&&dataRecord4.put(&id&,&&113000&);&&&&dataRecord4.put(&text&,&&廊坊银行开发区支行&);&&&&dataRecord4.put(&parentId&,&&110000&);&&&&&&&&&&&&HashMap&dataRecord5&=&new&HashMap();&&&&dataRecord5.put(&id&,&&100000&);&&&&dataRecord5.put(&text&,&&廊坊银行总行&);&&&&dataRecord5.put(&parentId&,&&&);&&&&&&&&HashMap&dataRecord6&=&new&HashMap();&&&&dataRecord6.put(&id&,&&110000&);&&&&dataRecord6.put(&text&,&&廊坊分行&);&&&&dataRecord6.put(&parentId&,&&100000&);&&&&&&&&HashMap&dataRecord7&=&new&HashMap();&&&&dataRecord7.put(&id&,&&111000&);&&&&dataRecord7.put(&text&,&&廊坊银行金光道支行&);&&&&dataRecord7.put(&parentId&,&&110000&);&&&&&&&&&&&&dataList.add(dataRecord1);&&&&dataList.add(dataRecord2);&&&&dataList.add(dataRecord3);&&&&dataList.add(dataRecord4);&&&&dataList.add(dataRecord5);&&&&dataList.add(dataRecord6);&&&&dataList.add(dataRecord7);&&&&&&&&return&dataL&&&}&&&}&&
好了，通过上面的代码，就可以实现多叉树的兄弟节点横向排序和先序遍历了，实现了将层次数据转换为有序无限级JSON字符串的目的。
在实际的项目中，可以把上面的有效代码融入其中，或者在此基础上进行一些扩展：
1、 实现对指定层次的排序（例如只排序第一层的节点，或者只排序某一父节点下的所有子节点）
2、 遍历输出树形结构时可以加入判断条件过滤掉某些节点
3、 实现节点的删除功能
4、 在节点类中增加一个父节点的引用，就可以计算出某一节点所处的级别
5、 在不支持层次查询的数据库应用系统中使用该算法实现相同的效果
四、思考与总结
这篇文章的重点是如何构造有序的无限级的树形结构JSON字符串，一次性生成树形菜单，而不是利用AJAX的方式，反复向服务器端发送请求，一级接一级的加载树节点。
既然可以构造无限级的JSON字符串，那么也可以根据这个思路构造无限级的XML字符串，或者构造具有层次结构的UL – LI组合（用UL - LI来展示树形结构），或者构造具有层次结构的TABLE（用TABLE来展示树形结构）。如下所示：
（1）XML层次结构
&menuGroup&id=&100000&&name=&廊坊银行总行&&&&&&&menuGroup&id=&110000&&name=&廊坊分行&&&&&&&&&&menu&id=&113000&&name=&廊坊银行开发区支行&&&&&&&&&&&&/menu&&&&&&&&&menu&id=&111000&&name=&廊坊银行金光道支行&&&&&&&&&&&&/menu&&&&&&&&&menuGroup&id=&112000&&name=&廊坊银行解放道支行&&&&&&&&&&&&menu&id=&112200&&name=&廊坊银行三大街支行&&&&&&&&&&&&&&&/menu&&&&&&&&&&&menu&id=&112100&&name=&廊坊银行广阳道支行&&&&&&&&&&&&&&&/menu&&&&&&&&&/menuGroup&&&&&&/menuGroup&&&&/menuGroup&&&
（2）UL - LI&层次结构
Html代码&&
&ul&&&&&li&廊坊银行总行&/li&&&&&ul&&&&&&li&廊坊分行&/li&&&&&&ul&&&&&&&&li&廊坊银行开发区支行&/li&&&&&&&&&&&&&&li&廊坊银行解放道支行&/li&&&&&&&&&ul&&&&&&&&&&li&廊坊银行三大街支行&/li&&&&&&&&&&li&廊坊银行广阳道支行&/li&&&&&&&&&/ul&&&&&&&&&li&廊坊银行金光道支行&/li&&&&&&/ul&&&&&&/ul&&&&&/ul&&&&
（3）TABLE层次结构
Html代码&&
&table&&&&tr&&td&廊坊银行总行&/td&&/tr&&&&tr&&td&&&廊坊分行&/td&&/tr&&&&tr&&td&&&&&廊坊银行开发区支行&/td&&/tr&&&&tr&&td&&&&&廊坊银行解放道支行&/td&&/tr&&&&tr&&td&&&&&&&廊坊银行三大街支行&/td&&/tr&&&&tr&&td&&&&&&&廊坊银行广阳道支行&/td&&/tr&&&&tr&&td&&&&&廊坊银行金光道支行&/td&&/tr&&&&/table&&&
另外对TreeGrid树形表格也有一定的价值：
&& 1、&&一次性构造树形表格，实现数据分级展示
&& 2、&&通过更换比较器，实现对不同表格列的全排序（全排序指的是对所有页的数据进行排序，而不是只对当前页的数据排序）
&& 3、&&实现对树形表格的完整分页（每次分页时，只取固定数目的第一层节点，之后调用toString方法，展示出完 整条数的分级数据）
五、参考书籍
&&&1、Mark Allen Weiss，数据结构与算法分析（Java语言描述）
&& 2、Bruce Eckel，Thinking In Java Third Edition
&& 3、David Flanagan，JavaScript: The Definitive Guide, 5th Edition
&& 4、OCA Oracle Database 11g SQL Fundamentals I Exam Guide
六、联系方式
另一篇也很不错 &&& &&
&&相关文章推荐
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：3531次
排名：千里之外实现代码：
public function findChild(&$data, $parent_id = 0) {
$rootList = array();
foreach ($data as $key =& $val) {
if ($val['parent_id'] == $parent_id) {
$rootList[]
unset($data[$key]);
return $rootL
public function getTree(&$data, $parent_id = 0) {
$Model = M('tiku_point');
$childs = $this-&findChild($data, $parent_id);
if (empty($childs)) {
foreach ($childs as $key =& $val) {
$result = $Model-&where(&parent_id=&.$val['id'])-&find();
if ($result) {
$treeList = $this-&getTree($data, $val['id']);
if ($treeList !== null) {
$childs[$key]['childs'] = $treeL
//调用方法
public function getAllPoints(){
        $Model = M('tiku_point');
        $child_data = $Model-&where(&course_id=3&)-&select(); //获取所有知识点
        $data = $this-&getTree($child_data,$pid = 0);
        var_dump($data);
    }
&&相关文章推荐
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：75538次
积分：1468
积分：1468
排名：千里之外
原创：78篇
转载：19篇
(1)(2)(2)(4)(2)(2)(10)(5)(9)(4)(2)(13)(18)(2)(1)(7)(13)