`
v5browser
  • 浏览: 1138532 次
社区版块
存档分类
最新评论

新概念智能树形菜单--利用加权多叉树结合JavaScript树形控件实现

 
阅读更多
一、 智能树形菜单的概念
在描述智能树形菜单的概念之前，请先阅读我的上一篇文章《多叉树结合JavaScript树形控件实现无限级树形菜单（一种构建多级有序树形结构JSON（或XML）数据源的方法）》，请点击链接查看：http://www.iteye.com/topic/1122125，阅读完上一篇文章之后，再继续向下阅读，因为这两篇文章是紧密联系、前后关联的，谢谢。

大家都知道树形菜单，不管在基于什么样的技术开发的系统上，树形菜单都是用户界面中非常常用的一种菜单形式，在目前市场上常见的JavaScript框架及组件库中均包含自己的树形控件，例如JQuery、Dojo、Yahoo UI、Ext JS等，还有一些独立的树形控件，例如dhtmlxtree等，这些树形控件完美的解决了层次数据的展示问题。那么树形菜单发展到现在就算完美了吗？还有没有进一步的发展空间呢？还有没有进一步的完善空间呢？答案是肯定的。在这篇文章里，我提出一种新的想法对树形菜单进行扩展，也许会给您的项目带来一些新的用户体验，我管这种扩展型的树形菜单叫做“智能树形菜单”。那么智能树形菜单和普通的树形菜单到底有什么区别呢，它到底智能在哪呢，让我们先来看一组用例场景：

网民高小宝是一名网上银行的忠实用户，他经常利用网银办理各种银行业务，假设高小宝在
某某银行开通了网上银行功能，他回到家之后，想试验一下这个新的网银系统，于是他首次登录了某某银行的网上银行，登录成功后，系统展示界面如下所示（简略概要图）：
图1.1

他想给自己的朋友李小磊转一笔钱，于是他在界面左上角的“输入交易功能关键字”输入框中输入“转账”二字，点击“搜索”按钮，查询出了如下的结果，如图：
图1.2


他看到左侧的树形菜单区域中搜索出了三个交易功能，分别是行内转账、跨行转账和跨行快速转账，于是他点击跨行转账后，主界面进入跨行转账信息录入界面，高小宝很快完成了转账操作，如下图：
图1.3

高小宝一看，这个银行的网上银行系统操作这么方便，于是他又陆续使用了以下几个功能，分别是“投资理财->定活互转”、“投资理财->理财产品->产品购买”、“我的贷款->贷款信息查询”、“客户服务->昵称设置”，本次登录他一共使用了五个功能点，其中“转账汇款->跨行转账”功能使用了两次，一次是给朋友李小磊转钱，另一次是给朋友王小然转钱，其他四个功能各使用了一次。


第二天，高小宝又登录了网上银行系统，登录成功后，他看到系统的操作界面和第一次登录时不太一样了，变成了如下样子：
图1.4


他看到昨天使用的五个功能点菜单全部自动展开了，而且菜单顺序也发生了变化：原来排在最后的一级菜单“客户服务”居然移到了“我的贷款”下面，而原来排在第一位的“账户管理”却移到了“客户服务”下面，由于部分菜单自动展开，所以菜单栏右侧出现了滚动条。
不光一级菜单的顺序发生了变化，二级菜单的顺序也发生了变化，原来在“转账汇款”下面的子菜单中，“跨行转账”排在“行内转账”下面，现在却排在了第一位。不光菜单发生了变化，中间主界面也发生了变化，原来是欢迎界面，现在变成了“跨行转账”信息录入界面。
高小宝一看，正合我意，他正想给朋友吴艳清转一笔钱，吴艳清的开户行是工商银行，不是本行，正好需要使用跨行转账功能，于是他很快完成了转账操作。他今天还想通过“定活互转”功能，存一笔定期，由于昨天使用了一次该功能，所以这个功能也默认自动展开，他很容易就看到了这个菜单项，顺利完成了存定期的操作，也就是说功能使用率大于平均功能使用率的功能节点自动展开了（假设有10个功能，功能A和功能B分别被使用了3次和2次，其它功能都被使用了1次，那么平均使用率是（3+2+8）/ 10 = 1.3次，A和B的使用率大于平均使用率，自动展开，其他8个功能的使用率小于1.3，不展开），真智能啊！高小宝心想，看来以后得多多使用网上银行了，太方便了。


好了，读者朋友们，通过上面这组用例场景，相信您已经看出了本文要论述的主题内容，对了，这就是智能树形菜单，现在我们给智能树形菜单下一个完整科学的定义，


智能树形菜单满足如下几个条件：

Html代码 复制代码 收藏代码
  1. A、用户首次登录系统时，功能菜单树全部闭合，并且按照菜单编号排序，且每一层菜单节点都按照这个规则排序，保持整棵功能树兄弟节点横向有序（关于“兄弟节点横向有序”的概念请查看附录：我的上一篇文章《多叉树结合JavaScript树形控件实现无限级树形菜单（一种构建多级有序树形结构JSON（或XML）数据源的方法）》）；
  3. B、系统会自动记录每一个功能路径（功能路径指的是由一级菜单节点到功能叶子节点的一条完整路径，例如“投资理财->理财产品->产品购买”就是一条功能路径）的使用率；
  5. C、系统提供菜单节点搜索功能，用户可以输入菜单节点关键字，系统会搜索出包含关键字的所有功能路径，并展示出搜索结果；
  7. D、用户再次登录系统时，功能菜单重新排序，并且部分展开，其规则如下：
  8. （1）整棵功能菜单树按照使用率加节点编号的方式排序，先按使用率排序，使用率相同的情况下按照节点编号排序，保持兄弟节点横向有序；
  9. （2）热点功能自动展开（热点功能指的是功能使用率大于所有功能平均使用率的功能叶子节点，例如在上面的用例场景中，高小宝第一次使用网银时，“跨行转账”被使用了两次，“定活互转”、“产品购买”、“贷款信息查询”、“昵称设置”都被使用了一次，其他功能被使用了零次，假设一共有30个功能，那么功能平均使用率是（2+1+1+1+1）/ 30 = 0.2， 这五个功能的使用率均大于0.2，所以都属于热点功能）
  11. E、系统主界面默认进入焦点功能（焦点功能指的是热点功能中使用率最高的功能）的操作界面；

好了，智能树形菜单的概念就介绍完了，下面讲述详细实现方案。

二、 详细实现方案
在《多叉树结合JavaScript树形控件实现无限级树形菜单（一种构建多级有序树形结构JSON（或XML）数据源的方法）》一文中，谈到了多叉树，智能树形菜单就可以在多叉树的基础上进行扩展，实现概念定义中所描述的所有功能，下面介绍详细设计方案。

下面这张图就是扩展之后的多叉树，并且根据这张图定义了一系列名词概念，如图所示：
图1.5

我们先根据这张图定义一组名词概念：
1、 菜单树
所有菜单可以抽象成一棵菜单树，为了保持树的完整性，在一级菜单上面加了一个虚拟的根节点，每个节点由两个值组成，用逗号分割，前一个值是菜单节点编号，后一个值是节点权值，默认权值都为1。

2、节点权值
为了描述某一个节点在其兄弟节点之中的优先级（也就是功能使用率），用一个数值来表示，就叫节点权值。

3、功能叶子节点
菜单树中的叶子节点，下面不再下挂其他子功能节点。

4、功能路径
由根节点到功能叶子节点的一条完整路径，例如图中的蓝色线条部分，即 “根->3->32->323”就是一条功能路径，上图的菜单树中共有13条功能路径，您可以数一数，呵呵。

5、功能路径权值
功能路径权值由功能路径中所有节点的权值由父到子拼接而成，例如路径“根->3->32->323”的路径权值是“111”。

6、 优先功能路径
指的是功能路径权值最高的那一条路径，如上图菜单树中的红色线条部分，该路径为“根->1->11”，它的路径权值是“32”。路径权值比较的规则是逐级比较，“32”的第一级是3，“111”的第一级是1，所以“32”大于“111”，路径权值相同时比较节点编号，也就是用权值加节点编号进行比较，例如路径“根->1->11”和路径“根->1->12->121”，它们的路径权值分别是“32”和“322”，当比较到第二级时，节点权值都是2，但是由于节点11比节点12的编号小，所以节点11排列在节点12前面，也就是说功能路径“根->1->11”的优先级排在“根->1->12->121”之前。

7、功能叶子列表
当构造好一棵菜单树后，通过深度优先先序遍历，找到所有叶子节点，并将其存放在一个列表里面，这个列表叫做功能叶子列表。

8、功能叶子权值
功能叶子节点的权值叫做功能叶子权值。

9、热点功能叶子
功能叶子权值大于所有功能叶子节点的平均权值的叶子节点，例如上图中功能叶子列表中的前两个节点：11和121，其权值分别是2和2，而叶子节点的平均权值是1.15，用数学语言描述就是权值大于加权平均数的功能叶子节点。

10、焦点功能叶子
热点功能叶子中权值最高的叶子叫做焦点功能叶子，如果权值相等，则比较节点编号，节点编号优先的叶子为焦点功能叶子。

11、功能路径可见
在菜单节点中增加一个“是否可见”属性，如果一条功能路径中所有节点的“是否可见”属性为true，那么称该条路径可见，否则该条路径不可见，所谓不可见，指的是不向用户展示这条功能路径。

12、菜单节点搜索
指的是在整棵功能树的所有节点中按照节点关键字查找包含该关键字的菜单节点。

13、功能路径筛选
指的是对整棵树的功能路径的可见性进行重新设置，首先将所有节点设置为不可见，然后根据菜单节点的搜索结果，将包含该菜单节点的所有功能路径设置为可见，也就是向用户展示菜单节点搜索的结果。

14、增加功能路径权值
指的是将包含某一功能叶子节点的一条完整功能路径上的所有节点的权值增加相同的幅度（例如将某一功能路径上的所有节点权值加1）。

我们可以把这棵加了节点权值的多叉树叫做加权多叉树，英文名称叫weighted multiple tree，简称W-M-Tree。


好了，定义完名词概念之后，用下面一组图来展示加权多叉树的变化过程。


图一，用户首次登录系统时，在服务器端构造出加权多叉树和功能叶子列表：
图1.6

其中黄色圆圈代表功能叶子节点。

构造出这棵树之后，向客户端的JavaScript树形控件返回树形结构的JSON字符串，返回如下内容：

Js代码 复制代码 收藏代码
  1. {
  2. id: '0',
  3. text: '根',
  4. children: [
  5. {
  6. id: '1',
  7. text: '1',
  8. children: [
  9. {
  10. id: '11',
  11. text: '11',
  12. leaf: true
  13. },
  14. {
  15. id: '12',
  16. text: '12',
  17. children: [
  18. {
  19. id: '121',
  20. text: '121',
  21. leaf: true
  22. },
  23. {
  24. id: '122',
  25. text: '122',
  26. leaf: true
  27. },
  28. {
  29. id: '123',
  30. text: '123',
  31. leaf: true
  32. }
  33. ]
  34. }
  35. ]
  36. },
  37. {
  38. id: '2',
  39. text: '2',
  40. children: [
  41. {
  42. id: '21',
  43. text: '21',
  44. leaf: true
  45. },
  46. {
  47. id: '22',
  48. text: '22',
  49. leaf: true
  50. }
  51. ]
  52. },
  53. {
  54. id: '3',
  55. text: '3',
  56. children: [
  57. {
  58. id: '31',
  59. text: '31',
  60. leaf: true
  61. },
  62. {
  63. id: '32',
  64. text: '32',
  65. children: [
  66. {
  67. id: '321',
  68. text: '321',
  69. leaf: true
  70. },
  71. {
  72. id: '322',
  73. text: '322',
  74. leaf: true
  75. },
  76. {
  77. id: '323',
  78. text: '323',
  79. leaf: true
  80. }
  81. ]
  82. }
  83. ]
  84. },
  85. {
  86. id: '4',
  87. text: '4',
  88. children: [
  89. {
  90. id: '41',
  91. text: '41',
  92. leaf: true
  93. },
  94. {
  95. id: '42',
  96. text: '42',
  97. leaf: true
  98. },
  99. {
  100. id: '43',
  101. text: '43',
  102. leaf: true
  103. }
  104. ]
  105. }
  106. ]
  107. }


图二，用户使用关键字“12”在功能叶子列表中进行搜索，并将包含搜索结果的功能路径设置为可见，其他路径设置为不可见，图中红色线条部分为可见路径，其他的为不可见路径，如图所示：
图1.7

进行功能路径筛选后，向客户端返回如下JSON字符串：

Js代码 复制代码 收藏代码
  1. {
  2. id: '0',
  3. text: '根',
  4. children: [
  5. {
  6. id: '1',
  7. text: '1',
  8. children: [
  9. {
  10. id: '12',
  11. text: '12',
  12. children: [
  13. {
  14. id: '121',
  15. text: '121',
  16. leaf: true
  17. },
  18. {
  19. id: '122',
  20. text: '122',
  21. leaf: true
  22. },
  23. {
  24. id: '123',
  25. text: '123',
  26. leaf: true
  27. }
  28. ]
  29. }
  30. ]
  31. }
  32. ]
  33. }

图三，用户再使用关键字“321”在功能叶子列表中进行搜索，搜索结果如图所示：
图1.8

进行功能路径筛选后，向客户端返回如下JSON字符串：

Js代码 复制代码 收藏代码
  1. {
  2. id: '0',
  3. text: '根',
  4. children: [
  5. {
  6. id: '3',
  7. text: '3',
  8. children: [
  9. {
  10. id: '32',
  11. text: '32',
  12. children: [
  13. {
  14. id: '321',
  15. text: '321',
  16. leaf: true
  17. }
  18. ]
  19. }
  20. ]
  21. }
  22. ]
  23. }

到这里，您一定会问：菜单节点搜索必须要在服务器端进行吗，这样响应速度岂不是很慢？是的，这的确是个问题，那么，该功能能否放在客户端来实现呢？通过改造现有的树形控件或者重新开发新的树形控件，利用JavaScript在客户端来实现菜单节点的搜索功能，而无需与服务器进行交互。比如，能否利用JavaScript在客户端构造一棵多叉树，然后采用类似的方法来实现菜单节点的搜索呢？具体实现方法不是本文讨论的重点，本文只是提供一个思路，具体实现还要看您了，呵呵。


图四，用户使用某个功能后，系统将该功能路径权值加1，并将该功能路径上的所有节点的权值更新到数据库中的菜单节点定义表中，如图所示，路径“根->3->32->323”的权值加1，由“111”变成了“222”：
图1.9

图五，当用户退出，再次登录系统后，在服务器端再次构造出加权多叉树和功能叶子列表，此时数据结构变成如下样子：
图2.0

树中红色线条部分为优先功能路径，功能叶子列表中红色圆圈为焦点功能叶子。


图六，用户再次使用某个功能后，系统将该功能路径权值加1，并将该功能路径上的所有节点的权值更新到数据库中的菜单节点定义表中，如图所示，路径“根->1->12->122”的权值加1，由“111”变成了“222”：
图2.1

图七，当用户退出，再次登录系统后，在服务器端再次构造出加权多叉树和功能叶子列表，此时数据结构变成如下样子：
图2.2

树中红色线条部分根据路径权值和节点编号重新进行了兄弟节点横向排序；
功能叶子列表中红色圆圈为热点叶子，现在有两个热点叶子了，其中122为焦点叶子。

现在服务器向客户端返回的JSON字符串变成了如下：

Js代码 复制代码 收藏代码
  1. {
  2. id: '0',
  3. text: '根',
  4. children: [
  5. {
  6. id: '1',
  7. text: '1',
  8. children: [
  9. {
  10. id: '12',
  11. text: '12',
  12. children: [
  13. {
  14. id: '122',
  15. text: '122',
  16. leaf: true
  17. },
  18. {
  19. id: '121',
  20. text: '121',
  21. leaf: true
  22. },
  23. {
  24. id: '123',
  25. text: '123',
  26. leaf: true
  27. }
  28. ]
  29. },
  30. {
  31. id: '11',
  32. text: '11',
  33. leaf: true
  34. }
  35. ]
  36. },
  37. {
  38. id: '3',
  39. text: '3',
  40. children: [
  41. {
  42. id: '32',
  43. text: '32',
  44. children: [
  45. {
  46. id: '323',
  47. text: '323',
  48. leaf: true
  49. },
  50. {
  51. id: '321',
  52. text: '321',
  53. leaf: true
  54. },
  55. {
  56. id: '322',
  57. text: '322',
  58. leaf: true
  59. }
  60. ]
  61. },
  62. {
  63. id: '31',
  64. text: '31',
  65. leaf: true
  66. }
  67. ]
  68. },
  69. {
  70. id: '2',
  71. text: '2',
  72. children: [
  73. {
  74. id: '21',
  75. text: '21',
  76. leaf: true
  77. },
  78. {
  79. id: '22',
  80. text: '22',
  81. leaf: true
  82. }
  83. ]
  84. },
  85. {
  86. id: '4',
  87. text: '4',
  88. children: [
  89. {
  90. id: '41',
  91. text: '43211',
  92. leaf: true
  93. },
  94. {
  95. id: '42',
  96. text: '42',
  97. leaf: true
  98. },
  99. {
  100. id: '43',
  101. text: '43',
  102. leaf: true
  103. }
  104. ]
  105. }
  106. ]
  107. }

对于热点功能叶子自动展开，和系统默认进入焦点功能界面这两个功能，只需要客户端通过AJAX的方式从服务器端的功能叶子列表中取出热点功能叶子和焦点功能叶子的节点编号后，在客户端通过编程处理，取热点功能叶子的方法很简单，只需要取出叶子权值大于叶子平均权值的节点即可，然后再找到一个权值最大的叶子就是焦点功能叶子；至于如何展开树形控件的叶子节点本文不做叙述，那是树形控件要实现的功能。

三、 源代码实现（服务器端JAVA代码演示）

以下代码拷贝出来后可以直接运行测试（注：关于菜单节点搜索功能，这里用java来演示，在服务器端进行，系统响应速度很慢，应该放在客户端实现）：

Java代码 复制代码 收藏代码
  1. package test;
  3. import java.math.BigDecimal;
  4. import java.util.ArrayList;
  5. import java.util.Comparator;
  6. import java.util.HashMap;
  7. import java.util.Iterator;
  8. import java.util.List;
  9. import java.util.Map;
  10. import java.util.Set;
  11. import java.util.Collections;
  13. /**
  14. * 功能菜单树类
  15. */
  16. public class FunctionTree {
  18. public static void main(String[] args) {
  19. // 读取层次数据结果集列表
  20. List dataList = VirtualDataGenerator.getVirtualResult();
  22. // 构造加权多叉树
  23. Node root = buildWeightedMultiTree(dataList);
  25. // 构造功能叶子列表
  26. List functionLeafList = buildFunctionLeafList(root);
  28. // 对多叉树重新进行横向排序
  29. root.sortChildren();
  30. // 输出首次登录后的树形菜单
  31. System.out.println("首次登录时的树形菜单：\n" + root.toString());
  33. // 进行菜单节点搜索（即功能路径筛选）
  34. searchTreeNode(root, "321");
  36. // 输出搜索结果
  37. System.out.println("搜索后的树形菜单：\n" + root.toString());
  39. // 增加功能路径权值
  40. increaseRouteWeight(root, functionLeafList, "122");
  41. increaseRouteWeight(root, functionLeafList, "323");
  43. // 对多叉树重新进行横向排序
  44. root.sortChildren();
  45. // 输出权值变化后的树形菜单
  46. System.out.println("路径权值变化后再次登录时的树形菜单：\n" + root.toString());
  48. // 获取热点功能叶子
  49. List hotFunctionLeaf = getHotFunctionLeaf(functionLeafList);
  51. // 输出热点功能叶子
  52. printHotFunctionLeaf(hotFunctionLeaf);
  54. // 程序输出结果如下：
  55. // 首次登录时的树形菜单：
  56. // {id : '0', text : '根', children : [{id : '1', text : '1', children : [{id : '11', text : '11', leaf : true},{id : '12', text : '12', children : [{id : '121', text : '121', leaf : true},{id : '122', text : '122', leaf : true},{id : '123', text : '123', leaf : true}]}]},{id : '2', text : '2', children : [{id : '21', text : '21', leaf : true},{id : '22', text : '22', leaf : true}]},{id : '3', text : '3', children : [{id : '31', text : '31', leaf : true},{id : '32', text : '32', children : [{id : '321', text : '321', leaf : true},{id : '322', text : '322', leaf : true},{id : '323', text : '323', leaf : true}]}]},{id : '4', text : '4', children : [{id : '41', text : '41', leaf : true},{id : '42', text : '42', leaf : true},{id : '43', text : '43', leaf : true}]}]}
  57. // 搜索后的树形菜单：
  58. // {id : '0', text : '根', children : [{id : '3', text : '3', children : [{id : '32', text : '32', children : [{id : '321', text : '321', leaf : true}]}]}]}
  59. // 路径权值变化后再次登录时的树形菜单：
  60. // {id : '0', text : '根', children : [{id : '1', text : '1', children : [{id : '12', text : '12', children : [{id : '122', text : '122', leaf : true},{id : '121', text : '121', leaf : true},{id : '123', text : '123', leaf : true}]},{id : '11', text : '11', leaf : true}]},{id : '3', text : '3', children : [{id : '32', text : '32', children : [{id : '323', text : '323', leaf : true},{id : '321', text : '321', leaf : true},{id : '322', text : '322', leaf : true}]},{id : '31', text : '31', leaf : true}]},{id : '2', text : '2', children : [{id : '21', text : '21', leaf : true},{id : '22', text : '22', leaf : true}]},{id : '4', text : '4', children : [{id : '41', text : '41', leaf : true},{id : '42', text : '42', leaf : true},{id : '43', text : '43', leaf : true}]}]}
  61. // 热点功能叶子：
  62. // [{id : '323', text : '323', leaf : true}, {id : '122', text : '122', leaf : true}]
  63. }
  65. /**
  66. * 构造加权多叉树
  67. * @return
  68. */
  69. public static Node buildWeightedMultiTree(List dataList) {
  70. // 节点列表（散列表，用于临时存储节点对象）
  71. HashMap nodeList = new HashMap();
  72. // 根节点
  73. Node root = null;
  74. // 根据结果集构造节点列表（存入散列表）
  75. for (Iterator it = dataList.iterator(); it.hasNext();) {
  76. Map dataRecord = (Map) it.next();
  77. Node node = new Node();
  78. node.id = (String) dataRecord.get("id");
  79. node.text = (String) dataRecord.get("text");
  80. node.parentId = (String) dataRecord.get("parentId");
  81. node.weight = Integer.parseInt((String) dataRecord.get("weight"));
  82. nodeList.put(node.id, node);
  83. }
  84. // 构造无序的多叉树
  85. Set entrySet = nodeList.entrySet();
  86. for (Iterator it = entrySet.iterator(); it.hasNext();) {
  87. Node node = (Node) ((Map.Entry) it.next()).getValue();
  88. if (node.parentId == null || node.parentId.equals("")) {
  89. root = node;
  90. } else {
  91. ((Node) nodeList.get(node.parentId)).addChild(node);
  92. // 在节点中增加一个父节点的引用
  93. node.parentNode = (Node) nodeList.get(node.parentId);
  94. }
  95. }
  97. return root;
  98. }
  100. /**
  101. * 构造功能叶子列表
  102. * @param root
  103. * @return
  104. */
  105. public static List buildFunctionLeafList(Node root) {
  106. List functionLeafList = new ArrayList();
  107. root.initializeLeafList(functionLeafList);
  108. return functionLeafList;
  109. }
  111. /**
  112. * 进行菜单节点搜索（即功能路径筛选）
  113. * @param root
  114. * @param keyWord
  115. */
  116. public static void searchTreeNode(Node root, String keyWord) {
  117. // 首先设置整棵树的功能路径为不可见
  118. root.setTreeNotVisible();
  119. // 在整棵功能树中搜索包含关键字的节点，并进行路径筛选
  120. root.searchTreeNode(keyWord);
  121. }
  123. /**
  124. * 增加功能路径权值
  125. * @param root
  126. */
  127. public static void increaseRouteWeight(Node root, List functionLeafList, String nodeId) {
  128. // 首先设置整棵树的功能路径为可见
  129. root.setTreeVisible();
  130. // 对包含功能叶子节点的路径权值加1
  131. for (Iterator it = functionLeafList.iterator(); it.hasNext();) {
  132. Node leafNode = (Node) it.next();
  133. if (leafNode.id.equals(nodeId)) {
  134. leafNode.increaseRouteWeight();
  135. }
  136. }
  137. }
  139. /**
  140. * 获取热点功能叶子
  141. * @param functionLeafList
  142. * @return
  143. */
  144. public static List getHotFunctionLeaf(List functionLeafList) {
  145. int count = 0;
  146. int totalWeight = 0;
  147. BigDecimal avgWeight;
  148. for (Iterator it = functionLeafList.iterator(); it.hasNext();) {
  149. Node node = (Node) it.next();
  150. totalWeight += node.weight;
  151. count++;
  152. }
  153. avgWeight = (new BigDecimal(totalWeight)).divide(new BigDecimal(count), 2, BigDecimal.ROUND_HALF_UP);
  154. List retList = new ArrayList();
  155. for (Iterator it = functionLeafList.iterator(); it.hasNext();) {
  156. Node node = (Node) it.next();
  157. if (node.weight > avgWeight.doubleValue()) {
  158. retList.add(node);
  159. }
  160. }
  161. return retList;
  162. }
  164. /**
  165. * 输出热点功能叶子
  166. * @param hotFunctionLeaf
  167. */
  168. public static void printHotFunctionLeaf(List hotFunctionLeaf) {
  169. System.out.println("热点功能叶子：\n" + hotFunctionLeaf);
  170. }
  173. }
  176. /**
  177. * 节点类
  178. */
  179. class Node {
  180. /**
  181. * 节点编号
  182. */
  183. public String id;
  184. /**
  185. * 节点内容
  186. */
  187. public String text;
  188. /**
  189. * 父节点编号
  190. */
  191. public String parentId;
  192. /**
  193. * 节点权值
  194. */
  195. public int weight;
  196. /**
  197. * 是否可见，默认为true
  198. */
  199. public boolean visible = true;
  200. /**
  201. * 父节点引用
  202. */
  203. public Node parentNode;
  204. /**
  205. * 孩子节点列表
  206. */
  207. private Children children = new Children();
  209. // 添加孩子节点
  210. public void addChild(Node node) {
  211. this.children.addChild(node);
  212. }
  214. // 先序遍历，拼接JSON字符串
  215. public String toString() {
  216. if (visible) {
  217. String result = "{"
  218. + "id : '" + id + "'"
  219. + ", text : '" + text + "'";
  221. if (children != null && children.getSize() != 0) {
  222. result += ", children : " + children.toString();
  223. } else {
  224. result += ", leaf : true";
  225. }
  227. return result + "}";
  228. } else {
  229. return "";
  230. }
  231. }
  233. // 兄弟节点横向排序
  234. public void sortChildren() {
  235. if (children != null && children.getSize() != 0) {
  236. children.sortChildren();
  237. }
  238. }
  240. // 先序遍历，构造功能叶子列表
  241. public void initializeLeafList(List leafList) {
  242. if (children == null || children.getSize() == 0) {
  243. leafList.add(this);
  244. } else {
  245. children.initializeLeafList(leafList);
  246. }
  247. }
  249. // 先序遍历，设置该节点下的所有功能路径为不可见
  250. public void setTreeNotVisible() {
  251. visible = false;
  252. if (children != null && children.getSize() != 0) {
  253. children.setTreeNotVisible();
  254. }
  255. }
  257. // 先序遍历，设置该节点下的所有功能路径为可见
  258. public void setTreeVisible() {
  259. visible = true;
  260. if (children != null && children.getSize() != 0) {
  261. children.setTreeVisible();
  262. }
  263. }
  265. // 设置包含该叶子节点的功能路径可见
  266. public void setRouteVisible() {
  267. visible = true;
  268. for (Node parentNode = this.parentNode; parentNode != null; parentNode = parentNode.parentNode) {
  269. parentNode.visible = true;
  270. }
  271. }
  273. // 对包含该叶子节点的功能路径权值加1
  274. public void increaseRouteWeight() {
  275. weight++;
  276. updateNodeWeightToDB(this);
  277. for (Node parentNode = this.parentNode; parentNode != null; parentNode = parentNode.parentNode) {
  278. parentNode.weight++;
  279. updateNodeWeightToDB(parentNode);
  280. }
  281. }
  283. // 更新节点权值到数据库
  284. public void updateNodeWeightToDB(Node node) {
  285. // 暂时不实现，实际应用中需要实现该方法
  286. // 或者用户退出系统时，遍历整棵树，统一更新所有节点的权值到数据库中，应该这样做比较好，一次性统一处理
  287. }
  289. // 先序遍历，搜索菜单节点，同时进行功能路径过滤
  290. public void searchTreeNode(String keyWord) {
  291. if (this.text.indexOf(keyWord) > -1) {
  292. this.setTreeVisible();
  293. this.setRouteVisible();
  294. } else {
  295. if (children != null && children.getSize() != 0) {
  296. children.searchTreeNode(keyWord);
  297. }
  298. }
  299. }
  300. }
  302. /**
  303. * 孩子列表类
  304. */
  305. class Children {
  306. private List list = new ArrayList();
  308. public int getSize() {
  309. return list.size();
  310. }
  312. public void addChild(Node node) {
  313. list.add(node);
  314. }
  316. // 拼接孩子节点的JSON字符串
  317. public String toString() {
  318. String result = "[";
  319. for (Iterator it = list.iterator(); it.hasNext();) {
  320. Node node = (Node) it.next();
  321. if (node.visible) {
  322. result += node.toString();
  323. result += ",";
  324. }
  325. }
  326. result = result.substring(0, result.length() - 1);
  327. result += "]";
  328. return result;
  329. }
  331. // 在孩子节点中寻找功能叶子节点
  332. public void initializeLeafList(List leafList) {
  333. for (Iterator it = list.iterator(); it.hasNext();) {
  334. ((Node) it.next()).initializeLeafList(leafList);
  335. }
  336. }
  338. // 孩子节点排序
  339. public void sortChildren() {
  340. // 对本层节点进行排序
  341. // 可根据不同的排序属性，传入不同的比较器，这里传入优先级比较器
  342. Collections.sort(list, new NodePriorityComparator());
  343. // 对每个节点的下一层节点进行排序
  344. for (Iterator it = list.iterator(); it.hasNext();) {
  345. ((Node) it.next()).sortChildren();
  346. }
  347. }
  349. // 设置孩子节点为不可见
  350. public void setTreeNotVisible() {
  351. for (Iterator it = list.iterator(); it.hasNext();) {
  352. ((Node) it.next()).setTreeNotVisible();
  353. }
  354. }
  356. // 设置孩子节点为可见
  357. public void setTreeVisible() {
  358. for (Iterator it = list.iterator(); it.hasNext();) {
  359. ((Node) it.next()).setTreeVisible();
  360. }
  361. }
  363. // 搜索菜单节点，同时进行功能路径过滤
  364. public void searchTreeNode(String keyWord) {
  365. for (Iterator it = list.iterator(); it.hasNext();) {
  366. ((Node) it.next()).searchTreeNode(keyWord);
  367. }
  368. }
  369. }
  371. /**
  372. * 节点比较器
  373. */
  374. class NodePriorityComparator implements Comparator {
  375. // 按照 （节点权值+节点编号） 比较
  376. public int compare(Object o1, Object o2) {
  377. // 按权值由大到小排序
  378. int w1 = ((Node)o1).weight;
  379. int w2 = ((Node)o2).weight;
  380. if (w1 < w2) {
  381. return 1;
  382. } else if (w1 > w2) {
  383. return -1;
  384. } else { // 权值相等时，按照节点编号由小到大排序
  385. int i1 = Integer.parseInt(((Node)o1).id);
  386. int i2 = Integer.parseInt(((Node)o2).id);
  387. return i1 < i2 ? -1 : (i1 == i2 ? 0 : 1);
  388. }
  389. }
  390. }
  392. /**
  393. * 构造虚拟的层次数据
  394. */
  395. class VirtualDataGenerator {
  396. // 构造无序的结果集列表，实际应用中，该数据应该从数据库中查询获得；
  397. public static List getVirtualResult() {
  398. List dataList = new ArrayList();
  400. HashMap dataRecord1 = new HashMap();
  401. dataRecord1.put("id", "0");
  402. dataRecord1.put("text", "根");
  403. dataRecord1.put("parentId", "");
  404. dataRecord1.put("weight", "1");
  406. HashMap dataRecord2 = new HashMap();
  407. dataRecord2.put("id", "1");
  408. dataRecord2.put("text", "1");
  409. dataRecord2.put("parentId", "0");
  410. dataRecord2.put("weight", "1");
  412. HashMap dataRecord3 = new HashMap();
  413. dataRecord3.put("id", "2");
  414. dataRecord3.put("text", "2");
  415. dataRecord3.put("parentId", "0");
  416. dataRecord3.put("weight", "1");
  418. HashMap dataRecord4 = new HashMap();
  419. dataRecord4.put("id", "3");
  420. dataRecord4.put("text", "3");
  421. dataRecord4.put("parentId", "0");
  422. dataRecord4.put("weight", "1");
  424. HashMap dataRecord5 = new HashMap();
  425. dataRecord5.put("id", "4");
  426. dataRecord5.put("text", "4");
  427. dataRecord5.put("parentId", "0");
  428. dataRecord5.put("weight", "1");
  430. HashMap dataRecord6 = new HashMap();
  431. dataRecord6.put("id", "11");
  432. dataRecord6.put("text", "11");
  433. dataRecord6.put("parentId", "1");
  434. dataRecord6.put("weight", "1");
  436. HashMap dataRecord7 = new HashMap();
  437. dataRecord7.put("id", "12");
  438. dataRecord7.put("text", "12");
  439. dataRecord7.put("parentId", "1");
  440. dataRecord7.put("weight", "1");
  442. HashMap dataRecord8 = new HashMap();
  443. dataRecord8.put("id", "21");
  444. dataRecord8.put("text", "21");
  445. dataRecord8.put("parentId", "2");
  446. dataRecord8.put("weight", "1");
  448. HashMap dataRecord9 = new HashMap();
  449. dataRecord9.put("id", "22");
  450. dataRecord9.put("text", "22");
  451. dataRecord9.put("parentId", "2");
  452. dataRecord9.put("weight", "1");
  454. HashMap dataRecord10 = new HashMap();
  455. dataRecord10.put("id", "31");
  456. dataRecord10.put("text", "31");
  457. dataRecord10.put("parentId", "3");
  458. dataRecord10.put("weight", "1");
  460. HashMap dataRecord11 = new HashMap();
  461. dataRecord11.put("id", "32");
  462. dataRecord11.put("text", "32");
  463. dataRecord11.put("parentId", "3");
  464. dataRecord11.put("weight", "1");
  466. HashMap dataRecord12 = new HashMap();
  467. dataRecord12.put("id", "41");
  468. dataRecord12.put("text", "41");
  469. dataRecord12.put("parentId", "4");
  470. dataRecord12.put("weight", "1");
  472. HashMap dataRecord13 = new HashMap();
  473. dataRecord13.put("id", "42");
  474. dataRecord13.put("text", "42");
  475. dataRecord13.put("parentId", "4");
  476. dataRecord13.put("weight", "1");
  478. HashMap dataRecord14 = new HashMap();
  479. dataRecord14.put("id", "43");
  480. dataRecord14.put("text", "43");
  481. dataRecord14.put("parentId", "4");
  482. dataRecord14.put("weight", "1");
  484. HashMap dataRecord15 = new HashMap();
  485. dataRecord15.put("id", "121");
  486. dataRecord15.put("text", "121");
  487. dataRecord15.put("parentId", "12");
  488. dataRecord15.put("weight", "1");
  490. HashMap dataRecord16 = new HashMap();
  491. dataRecord16.put("id", "122");
  492. dataRecord16.put("text", "122");
  493. dataRecord16.put("parentId", "12");
  494. dataRecord16.put("weight", "1");
  496. HashMap dataRecord17 = new HashMap();
  497. dataRecord17.put("id", "123");
  498. dataRecord17.put("text", "123");
  499. dataRecord17.put("parentId", "12");
  500. dataRecord17.put("weight", "1");
  502. HashMap dataRecord18 = new HashMap();
  503. dataRecord18.put("id", "321");
  504. dataRecord18.put("text", "321");
  505. dataRecord18.put("parentId", "32");
  506. dataRecord18.put("weight", "1");
  508. HashMap dataRecord19 = new HashMap();
  509. dataRecord19.put("id", "322");
  510. dataRecord19.put("text", "322");
  511. dataRecord19.put("parentId", "32");
  512. dataRecord19.put("weight", "1");
  514. HashMap dataRecord20 = new HashMap();
  515. dataRecord20.put("id", "323");
  516. dataRecord20.put("text", "323");
  517. dataRecord20.put("parentId", "32");
  518. dataRecord20.put("weight", "1");
  520. dataList.add(dataRecord1);
  521. dataList.add(dataRecord2);
  522. dataList.add(dataRecord3);
  523. dataList.add(dataRecord4);
  524. dataList.add(dataRecord5);
  525. dataList.add(dataRecord6);
  526. dataList.add(dataRecord7);
  527. dataList.add(dataRecord8);
  528. dataList.add(dataRecord9);
  529. dataList.add(dataRecord10);
  530. dataList.add(dataRecord11);
  531. dataList.add(dataRecord12);
  532. dataList.add(dataRecord13);
  533. dataList.add(dataRecord14);
  534. dataList.add(dataRecord15);
  535. dataList.add(dataRecord16);
  536. dataList.add(dataRecord17);
  537. dataList.add(dataRecord18);
  538. dataList.add(dataRecord19);
  539. dataList.add(dataRecord20);
  541. return dataList;
  542. }
  543. }

四、 联系方式
memorymultitree@163.com

分享到：
| 多叉树结合JavaScript树形控件实现无限级树 ...
评论
发表评论

您还没有登录,请您登录后再发表评论

相关推荐

Magicbox
Global site tag (gtag.js) - Google Analytics