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>