рекурсия — Построение дерева из XML-файла с использованием RapidXML и переполнения стека

Question

рекурсия — Построение дерева из 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());
}
}

}

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

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

1

binary-tree c++rapidxml recursion xml-parsing

Решение

Другие решения

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

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

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

0

Источник

Accepted Answer

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

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

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

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

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

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

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

3