maksipes
@maksipes

Как получить ветвь дерева?

например есть такое дерево: (только idишники)
31940649
  31951793
  31951796 
    31951905 
    31951908
    31951911
    31951914
    31951917
  31951799
    31951920
    31951923
    31951926
    31951929
    31951932


и мне надо ветку для id 31951932 (последний), и тогда я должен получить такое:
31940649
  31951799
    31951932

не соображу как это сделать.

п.с. логики в idишниках нет, парсить их бесполезно.
  • Вопрос задан
  • 62 просмотра
Пригласить эксперта
Ответы на вопрос 2
xmoonlight
@xmoonlight
https://sitecoder.blogspot.com
1. Ищем родителя и unshift.
2. Повторять, пока есть родитель.
Ответ написан
wataru
@wataru Куратор тега Алгоритмы
Разработчик на С++, гуглер, экс-олимпиадник.
Если, как у вас в примере, вам дан текст с отступами, то можно делать так:

Читайте построчно и разбивайте строку на число и сколько пробелов перед ним стоит.
Заведите массив, в котором будете хранить "активных" предков для всех уровней.
Перезаписывайте значение по индексу "сколько пробелов в начале строки".
При нахождении вашего искомого индекса выводите этот массив (до текущего числа)
Фактически, этот массив - это стек в котором вы храните текущую ветвь.

Вот пример:
1
 2
 3
  4


Допустим, вам нужны предки для id=4.
Прочли "1". Массив {1,0,0...}. Прочли " 2". Массив {1, 2, 0...}. Прочли " 3". Массив {1, 3, 0...}. Прочли " 4". Массив стал {1, 3, 4}. 4 - искомый элемент выводим ветку 1-3-4.

Если у вас отступы длины 2, то делите количество пробелов на 2 для получения индекса. Или у вас там могут быть символы табуляции - считайте их. Решение не работает, если формат не постоянен и разные уровни могут иметь разные отступы. Но тут можно считать текущую глубину. Надо так же в массиве хранить сколько пробелов в начале каждого уровня. Если новая строка имеет больше отступов, чем строка на текущем уровне, то увеличиваем глубину и кладем строку в массив. Если имеет меньше, то уменьшаем глубину, пока отступы не станут такими же, как и у строки на этом уровне.

Если надо делать эту операцию быстро и много раз, то лучше один раз переведите эту строковую запись в настоящее дерево, со ссылками на родителя для каждого id: каждый раз при записи id в массив делайте ссылку на предыдущий id в массиве, как родителя.
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы
Artezio Нижний Новгород
от 130 000 до 180 000 ₽
Яндекс Москва
от 100 000 до 300 000 ₽
Artezio Москва
от 160 000 до 220 000 ₽
30 нояб. 2020, в 09:52
1 руб./за проект
30 нояб. 2020, в 09:42
111 руб./за проект
30 нояб. 2020, в 09:28
3000 руб./за проект