Python3 解析XML 层序遍历二叉树

Python3 解析XML 层序遍历二叉树

keyword : python3, xml, xml.dom.minidom, 层序遍历, 层次遍历, 二叉树

part1 问题描述

面对如下 XML 文件，写程序按层序遍历二叉树，要求打印 text 节点中的 text 属性，并按文法的形式展示。

1.1 二叉树举例如下图

1.2 对应的文法规则如下所示

Root ->Dir +AbMissHigh
Dir ->截至
AbMissHigh ->AbMissHigh +PartOf
AbMissHigh ->Num +Tut
PartOf ->Dt +Tut
Num ->21
Tut ->日
Dt ->上
Tut ->午

part 2 程序代码

import xml.dom.minidom

def getText(node):
    return node.firstChild.getAttribute('text')

def getChilds(node):
    nodes = list()
    for child in node.childNodes:
       if (child.nodeName == "syntacticstructure"):
           nodes.append(child)
    return nodes

if __name__ == "__main__":
    DOMTree = xml.dom.minidom.parse("kim.xml")
    sentence = DOMTree.documentElement
    syntacticstructure = sentence.firstChild
    q = list()
    q.append(syntacticstructure)
    while(len(q)):
        node = q.pop(0)
        for child in getChilds(node):
            q.append(child)
        if len(getChilds(node)):
            print(getText(node) + "->", end="")
            for i,child in enumerate(getChilds(node)):
                if i == len(getChilds(node)) - 1:
                    print(getText(child))
                else:
                    print(getText(child) + "+", end="")

附录

xml文件。文件名 kim.xml：

<sentence defaultfontsize="10" file="E:\Corpus\新建文件夹\3.9.xml" lefttranslate="20" linelength="10" mintextwidth="30" name="3.9.xml" toptranslate="20" type="TreeForm">
<syntacticstructure lineblue="0" linegreen="0" linered="0" string="664305241" syntacticlevel="HEAD">
<text text="Root ">
<N0 backgroundblue="255" backgroundgreen="255" backgroundred="255" font="Dialog" foregroundblue="0" foregroundgreen="0" foregroundred="0" size="10" strikethrough="false" style="0" subscript="normal" underline="false"/>
<N1 backgroundblue="255" backgroundgreen="255" backgroundred="255" font="Dialog" foregroundblue="0" foregroundgreen="0" foregroundred="0" size="10" strikethrough="false" style="0" subscript="normal" underline="false"/>
<N2 backgroundblue="255" backgroundgreen="255" backgroundred="255" font="Dialog" foregroundblue="0" foregroundgreen="0" foregroundred="0" size="10" strikethrough="false" style="0" subscript="normal" underline="false"/>
<N3 backgroundblue="255" backgroundgreen="255" backgroundred="255" font="Dialog" foregroundblue="0" foregroundgreen="0" foregroundred="0" size="10" strikethrough="false" style="0" subscript="normal" underline="false"/>
<N4 font="Dialog" size="10" style="0" subscript="normal"/>
</text>
<syntacticfeaturesets/>
<syntacticassociations/>
<starttraces/>
<endtraces/>
<syntacticstructure lineblue="0" linegreen="0" linered="0" string="1493421489" syntacticlevel="HEAD">
<text text="Dir ">
<N0 backgroundblue="255" backgroundgreen="255" backgroundred="255" font="Dialog" foregroundblue="0" foregroundgreen="0" foregroundred="0" size="10" strikethrough="false" style="0" subscript="normal" underline="false"/>
<N1 backgroundblue="255" backgroundgreen="255" backgroundred="255" font="Dialog" foregroundblue="0" foregroundgreen="0" foregroundred="0" size="10" strikethrough="false" style="0" subscript="normal" underline="false"/>
<N2 backgroundblue="255" backgroundgreen="255" backgroundred="255" font="Dialog" foregroundblue="0" foregroundgreen="0" foregroundred="0" size="10" strikethrough="false" style="0" subscript="normal" underline="false"/>
<N3 font="Dialog" size="10" style="0" subscript="normal"/>
</text>
<syntacticfeaturesets/>
<syntacticassociations/>
<starttraces/>
<endtraces/>
<syntacticstructure lineblue="0" linegreen="0" linered="0" string="1023074303" syntacticlevel="MORPH">
<text text="截至 ">
<N0 backgroundblue="255" backgroundgreen="255" backgroundred="255" font="Dialog" foregroundblue="0" foregroundgreen="0" foregroundred="0" size="10" strikethrough="false" style="0" subscript="normal" underline="false"/>
<N1 backgroundblue="255" backgroundgreen="255" backgroundred="255" font="Dialog" foregroundblue="0" foregroundgreen="0" foregroundred="0" size="10" strikethrough="false" style="0" subscript="normal" underline="false"/>
<N2 font="Dialog" size="10" style="0" subscript="normal"/>
</text>
<syntacticfeaturesets/>
<syntacticassociations/>
<starttraces/>
<endtraces/>
</syntacticstructure>
</syntacticstructure>
<syntacticstructure lineblue="0" linegreen="0" linered="0" string="896569587" syntacticlevel="HEAD">
<text text="AbMissHigh ">
<N0 backgroundblue="255" backgroundgreen="255" backgroundred="255" font="Dialog" foregroundblue="0" foregroundgreen="0" foregroundred="0" size="10" strikethrough="false" style="0" subscript="normal" underline="false"/>
<N1 backgroundblue="255" backgroundgreen="255" backgroundred="255" font="Dialog" foregroundblue="0" foregroundgreen="0" foregroundred="0" size="10" strikethrough="false" style="0" subscript="normal" underline="false"/>
<N2 backgroundblue="255" backgroundgreen="255" backgroundred="255" font="Dialog" foregroundblue="0" foregroundgreen="0" foregroundred="0" size="10" strikethrough="false" style="0" subscript="normal" underline="false"/>
<N3 backgroundblue="255" backgroundgreen="255" backgroundred="255" font="Dialog" foregroundblue="0" foregroundgreen="0" foregroundred="0" size="10" strikethrough="false" style="0" subscript="normal" underline="false"/>
<N4 backgroundblue="255" backgroundgreen="255" backgroundred="255" font="Dialog" foregroundblue="0" foregroundgreen="0" foregroundred="0" size="10" strikethrough="false" style="0" subscript="normal" underline="false"/>
<N5 backgroundblue="255" backgroundgreen="255" backgroundred="255" font="Dialog" foregroundblue="0" foregroundgreen="0" foregroundred="0" size="10" strikethrough="false" style="0" subscript="normal" underline="false"/>
<N6 backgroundblue="255" backgroundgreen="255" backgroundred="255" font="Dialog" foregroundblue="0" foregroundgreen="0" foregroundred="0" size="10" strikethrough="false" style="0" subscript="normal" underline="false"/>
<N7 backgroundblue="255" backgroundgreen="255" backgroundred="255" font="Dialog" foregroundblue="0" foregroundgreen="0" foregroundred="0" size="10" strikethrough="false" style="0" subscript="normal" underline="false"/>
<N8 backgroundblue="255" backgroundgreen="255" backgroundred="255" font="Dialog" foregroundblue="0" foregroundgreen="0" foregroundred="0" size="10" strikethrough="false" style="0" subscript="normal" underline="false"/>
<N9 backgroundblue="255" backgroundgreen="255" backgroundred="255" font="Dialog" foregroundblue="0" foregroundgreen="0" foregroundred="0" size="10" strikethrough="false" style="0" subscript="normal" underline="false"/>
<N10 font="Dialog" size="10" style="0" subscript="normal"/>
</text>
<syntacticfeaturesets/>
<syntacticassociations/>
<starttraces/>
<endtraces/>
<syntacticstructure lineblue="0" linegreen="0" linered="0" string="310221747" syntacticlevel="HEAD">
<text text="AbMissHigh ">
<N0 backgroundblue="255" backgroundgreen="255" backgroundred="255" font="Dialog" foregroundblue="0" foregroundgreen="0" foregroundred="0" size="10" strikethrough="false" style="0" subscript="normal" underline="false"/>
<N1 backgroundblue="255" backgroundgreen="255" backgroundred="255" font="Dialog" foregroundblue="0" foregroundgreen="0" foregroundred="0" size="10" strikethrough="false" style="0" subscript="normal" underline="false"/>
<N2 backgroundblue="255" backgroundgreen="255" backgroundred="255" font="Dialog" foregroundblue="0" foregroundgreen="0" foregroundred="0" size="10" strikethrough="false" style="0" subscript="normal" underline="false"/>
<N3 backgroundblue="255" backgroundgreen="255" backgroundred="255" font="Dialog" foregroundblue="0" foregroundgreen="0" foregroundred="0" size="10" strikethrough="false" style="0" subscript="normal" underline="false"/>
<N4 backgroundblue="255" backgroundgreen="255" backgroundred="255" font="Dialog" foregroundblue="0" foregroundgreen="0" foregroundred="0" size="10" strikethrough="false" style="0" subscript="normal" underline="false"/>
<N5 backgroundblue="255" backgroundgreen="255" backgroundred="255" font="Dialog" foregroundblue="0" foregroundgreen="0" foregroundred="0" size="10" strikethrough="false" style="0" subscript="normal" underline="false"/>
<N6 backgroundblue="255" backgroundgreen="255" backgroundred="255" font="Dialog" foregroundblue="0" foregroundgreen="0" foregroundred="0" size="10" strikethrough="false" style="0" subscript="normal" underline="false"/>
<N7 backgroundblue="255" backgroundgreen="255" backgroundred="255" font="Dialog" foregroundblue="0" foregroundgreen="0" foregroundred="0" size="10" strikethrough="false" style="0" subscript="normal" underline="false"/>
<N8 backgroundblue="255" backgroundgreen="255" backgroundred="255" font="Dialog" foregroundblue="0" foregroundgreen="0" foregroundred="0" size="10" strikethrough="false" style="0" subscript="normal" underline="false"/>
<N9 backgroundblue="255" backgroundgreen="255" backgroundred="255" font="Dialog" foregroundblue="0" foregroundgreen="0" foregroundred="0" size="10" strikethrough="false" style="0" subscript="normal" underline="false"/>
<N10 font="Dialog" size="10" style="0" subscript="normal"/>
</text>
<syntacticfeaturesets/>
<syntacticassociations/>
<starttraces/>
<endtraces/>
<syntacticstructure lineblue="0" linegreen="0" linered="0" string="1733952868" syntacticlevel="HEAD">
<text text="Num ">
<N0 backgroundblue="255" backgroundgreen="255" backgroundred="255" font="Dialog" foregroundblue="0" foregroundgreen="0" foregroundred="0" size="10" strikethrough="false" style="0" subscript="normal" underline="false"/>
<N1 backgroundblue="255" backgroundgreen="255" backgroundred="255" font="Dialog" foregroundblue="0" foregroundgreen="0" foregroundred="0" size="10" strikethrough="false" style="0" subscript="normal" underline="false"/>
<N2 backgroundblue="255" backgroundgreen="255" backgroundred="255" font="Dialog" foregroundblue="0" foregroundgreen="0" foregroundred="0" size="10" strikethrough="false" style="0" subscript="normal" underline="false"/>
<N3 font="Dialog" size="10" style="0" subscript="normal"/>
</text>
<syntacticfeaturesets/>
<syntacticassociations/>
<starttraces/>
<endtraces/>
<syntacticstructure lineblue="0" linegreen="0" linered="0" string="202389819" syntacticlevel="MORPH">
<text text="21 ">
<N0 backgroundblue="255" backgroundgreen="255" backgroundred="255" font="Dialog" foregroundblue="0" foregroundgreen="0" foregroundred="0" size="10" strikethrough="false" style="0" subscript="normal" underline="false"/>
<N1 backgroundblue="255" backgroundgreen="255" backgroundred="255" font="Dialog" foregroundblue="0" foregroundgreen="0" foregroundred="0" size="10" strikethrough="false" style="0" subscript="normal" underline="false"/>
<N2 font="Dialog" size="10" style="0" subscript="normal"/>
</text>
<syntacticfeaturesets/>
<syntacticassociations/>
<starttraces/>
<endtraces/>
</syntacticstructure>
</syntacticstructure>
<syntacticstructure lineblue="0" linegreen="0" linered="0" string="893470908" syntacticlevel="HEAD">
<text text="Tut ">
<N0 backgroundblue="255" backgroundgreen="255" backgroundred="255" font="Dialog" foregroundblue="0" foregroundgreen="0" foregroundred="0" size="10" strikethrough="false" style="0" subscript="normal" underline="false"/>
<N1 backgroundblue="255" backgroundgreen="255" backgroundred="255" font="Dialog" foregroundblue="0" foregroundgreen="0" foregroundred="0" size="10" strikethrough="false" style="0" subscript="normal" underline="false"/>
<N2 backgroundblue="255" backgroundgreen="255" backgroundred="255" font="Dialog" foregroundblue="0" foregroundgreen="0" foregroundred="0" size="10" strikethrough="false" style="0" subscript="normal" underline="false"/>
<N3 font="Dialog" size="10" style="0" subscript="normal"/>
</text>
<syntacticfeaturesets/>
<syntacticassociations/>
<starttraces/>
<endtraces/>
<syntacticstructure lineblue="0" linegreen="0" linered="0" string="515093806" syntacticlevel="MORPH">
<text text="日 ">
<N0 backgroundblue="255" backgroundgreen="255" backgroundred="255" font="Dialog" foregroundblue="0" foregroundgreen="0" foregroundred="0" size="10" strikethrough="false" style="0" subscript="normal" underline="false"/>
<N1 font="Dialog" size="10" style="0" subscript="normal"/>
</text>
<syntacticfeaturesets/>
<syntacticassociations/>
<starttraces/>
<endtraces/>
</syntacticstructure>
</syntacticstructure>
</syntacticstructure>
<syntacticstructure lineblue="0" linegreen="0" linered="0" string="1588368286" syntacticlevel="HEAD">
<text text="PartOf ">
<N0 backgroundblue="255" backgroundgreen="255" backgroundred="255" font="Dialog" foregroundblue="0" foregroundgreen="0" foregroundred="0" size="10" strikethrough="false" style="0" subscript="normal" underline="false"/>
<N1 backgroundblue="255" backgroundgreen="255" backgroundred="255" font="Dialog" foregroundblue="0" foregroundgreen="0" foregroundred="0" size="10" strikethrough="false" style="0" subscript="normal" underline="false"/>
<N2 backgroundblue="255" backgroundgreen="255" backgroundred="255" font="Dialog" foregroundblue="0" foregroundgreen="0" foregroundred="0" size="10" strikethrough="false" style="0" subscript="normal" underline="false"/>
<N3 backgroundblue="255" backgroundgreen="255" backgroundred="255" font="Dialog" foregroundblue="0" foregroundgreen="0" foregroundred="0" size="10" strikethrough="false" style="0" subscript="normal" underline="false"/>
<N4 backgroundblue="255" backgroundgreen="255" backgroundred="255" font="Dialog" foregroundblue="0" foregroundgreen="0" foregroundred="0" size="10" strikethrough="false" style="0" subscript="normal" underline="false"/>
<N5 backgroundblue="255" backgroundgreen="255" backgroundred="255" font="Dialog" foregroundblue="0" foregroundgreen="0" foregroundred="0" size="10" strikethrough="false" style="0" subscript="normal" underline="false"/>
<N6 font="Dialog" size="10" style="0" subscript="normal"/>
</text>
<syntacticfeaturesets/>
<syntacticassociations/>
<starttraces/>
<endtraces/>
<syntacticstructure lineblue="0" linegreen="0" linered="0" string="670131188" syntacticlevel="HEAD">
<text text="Dt ">
<N0 backgroundblue="255" backgroundgreen="255" backgroundred="255" font="Dialog" foregroundblue="0" foregroundgreen="0" foregroundred="0" size="10" strikethrough="false" style="0" subscript="normal" underline="false"/>
<N1 backgroundblue="255" backgroundgreen="255" backgroundred="255" font="Dialog" foregroundblue="0" foregroundgreen="0" foregroundred="0" size="10" strikethrough="false" style="0" subscript="normal" underline="false"/>
<N2 font="Dialog" size="10" style="0" subscript="normal"/>
</text>
<syntacticfeaturesets/>
<syntacticassociations/>
<starttraces/>
<endtraces/>
<syntacticstructure lineblue="0" linegreen="0" linered="0" string="1617277174" syntacticlevel="MORPH">
<text text="上 ">
<N0 backgroundblue="255" backgroundgreen="255" backgroundred="255" font="Dialog" foregroundblue="0" foregroundgreen="0" foregroundred="0" size="10" strikethrough="false" style="0" subscript="normal" underline="false"/>
<N1 font="Dialog" size="10" style="0" subscript="normal"/>
</text>
<syntacticfeaturesets/>
<syntacticassociations/>
<starttraces/>
<endtraces/>
</syntacticstructure>
</syntacticstructure>
<syntacticstructure lineblue="0" linegreen="0" linered="0" string="141113787" syntacticlevel="HEAD">
<text text="Tut ">
<N0 backgroundblue="255" backgroundgreen="255" backgroundred="255" font="Dialog" foregroundblue="0" foregroundgreen="0" foregroundred="0" size="10" strikethrough="false" style="0" subscript="normal" underline="false"/>
<N1 backgroundblue="255" backgroundgreen="255" backgroundred="255" font="Dialog" foregroundblue="0" foregroundgreen="0" foregroundred="0" size="10" strikethrough="false" style="0" subscript="normal" underline="false"/>
<N2 backgroundblue="255" backgroundgreen="255" backgroundred="255" font="Dialog" foregroundblue="0" foregroundgreen="0" foregroundred="0" size="10" strikethrough="false" style="0" subscript="normal" underline="false"/>
<N3 font="Dialog" size="10" style="0" subscript="normal"/>
</text>
<syntacticfeaturesets/>
<syntacticassociations/>
<starttraces/>
<endtraces/>
<syntacticstructure lineblue="0" linegreen="0" linered="0" string="420497037" syntacticlevel="MORPH">
<text text="午 ">
<N0 backgroundblue="255" backgroundgreen="255" backgroundred="255" font="Dialog" foregroundblue="0" foregroundgreen="0" foregroundred="0" size="10" strikethrough="false" style="0" subscript="normal" underline="false"/>
<N1 font="Dialog" size="10" style="0" subscript="normal"/>
</text>
<syntacticfeaturesets/>
<syntacticassociations/>
<starttraces/>
<endtraces/>
</syntacticstructure>
</syntacticstructure>
</syntacticstructure>
</syntacticstructure>
</syntacticstructure>
</sentence>