DFS遍历多叉树实现XML转JSON
本文最后更新于 481 天前,其中的信息可能已经有所发展或是发生改变。

最近做的一个项目用到了标题中所说的东西,我想:

微信公众平台的数据格式真的是坑爹啊啊啊!
这个大家应该诗有所了解的。

一会儿json,一会儿XML,给我们的开发造成了很大的困扰。

于是涉及到了XML转JSON的一部分内容,我想要做的是:实现任意深度的多叉树深度优先遍历搜索,并获取搜索结果,存入字典结果集(Python中的字典很方便的可以转换成JSON格式,这个轮子我们已经有了)

我的思路如下:

  1. 对于任意深度的一棵树,我们可以获取其根节点,存为ROOT,令当前结点为ROOT
  2. 进入循环,获取当前节点的子节点,存入列表ChildList
  3. 遍历列表中的每一个子节点,检查子节点是否有子节点,如果被遍历节点无子节点,说明其已经是顶叶子节点了,将其从ChildList中删除。
  4. 检查修改过的ChildList是否为空,如果不为空,从列表中pop出一个节点作为当前节点,并将ChildList备份为父节点列表ParentList,继续循环(continue)。
  5. 如果当前ChildList为空,那么说明当前节点的所有子节点都已经是叶子节点了,所以我们根据自己的需要,将叶子节点的信息读取,如果要转Json,可以以当前结点的名称作为字典键,然后我们合并信息,将当前节点和所有子节点删除。并从父节点列表中pop出一个节点作为当前节点
  6. 在进行完以上两步之后,检查当前节点是否为根节点Root,如果是那么说明遍历已经退回树的根部,结束循环(break)并返回已经合并的字典

我自己写的一部分代码,最关键的循环体部分:

def Go(self):
    while bool(self.Root.getchildren()):
        self.CNodeChild = self.CurrentNode.getchildren()
        self.CNodeChild = [N for N in self.CNodeChild if bool(N.getchildren())]
        if len(self.CNodeChild) == 0:
            self.MergeNode()
            self.CurrentNode = self.PreviousNode.pop()
            continue
        else:
            self.PreviousNode.append(self.CurrentNode)
            self.CurrentNode = self.CNodeChild.pop()
            continue
    return {self.RootTag : self.ReturnDict}

其中,CNodeChild相当于当前节点子节点列表;getchildren方法为获取当前节点子节点列表;PreviousNode相当于父节点列表;RootTag相当于根节点名称;ReturnDict相当于返回字典;MergeNode为自己需要对获取到的子节点进行的合并操作。

源代码是在类中写的,不很好看,就不给大家献丑了。

给大家看一下结果,还是挺好的,就是字典有些复杂,不过转Json之后格式化就很好看了。

这个算法的时间复杂度并不好,O(N^2),希望有大神能够优化一下它。

暂无评论

发送评论 编辑评论


|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇