数组,根据判断条件找到满足条件的叶子节点。
如果只是搜索叶子的话,建立一个叶子引用的列表就可以了,但是我们这里可能对多个层级的节点进行筛选或者向上加权,按照那种方法的话,有多少层就得建立多少个节点列表,每一层都得建立一个节点列表,筛选的时候,在某一层的节点列表中进行筛选,这样就太麻烦了。
既然是线性查找,那么可以用节点链表的形式取代这个节点引用数组,也就是说在每个节点中增加两个引用,前一个引用指向同一层级的前一个节点,后一个引用指向同一层级的下一个节点,同一层级的第一个节点和最后一个节点也要建立这种互相引用的关系,也就是说对同一层级的节点连成一个双向循环链表(其实用单向循环链表就可以,构造双向循环链表也许以后会有用,之所以构造循环链表,是因为横向排序之后,同一层级节点顺序会被打乱,而每次筛选都是从第一个节点开始,所以为了保证遍历到该层级所有节点,需要使用循环链表),从第一个节点开始,逐个向后遍历节点,逐个筛选。
此时一个节点中会包含四种指针,分别是:孩子指针列表、父节点指针、前节点指针、后节点指针,如下图所示:如果对某一层节点(例如对区县级节点)进行向上加权的话,首先需要从根节点开始沿着最左侧路径,找到那一层的第一个节点,然后从这个节点开始沿着链表的指向遍历本层节点,遇到满足条件的节点,就向上加权,如下图所示:蓝色箭头代表节点的遍历的顺序;黄色箭头代表向上加权的顺序,红色线条代表被加权的路径,图中“吉林-gt长春-gt二道区“被加权。
如果对某一层节点(例如对区县级节点)进行筛选的话,首先需要从根节点开始沿着最左侧路径,找到那一层的第一个节点,然后从这个节点开始沿着链表的指向遍历本层节点,遇到满足条件的节点,就向上重新汇总,然后将该节点所在的路径设置为可见,其它路径设置为不可见,如下图所示:蓝色箭头代表节点的遍历的顺序;红色箭头代表向上重新汇总的顺序,绿色线条代表可见的路径,图中“二道区“和”铁东区“为被筛选的节点。
由于这棵树实现了上级节点与下级节点互相引用,同级节点与同级节点互相引用,竖着看是一棵多叉树,横着看,每一层都是一个双向循环链表,所以可以形象的称这棵树叫做“手拉手”树形结构,如图所示:我们也给这棵树起个名字,叫做 hand-in-hand tree,简称 H-Tree。
下面用
JAVA 来演示统计分析系统中的树形结构报表中所描述的五个功能。
比如要做一张类似于如下这样的各个地区的家庭平均月收入统计报表,如图所示:二、源代码演示(演示 4 个功能,分页除外)
Java 代码 1. package test 2. 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 12. 13./ 14. 树形报表类,15. 东北地区家庭平均月收入统计报表16. /17.public class ReportTree 18.19. public static void mainString args 20. // 读取层次数据结果集列表21. List dataList VirtualDataGenerator.getVirtualResult 22.23. // 构造加权多叉树(纵向拉手)24. Node root buildWeightedMultiTreedataList25.26. // 对树的每一层级节点构造双向循环链表(横向拉手)27. buildCircularlyDoublyLinkedListroot28.29. // 从客户级开始,逐级向上汇总指标数据(这里汇总家庭平均 月收入)30. // 汇总时并不是简单的累加,而是计算家庭平均月收入的平均 值31. calculateMeasureroot 532.33. // 指标排序,按各个地区的家庭平均月收入进行排序34. sortMeasureroot35.36. // 输出按家庭平均月收入升序排序后的报表37. System.out.printlnquot按家庭平均月收入升序排序后的报 表:nquot root.toString38.39. // 对家庭平均月收入小于 1000 的家庭进行向上加权,并按权值 排序,也就是说将贫困40.41.家庭数量多的地区排在前面42. upIncreaseRouteWeightAndSortroot 543.44. // 输出向上加权并排序后的报表45. System.out.printlnquot按各个地区的贫困家庭 (家庭平均月收入 小于 1000 的家庭)数量46.47.的多少排序:nquot root.toString48.49. // 对家庭平均月收入小于 1000 的家庭进行筛选并重新汇总,并 按家庭平均月收入排序50.51.,只列出贫困家庭52. filterAndCalculateMeasureroot 553.54. // 输出筛选并排序后的报表55. System.out.printlnquot只统计家庭平均月收入小于 1000 的家 庭:nquot root.toString56.57.58.59. // 树形报表的输出结果,假设这是一个简单的东北地区家庭平 均月收入统计报表,每60.61.一行由 行政地区 家庭平均月收入 组成,如下所示:62. // 按家庭平均月收入升序排序后的报表:63. // --东北地区 9077.2564. // --黑龙江 3461.6765. // --哈尔滨 1792.566. // --南岗区 885.067. // --李盛伟家 880.068. // --李磊家 890.069. // --道外区 2700.070. // --王泉历家 900.071. // --吴艳清家 4500.072. // --齐齐哈尔 6800.073. // --龙沙区 6800.074. // --李龙波家 6000.075. // --李涛家 7600.076. // --吉林 10875.077. // --长春 10875.078. // --二道区 6750.079. // --李雪涛家 3500.080. // --李润杰家 10000.081. // --宽城区 15000.082. // --窦晓峰家 10000.083. // --李坤奇家 20000.084. // --辽宁 13494.3385. // --鞍山 13091.586. // --铁东区 4683.087. // --金城家 666.088. // --王琪跃家 8700.089. // --铁西区 21500.090. // --朱一家 13000.091. // --由建宏家 30000.092. // --辽阳 14300.093. // --东京城 14300.094. // --李建保家 8600.095. // --龙明超家 20000.096. //97. // 按各个地区的贫困家庭(家庭平均月收入小于 1000 的家庭) 数量的多少排序:98. // --东北地区 9077.2599. // --黑龙江 3461.67100. // --哈尔滨 1792.5101. // --南岗区 885.0102. // --李盛伟家 880.0103. // --李磊家 890.0104. // --道外区 2700.0105. // --王泉历家 900.0106. // --吴艳清家 4500.0107. // --齐齐哈尔 6800.0108. // --龙沙区 6800.0109. // --李龙波家 6000.0110. // --李涛家 7600.0111. // --辽宁 13494.33112. // --鞍山 13091.5113. // --铁东区 4683.0114. // --金城家 666.0115. // --王琪跃家 8700.0116. // --铁西区 21500.0117. // --朱一家 13000.0118. // --由建宏家 30000.0119. // --辽阳 14300.0120. // --东京城 14300.0121. // --李建保家 8600.0122. // --龙明超家 20000.0123. // --吉林 10875.0124. // --长春 10875.0125. // --二道区 6750.0126. // --李雪涛家 3500.0127. // --李润杰家 10000.0128. // --宽城区 15000.0129. // --窦晓峰家 10000.0130. // --李坤奇家 20000.0131. //132. // 只统计家庭平均月收入小于 1000 的家庭:133. // --东北地区 834.0134. // --辽宁 666.0135. // --鞍山 666.0136. // --铁东区 666.0137. // --金城家 666.0138. // --黑龙江 890.0139. // --哈尔滨 890.0140. // --南岗区 885.0141. // --李盛伟家 880.0142. // --李磊家 890.0143. // --道外区 900.0144. // --王泉历家 900.0145.146. 147.148. /149. 构造加权多叉树150. return151. /152. public static Node buildWeightedMultiTreeList dataLis t 153. // 节点列表(散列表,用于临时存储节点对象)154. HashMap nodeList new HashMap155. // 根节点156. Node root null157. // 根据结果集构造节点列表(存入散列表)158. for Iterator it dataList.iterator it.hasNext 159. Map dataRecord Map it.next160. Node node new Node161. node.id String dataRecord.getquotidquot162. node.text String dataRecord.getquottextquot163. node.parentId String dataRecord.getquotparen tIdquot164. node.money Double.parseDoubleString dataR ecord.getquotmoneyquot165. nodeList.putnode.id node166. 167. // 构造无序的多叉树168. Set entrySet nodeList.entrySet169. for Iterator it entrySet.iterator it.hasNext 170. Node node Node Map.Entry it.next.get Value171. if node.parentId null node.parentId.equ alsquotquot 172. root node173. else 174. Node nodeList.getnode.parentId.addCh ildnode175. // 在节点中增加一个父节点的引用176. node.parentNode Node nodeList.getnode .parentId177. 178. 179.180. return root181. 182.183. /184. 对树的每一层级节点构造双向循环链表,将处于同一层级的 不同父节点下的子节点首尾相连185. /186. public static void buildCircularlyDoublyLinkedListNod e root 187. // 先将树中的每个父节点下的兄弟节点连成双向链表188. root.buildDoublyLinkedList189. // 再将处于同一层级的不同父节点下的子节点首尾相 连190. for Node firstNode root.getFirstChild firstN ode null firstNode 191.192. firstNode.getFirstChild 193. Node currentParent firstNode.parentNode194. Node nextParent currentParent.nextNode195. while nextParent null ampamp nextParent fir stNode.parentNode 196. currentParent.getLastChild.nextNode 197.198. nextParent.getFirstChild199. nextParent.getFirstChild.previousNode 200.201. currentParent.getLastChild202. currentParent nextParent203. .
上一篇:
基于Java平台的应用系统技术架构规范(试行)_v1
下一篇:
还记得,那年的风车吗?