将多个路径字符串转换成XML文档树

假设有下面的字符串：

给定一个根节点名字root和叶子节点名字leaf，如何将它们转换成一颗像下面这样的XML文档树呢？

对于这个问题，一个解决的思路是：先创建一颗以root作为根标签的XML文档树，再循环迭代每个字符串，将其按照'/'切开（Split），然后依次对每个文件夹名字创建一个XML节点（Node），并搜索整棵树，如果该节点存在，则直接pass掉，否则将节该点追加到某个父节点下。但是此种方法太麻烦，因为每次增加一个节点，你就需要去遍历一次。有很多情况下，前几层节点是存在的，这样判断就不那么高效了。举个例子，现在有一条深度为10的文件夹路径（比如/a/b/c/d/e/f/g/h/i/j/**.sh），为了插入这条路径，首先需要判断/a是否存在，存在就pass掉，不存在就创建/a；之后判断/a/b是否存在；之后是/a/b/c是否存在。。。

很显然，这样做，越到后面效率越低。而且，直接操作Xml文档会占用很多资源。

那么，有没有一种简单又高效的方式呢？答案是肯定的，这就是写这篇博客的原因了。这只是一种方案，也许还有更好的，有兴趣的同学可以自行研究，哈哈……

首先，我们可以将这些文件夹路径进行预处理────转换成中间格式进行存储。这里，我们可以先定义一个Map结构，Key用于保存当前节点名字和节点的XPath，中间可用特殊字符隔开；Value用于保存当前节点的父节点的名字和父节点的XPath（根节点root的父亲为null），中间也用相同的特殊字符隔开，像下面这样：

第一行表示：当前的home节点XPath为/root，其父节点root的xPath为null，同理，第二行表示：当前节点user的XPath为/root/home，而其父节点home的XPath为/root。把Key设计成这样有一个好处是，当一条路径中的多层里有相同名字的文件夹时，也可以轻易分辨。比如有一条路径为：/home/home/home，那么在创建节点时，会创建以下几个键值对：

就是说，在同一个XPath（例如/root/home）下，只会存在一个名为home的文件夹。如果以后的文件夹路径中还包含/home/home/home这样的地址，那么这些文件夹的子文件夹将会被放在已经存在的/root/home/home/home路径下。再通俗一点：每个Key-Value都是唯一的，它唯一表示了一条路径的存在。

有人可能会问：为什么Value也要设计成一样的结构呢？

答案很简单，便于在以后的处理中直接使用这个值，后面会提到。

通过这样的转换，我们可以看出，第二行的value实际上就是第一行的key，这样我们就可以表示一条一条的子孙——祖宗链，都是由子节点指向父节点。

转换之后的Map像下面这样：

细心的同学可能已经看见了，第5行以后，处理第二个URL时，home和user两个文件夹已经存在，则直接pass掉，接着处理desktop文件夹了。还有desktop文件夹对应的value是user#/root/home，这和第3行的value相同，因此文件夹desktop和abc属于同一级，都在/root/home/user下。

转换后，我们可以做以下几件事：

1. 直接遍历这个Map，先找出根目录（即value为root#null的）root下的所有节点（这里是home, etc, tmp, usr，当然也可能直接就是一个文件了）。判定的标准为：所有的value都为root#null的。

2. 循环遍历root的子节点集合，判定每个子节点是否为叶子节点（即文件），若是，则加上<leaf>节点名字<leaf>，可以考虑使用StringBuilder.append();，若不是，则对每个子节点做以下几件事：

   1. 加上节点开始标记<节点名字>

   2. 做第1步，只是当前目录不是根目录而已（递归了）

   3. 加上节点结束标志<节点名字>

      
      

这样递归下去，就会形成多颗以文件夹路径开始的文件夹作为根目录的XML树，最后将所有得到的小树都添加到新创建的<root></root>根标签中，到此，文档生成完成。

代码就不写了，思路已经相当清晰了，哈哈

使用这种方式，虽然迭代次数可能比较多，但是使用Map来保存树的结构以及使用字符串来生成XML的资源消耗都不大，而且效率都相当高。至于有多高，我用以上数据做了个测试，执行时间在1~3ms，感兴趣的亲们可以试试。

后记

    开始的一个版本是：将Map中的Key和Value都表示为当前【节点名字#深度】，但是当我按照这种思路写完后，立刻发现生成的XML不是我想要的，因为我的测试数据中存在多个【节点名字】和【深度】都相同的节点，但是其根节点不同。。。。究其原因，是因为我们设计时可能存在同样的Key，于是后面的同深度且同名的文件夹名字则被pass掉了，导致该深度下所有同名的文件夹都被添加到了第一颗根节点下。

    后来想了半天，才把这个【节点名字#深度】替换为【节点名字#XPath】，这个必须是唯一的了。