树形结构的定位
回顾过去，无论是学校的书本上，还是网上各种算法，关于树的各种算法可谓是白花争鸣，然而，从各种评论的题目就能看出，大部分讨论的都是以数据结构为焦点的讨论，当然少不了二叉树，他的应用不用说的确非常的大，然而，实际应用中，却经常有多节点树的存在，那么又如何定位其中的一个节点呢？
1、要分析树，定位节点，主要就是树的查找 。 由于这个树没有什么限制，因此这二叉树的遍历、二分查找法等方法查找在这里不再适用(这里就不介绍了)。 这里，如果树的高度和分支比较小，我们这里可以用2种笨重图遍历： DFS(深度优先，堆栈结构实现),BFS(广度优先，对列结构实现)； 上面这种限制要求： 一切查找都要从节点定义开始： public class Node { private String dataStr; //TODO get / set method . public Node(String str){ dataStr = str; } } 假设，我在程序(或数据库)中限制，每个dataStr(节点数据最大值为1024 byte)，因为上述2种方式的遍历中， 都需要用的递归算法，因此，在定位到需要的数据前，需要将数据存在栈中，因此，当树的高度和分支节点数增加时， 栈内存将被几何方式耗尽，因此上述方法仅适用于数据量小时； 2、对于数据量大时的一个可行方法(其实，只要是一种好方法都很难，这里简单介绍下我认为可行的方法) 一切的查找/定位 都要从定义节点开始；这里我先说明一下我的思路。 1、在定义节点时，在节点结构中增加相应的标示位字段 (String node_label); 如果环境不允许增加字段可以通过在dataStr上作标示位，比如 (dataStr + 分隔符 + node_label ) 2、在插入每个节点时，除了要将相应的用户数据dataStr保存进数据库，同时要产生一个系统唯一的一个 标示符 ：产生系统唯一的字符串方式有很多，比如引用Calendar的当前时间毫秒数，就是唯一的， 但这里的要求不仅要唯一，而且他的主要任务是方便树节点的定位。 /** * 这个方法，主要是在数据库中专门维护一个表，其中2个字段 * code：是我们要使用的标志， * type：这个可以用户扩展，比如dataStr分类时他可以被用上 * **/ public synchronized String getValue(String parent_node_label) { //比如parent_node_label = "-11" ; 则label = "-11-111", (G节点的标志位，C下最大的) String label = getMaxLabel(parent_node_label); //转换处理label："-11-111" 处理后变为 "-11-1111",并保存到数据库中 insert(convert_method(label)); return label; } //TODO updat_method 更新 //TODO delete_method(boolean flag) 级联删除 举一个树形结构的例子：（其中 &^& 代表分隔符） |-----B(dataStr = "B&^&-1") | |-------E(dataStr = "E&^&-11-1") A(根节点)--|-----C(dataStr = "C&^&-11")--| | |-------F(dataStr = "F&^&-11-11") | | | |-------G(dataStr = "G&^&-11-111") | | | ..................... |-----D(dataStr = "D&^&-111") | ................... 了解上面的存储原理后，就可以 定位/查找 你想要的节点了 public List searchSpecialElements(String parent_node_label) throws DBException{ //ORM 处理环境 或者 JDBC StringBuffer sql = new StringBuffer(); sql.append(" select * "); sql.append(" from table_tree ").append(" t1 "); sql.append(" where "); //这里的node_label就是标示位，也可以从dataStr中通过分隔符分离出来的字符 //比如我想查找节点C的直接子节点，这parent_node_label = "-11" if(node_label != null){ sql.append(" t1.node_label like '"). append(parent_node_label).append("%'"); } SQLQuery sqlQuery = getSession().createSQLQuery(sql.toString()); } //如果，你想准确定位某个节点，可以利用数据库直接指定查询， 也可以很高效率的利用标示位，使用类似于二分查找法查找 比如用上面的树结构举例：标志符：label = "-11-11" 即定位了F节点所在位置， 1、 if(label.StringUtil.contain(A.node_label)){ Iterator ite = getSubNodeLabels(A).iterator(); while(ite.hasNext()){ Node instance = (Node)ite.next(); if(label.StringUtil.contain(instance.node_label)){ if(label.equals(instance.node_label)){ //定位成功 } //todo C 的子节点,递归调用 } } } 3、如果用户需要频繁的定位节点，那么上述的方法在性能上也将会成为系统的一个瓶颈， 解决方案： 使Node节点类定义自己的equals();hashCode()函数 (hash函数定义的好坏，对性能有一定影响，碰撞几率越小越好当然)； 这样，在系统运行初始化时，将tree结构上的节点读入到HashMap中进行缓存， 以后，每次获取都就可以直接从此HashMap中获得了 如果，修改了树形结构，根据修改的规模不同，树形内存对象不同分支 //define class.................................... private HashMap cacheTreeInfo; private static final String defauleValue = "noneElement"; public HashaMap get(){ if(cacheTreeInfo == null){ init(); } return cacheTreeInfo } public void init(){ //init cacheTreeInfo; //这里需要根据业务上的不同，可以对树进行分类定义key(唯一) } //刷新内存对象 public void refresh(){ //refresh all tree; } public void refresh(Node node){ //refresh tree info under this node; } public void refreshElement(Node node){ // only refresh this node info } //getElement via Object key //nomal : Best convert Object to Serializable if it used for Stream / database public Object getElement(Object key){ return cacheTreeInfo.getValue(key) ? defauleValue :cacheTreeInfo.getValue(key); } public boolean update(Node node){....} public boolean delete(Node node,boolean flag){.....} .......................................................
一个朋友曾经提出这样的问题：
回答有点局限。 如果现在窗外有一棵苹果树，你想要其中的一个苹果，但是你不能出去。需要别人帮你来取得这个苹果。 你可以通过告诉外面的人你想要第几个分支上的第几个分支上的苹果。来引导外面的人帮你取得苹果。 通过这种方法你可以准确的定位到你想要的苹果。（定位不同于查找，或者说查找应该是定位的一种方法）。 请问你能否提供更多的定位这个苹果的方法？
这个问题可以用我提到的第二种方式解决： 举一个树形结构的例子：（其中 &^& 代表分隔符） |-----B(dataStr = "B&^&-1") | |-------E(dataStr = "E&^&-11-1") A(根节点)--|-----C(dataStr = "C&^&-11")--| | |-------F(dataStr = "F&^&-11-11") | | |-----H(dataStr="H&^&-11-111-1") | |-------G(dataStr = "G&^&-11-111")-----| | | |-----I(dataStr="I&^&-11-111-11") | | | ..................... |-----D(dataStr = "D&^&-111")--| | | | |----................. ...................
如果你站在房间里，告诉窗外的朋友你想要 "苹果I" , 苹果I的标示："-11-111-11" ; 那么定位苹果I的方法就是：分支"-11" 下 ====〉 分支"-11-111" ====> 分支"-11-111-11" 标示符含义：每增加1个字符"-" 代表树延伸一层，或者可以理解为树的高度增加1 比如，苹果I的标示："-11-111-11" 中有3个"-"， 第一个"-"代表树的第一次分支(该层可能包含标示符："-1","-11","-111","-1111",... 但是不会有重复) 第二个"-"代表数的第二次分支(该层可能含有标示符：({"-1-1","-1-11","-1-111"},{"-11-1","-11-11"},{"-111-1"})等等 只要给出该节点标示位，就可知道其上级的标示位，递推其上上级表示位......，根节点 当然也可以从根节点递推，直到当前节点。 另一种定位方法： ******在这种方法之上的另一种定位方法，如果你让窗外的朋友帮你取得苹果I,如果他明白表示符的含义， 也许可以不用从根节点查起，比如 苹果I的标示："-11-111-11" 中有3个"-" ,那么你就可以知道你要定位的苹果在树 的第几层(4)； [那么简单点查找方法]： 你可以直接从第四层的节点查询，比如定义一个模式匹配来查找； [复杂点]： 考虑条件1： 被定位的树的该层上大约有多少节点 考虑条件2： 树的是几叉树，或者平均考虑树的叉数 考虑条件3： 当前是第几层 你可根据一定的公式(条件1，条件2，条件3) 推导出你应该从哪一层开始查询效率可以更高。
--------------------------------------------------------------------------------------
节点定位的一个应用：在Java应用程序、Web应用程序中，随着各种框架的出现，越来越多的配置文件也随之而来。 而配置文件的格式也是也是由形同树状的 分支节点+属性 构成的。 通常，在Java中用于解析配置文件的方法有很多，很多开源软件都提供了这个功能。 目前，网上最流行的XML解析方式就是 DOM4J + XPath 并且这都是开源的，有很好的说明文档和例子文档。 这里，我主要想说说XPath，他的主要作用就是用于定位节点的；(当然有一些统一的规则) 下面我据理说明： ------------------------------------------------------ <A id="a1"> <B id="b1"> <C id="c1"> <B name="b"/> <D id="d1"/> <E id="e1"/> <E id="e2"/> </C> </B> <B id="b2"/> <C id="c2"> <B/> <D id="d2"/> <F/> </C> <E/> </A> ----------------------------------------- ***[路径匹配方法]*** （1）用“/”指示节点路径 如“/A/C/D” 表示节点"A"的子节点"C"的子节点"D"，即id值为d2的D节点， “/”表示根节点。
（2）用“//” 表示所有路径以"//"后指定的子路径结尾的元素 如“//E” 表示所有E元素，结果是所有三个E元素，如“//C/E”表示所有父节点为C的E元素，结果是id值为e1和e2的两个E元素 。
（3）用“*” 表示路径的通配符 如“/A/B/C/*”表示 A元素→B元素→C元素下的所有子元素，即name值为b的B元素、 id值为d1的D元素和id值为e1和e2的两个E元素 “/*/*/D”表示上面有两级节点的D元素，匹配结果是id值为d2的D元素 ，如“//*”表示所有的元素。
-------------------------------------------- ***[位置匹配方法]*** 对于每一个元素，它的各个子元素是有序的。
(1) /A/B/C[1]表示A元素→B元素→C元素的第一个子元素，得到name值为b的B元素
(2) /A/B/C[last()]表示A元素→B元素→C元素的最后一个子元素，得到id值为e2的E元素
(3) /A/B/C[position()>1]表示A元素→B元素→C元素之下的位置号大于1的元素， 得到id值为d1的D元素和两个具有id值的E元素 -------------------------------------------- ***[属性及属性值匹配方法]*** 在XPath中可以利用属性及属性值来匹配元素，要注意的是，元素的属性名前要有"@"前缀。例如：
(1) //B[@id]表示所有具有属性id的B元素，结果为id值为b1和b2的两个B元素
(2) //B[@*]表示所有具有属性的B元素，结果为两个具有id属性的B元素和一个具有name属性B元素
(3) //B[not(@*)]表示所有不具有属性的B元素，结果为A元素→C元素下的B元素
(4) //B[@id="b1"] id值为b1的B元素，结果为A元素下的B元素
***[亲属关系匹配]***
XML文档可归结为树型结构，因此任何一个节点都不是孤立的。通 常我们把节点之间的归属关系归结为一种亲属关系，如父亲、孩 子、祖先、后代、兄弟等等。在对元素进行匹配时，同样可以用到这些概念。例如：
(1) //E/parent::* 表示所有E节点的父节点元素，结果为id值为a1的A元素和id值为c1的C元素
(2) //F/ancestor::* 表示所有F元素的祖先节点元素，结果为id值为a1的A元素和id值为c2的C元素
(3) /A/child::* 表示A的子元素，结果为id值为b1、b2的B元素，id值为c2的C元素，以及没有任何属性的E元素
(4) /A/descendant::* 表示A的所有后代元素，结果为除A元素以外的所有其它元素
(5) //F/self::* 表示所有F的自身元素，结果为F元素本身
(6) //F/ancestor-or-self::* 表示所有F元素及它的祖先节点元素，结果为F元素、F元素的父节点C元素和A元素
(7) /A/C/descendant-or-self::* 表示所有A元素→C元素及它们的后代元素，结果为id值为c2的C元素、该元素的子元素B、D、F元素
(8) /A/C/following-sibling::* 表示A元素→C元素的紧邻的后序所有兄弟节点元素，结果为没有任何属性的E元素
(9) /A/C/preceding-sibling::* 表示A元素→C元素的紧邻的前面所有兄弟节点元素，结果为id值为b1和b2的两个B元素
(10) /A/B/C/following::* 表示A元素→B元素→C元素的后序的所有元素，结果为id 为b2的B元素、无属性的C元素、无属性的B元素、id为d2的D元素、无属性的F元素、/无属性的E元素。
(11) /A/C/preceding::* 表示A元素→C元素的前面的所有元素，结果为id为b2的B元素、id为e2的E元素、id为e1的E元素、id为d1的D元素、name为 b的B元素、id为c1的C元素、id为b1的B元素
*** [条件匹配]***
条件匹配就是利用一些函数的运算结果的布尔值来匹配符合条件的节 点。常用于条件匹配的函数有四大类：节点函数、字符串函数、数值函 数、布尔函数。例如last()、position()等等，这里我们就不再赘述。
以上这些匹配方法中，用得最多的还要数路径匹配。在上一章样式表的 例子中，无论是在语句<xsl:template match="学生花名册">中，还是在语句 <xsl:value-of select="名字"/>中，都是依靠给出相对于当前路径的子路径来定位节点的。
========上面只是利用开源项目XPath定位xml树形文件的位置==== 同理，我们在定位其他一些方面的树形结构时，可以像XPath一样，通过制定自己的一套规则来定位我们的节点。
email: w.yu@neusoft.com
