Как отсортировать двоичное дерево (которое в boost называется ptree)?

Модератор: Модераторы разделов

Аватара пользователя
жучара
Сообщения: 1024
ОС: астралинукс

Как отсортировать двоичное дерево (которое в boost называется ptree)?

Сообщение жучара »

Друзья! Вот так я создаю двоичное дерево tree и перегоняю его в файл dst.xml (ниже файл foo.cpp)

Код: Выделить всё

#include <boost/property_tree/ptree.hpp>
#include <boost/property_tree/xml_parser.hpp>
using namespace std;

int main ()
{
    boost::property_tree::ptree tree;
    
    tree.put("x", "");
    tree.put("x.r", "");
    tree.put("x.r.k", "");

    tree.put("x.y", "");
    tree.put("x.y.d", "");

    tree.put("x.e.z.k.n.p", "");
    tree.put("x.e.z.k.n.b", "");
    tree.put("x.e.z.a.b", "");

    tree.put("x.a.q.w.t", "");
    tree.sort();
	
    boost::property_tree::write_xml ("dst.xml", tree);

    return 0;
}
Выполняю:

Shell

$ g++ foo.cpp
$ ./a.out
$
Файл dst.xml смотрю так:

Shell

$ echo du | xmllint -oldxml10 --shell dst.xml | head -n -1 | tail -n +2
x
r
k
y
d
e
z
k
n
p
b
a
b
a
q
w
t
$
Вот мне хотелось бы, чтобы в дереве всё было отсортировано рекурсивно. Например, узлы, которые лежат непосредственно в головном узле x должны располагаться в таком порядке: (вывожу только первые буквы):
a
e
r
y
Весь вывод соответственно должен выглядеть так:

Shell

x
a
q
w
t
e
z
a
b
k
n
b
p
y
d
r
k
Не уверен, что это в принципе возможно, но зачем-то у boost::property_tree::ptree присутствует функция sort, кстати, применённая мной и описанная здесь. (а пунктом выше там описана ещё одна функция sort) Для чего она нужна- непонятно. Спасибо, кто откликнется. Debian 11.
Я просто читаю маны.
Спасибо сказали:
Аватара пользователя
Bizdelnick
Модератор
Сообщения: 20977
Статус: nulla salus bello
ОС: Debian GNU/Linux

Re: Как отсортировать двоичное дерево (которое в boost называется ptree)?

Сообщение Bizdelnick »

Так Вы сортируете корневой узел, в котором ничего, кроме x, нет.
Пишите правильно:
в консоли
вку́пе (с чем-либо)
в общем
вообще
в течение (часа)
новичок
нюанс
по умолчанию
приемлемо
проблема
пробовать
трафик
Спасибо сказали:
Аватара пользователя
жучара
Сообщения: 1024
ОС: астралинукс

Re: Как отсортировать двоичное дерево (которое в boost называется ptree)?

Сообщение жучара »

Bizdelnick писал:
31.12.2022 00:45
Так Вы сортируете корневой узел, в котором ничего, кроме x, нет.
пусть так. Надеюсь, мой вопрос понятен.
Я просто читаю маны.
Спасибо сказали:
Аватара пользователя
Bizdelnick
Модератор
Сообщения: 20977
Статус: nulla salus bello
ОС: Debian GNU/Linux

Re: Как отсортировать двоичное дерево (которое в boost называется ptree)?

Сообщение Bizdelnick »

Чтобы отсортировать рекурсивно, надо обойти дерево рекурсивно и сделать sort() для всех непустых узлов.
Пишите правильно:
в консоли
вку́пе (с чем-либо)
в общем
вообще
в течение (часа)
новичок
нюанс
по умолчанию
приемлемо
проблема
пробовать
трафик
Спасибо сказали:
Аватара пользователя
жучара
Сообщения: 1024
ОС: астралинукс

Re: Как отсортировать двоичное дерево (которое в boost называется ptree)?

Сообщение жучара »

Bizdelnick писал:
31.12.2022 01:03
Чтобы отсортировать рекурсивно, надо обойти дерево рекурсивно и сделать sort() для всех непустых узлов.
как же мне отсортировать указанные мной 4 ветки, если они даже не лежат в одном узле (x)?
Я просто читаю маны.
Спасибо сказали:
Аватара пользователя
Bizdelnick
Модератор
Сообщения: 20977
Статус: nulla salus bello
ОС: Debian GNU/Linux

Re: Как отсортировать двоичное дерево (которое в boost называется ptree)?

Сообщение Bizdelnick »

Bizdelnick писал:
31.12.2022 01:03
обойти дерево рекурсивно
Добавлено (14:55):
Примерно так:

Код: Выделить всё

template<class K, class D, class C>
void sort_ptree_reсursive(& boost::property_tree::basic_ptree<K, D, C> pt)
{
  pt.sort();
  for (auto it = pt.begin(); it < pt.end(); it++) {
    sort_ptree_recursive(*it);
  }
}
Не проверял, наверняка накосячил где-то. Но идея, надеюсь, понятна.
Пишите правильно:
в консоли
вку́пе (с чем-либо)
в общем
вообще
в течение (часа)
новичок
нюанс
по умолчанию
приемлемо
проблема
пробовать
трафик
Спасибо сказали: