Построение дерева из XML-файла с использованием RapidXML и c++

Для проекта для моего класса С++ я должен проанализировать и XML-файл и построить из него двоичное дерево. Файл гораздо более плотный, чем этот, но макет выглядит следующим образом:

<?xml version="1.0" encoding="utf-8"?>
<MyJournal>
    <species>
        <name>Sea Creature</name>
        <species>
            <name>Fish</name>
            <species>
                <name>swordfish</name>
            </species>
            <species>
                <name>grouper</name>
            </species>
        </species>
        <species>
            <name>Mammal</name>
            <species>
                <name>dolphin</name>
            </species>
            <species>
                <name>whale</name>
            </species>
        </species>
    </species>
    <species>
        <name>Land animal</name>
        <species>
            <name>Mammal</name>
            <species>
                <name>dog</name>
            </species>
            <species>
                <name>cat</name>
            </species>
        </species>
        <species>
            <name>Bird</name>
            <species>
                <name>blue jay</name>
            </species>
            <species>
                <name>robin</name>
            </species>
        </species>
    </species>
</MyJournal>

Мне трудно понять, как анализировать эти данные, чтобы я мог построить дерево. Я думал, что могу использовать рекурсию для каждой ветки, но я могу заставить ее получить только одного ребенка. Кто-то намекнул на использование очереди для помещения данных в древовидную структуру, но я не совсем уверен, как я мог пройти все уровни дерева, используя очередь. Я чувствую, что рекурсия - это самый простой способ проанализировать данные для каждой ветки, но я просто не могу понять, как правильно реализовать рекурсивный метод. Вот метод, который я пытался использовать. Сначала я прошел в корневом узле:

void loop(xml_node<> *species)
{
    Node t1 = *new Node();
    xml_node<> * name_node = species->first_node("name");
    if(name_node != 0)
    {
        t1.setName(name_node->value());
        cout << name_node->value() << endl;
    }


    xml_node<> * child = species->first_node("species");
    if(child != 0)
    {
        cout << child->first_node("name")->value() << endl;
        if(child->first_node()->next_sibling() != 0)
        {
            loop(child->first_node()->next_sibling());
            xml_node<> * child2 = child->next_sibling();
            cout << child2->first_node()->value() << endl;
            loop(child2->first_node()->next_sibling());
        }
    }

}

Он проходит только через первого потомка каждого узла, возвращая Морское существо Рыба-меч-рыба Наземное животное Млекопитающее Собака

Я был бы очень признателен за любые указатели в правильном направлении. Спасибо!


c++ recursion xml-parsing binary-tree rapidxml
person Community    schedule 07.03.2013    source источник
comment
Наземное животное не является видом. Используйте таксономические ранги :)   -  person David    schedule 07.03.2013
comment
Да, я на самом деле делаю этот проект для огромного филогенетического дерева, и я просто упростил его до небольшого базового дерева, чтобы получить представление о синтаксическом анализе :)   -  person    schedule 08.03.2013

Ответы (2)


arrow_upward
2
arrow_downward

Чтобы охватить все узлы в этом файле, вам нужно просмотреть дочерние узлы каждого узла и его родственных элементов. Кажется, ты это понимаешь.

Ваш рекурсивный подход - рабочий выбор для доступа к детям. Кажется, это работает. Каждый рекурсивный вызов loop идет на один уровень глубже в дочерние элементы. (Кто бы ни сказал вам использовать «очередь», возможно, имел в виду «стек»… и рекурсия неявно использует стек. Стек вызовов.)

Братьев и сестер не хватает. И поскольку рекурсия используется для более глубокого проникновения в XML-дерево, эту проблему, вероятно, не решить с помощью большей рекурсии.

Посмотрите на эту часть кода вашего кода:

xml_node<> * child = species->first_node("species");
if(child != 0)
{
    cout << child->first_node("name")->value() << endl;

Здесь вы найдете первого родственного брата, например "swordfish".

Попробуйте превратить этот оператор if в цикл, чтобы содержащаяся в нем логика выполнялась для всех братьев и сестер, а не только для первого.

person Drew Dormann    schedule 07.03.2013
comment
Спасибо за помощь. Я изменил оператор if на этот for(xml_node<> * child = species->first_node("species"); child != 0; child = child->next_sibling()) и получил вывод Sea Creature Fish swordfish grouper Land animal Mammal dog cat Land animal Mammal dog cat. Цикл теперь дважды проходит через дочерние узлы рыб и через узлы млекопитающих. Есть идеи, как мне это исправить? - person ; 08.03.2013

arrow_upward
0
arrow_downward

Я знаю, что на этот вопрос уже был дан ответ, но я просто хочу дать полезную подсказку.

Вместо использования рекурсии вы можете использовать стеки/очереди для разбора этого XML-файла, чтобы построить свою "древовидную" структуру.

Если вы хотите придерживаться рекурсии, убедитесь, что все дочерние элементы указывают на одного и того же родителя, иначе древовидная структура будет неправильной.

person user2137877    schedule 13.03.2013