Дерево поиска. Восстановить указатели на родителя

18.12.2014, 23:50. Показов 897. Ответов 0

Author24 — интернет-сервис помощи студентам

Здравствуйте! Задача состоит в следующем: в двоичном дереве поиска необходимо у каждого узла восстановить указатель на родителя. Например, есть вот такое дерево:

C++
1
2
3
4
5
           10
          /   \
       8      12
      /  \    /  \
     2   9   11  15

Надо сделать, чтобы 8.parent == 10, 11.parent == 12 и т.д.

Структура узла может выглядеть так:

C++
1
2
3
4
5
6
struct node{
  int key;
  node *right;
  node *left;
  node *parent;
}

Возможно ли как-нибудь рекурсивно пройти по дереву и восстановить указатель parent? Я плохо понимаю рекурсии, и еще хуже их пишу.
Единственные мысли, это запоминать на каждом шаге рекурсии текущий корневой элемент, а на следующем шаге указать parent на этот элемент.

Заказать работу у эксперта

cpp_developer

Эксперт

20123 / 5690 / 1417

Регистрация: 09.04.2010

Сообщений: 22,546

Блог

18.12.2014, 23:50

Ответы с готовыми решениями:

Вывод поста, который содержит id категории, её родителя, родителя родителя
Есть 2 таблицы, первая - категории ( category_id, parent_id и т.д), вторая - посты (post_id, category_id) В общем, в...

Дерево закрывается до родителя при нажатии на дочерние элементы Angular 6
В общем вывожу дерево, которое можно раскрывать и скрывать. Возникает 2 проблемs, подскажите как решить. Приложен скрин вывода для...

Исходное бинарное дерево превратить в бинарное дерево поиска, при этом сохранив его структуру
Помогите, не могу понять!( Нужно исходное бинарное дерево превратить в бинарное дерево поиска, при этом сохранив его структуру. вот...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.

raxper

Эксперт

30234 / 6612 / 1498

Регистрация: 28.12.2010

Сообщений: 21,154

Блог

18.12.2014, 23:50

Помогаю со студенческими работами здесь

указатели. двоичное дерево
Всем добрый день. Объясните мне, пожалуйста, несколько вещей. 1.Вот, например. root->left что делает он: -> Я вроде читал,...

Что значит восстановить бинарное дерево?
Восстановить бинарное дерево по прямому и обратному порядку. Нужно его построить или вывести на экран? Что это за слово - восстановить?)) В...

Бинарное дерево подклассов основного класса-узла. Доступ к подклассам по указателю - объекту класса-родителя
Короче, необходимо сделать бинарное дерево, решающее арифметическое выражение, предварительно туда записанное. Есть основной класс...

Преобразовать идеальное бинарное дерево в бинарное дерево поиска
Всем привет, я создал идельное бинарное дерево и написал к нему функции. Как мне теперь можно преобразовать его в бинарное дерево поиска?...

Дерево поиска
Помогите сделать задание. Нужно проверить есть ли в дереве элемент r:real НЕ РЕКУРСИВНО И РЕКУРСИВНО Tree = ^ Node; Node = record ...

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:

Опции темы

Новые блоги и статьи Все статьи Все блоги /
Stack, Queue и Hashtable в C# UnmanagedCoder 14.05.2025 Каждый опытный разработчик наверняка сталкивался с ситуацией, когда невинный на первый взгляд List<T> превращался в узкое горлышко всего приложения. Причина проста: универсальность – это прекрасно,. . .	Как использовать OAuth2 со Spring Security в Java Javaican 14.05.2025 Протокол OAuth2 часто путают с механизмами аутентификации, хотя по сути это протокол авторизации. Представьте, что вместо передачи ключей от всего дома вашему другу, который пришёл полить цветы, вы. . .	Анализ текста на Python с NLTK и Spacy AI_Generated 14.05.2025 NLTK, старожил в мире обработки естественного языка на Python, содержит богатейшую коллекцию алгоритмов и готовых моделей. Эта библиотека отлично подходит для образовательных целей и. . .	Реализация DI в PHP Jason-Webb 13.05.2025 Когда я начинал писать свой первый крупный PHP-проект, моя архитектура напоминала запутаный клубок спагетти. Классы создавали другие классы внутри себя, зависимости жостко прописывались в коде, а о. . .	Обработка изображений в реальном времени на C# с OpenCV stackOverflow 13.05.2025 Объединение библиотеки компьютерного зрения OpenCV с современным языком программирования C# создаёт симбиоз, который открывает доступ к впечатляющему набору возможностей. Ключевое преимущество этого. . .
POCO, ACE, Loki и другие продвинутые C++ библиотеки NullReferenced 13.05.2025 В C++ разработки существует такое обилие библиотек, что порой кажется, будто ты заблудился в дремучем лесу. И среди этого многообразия POCO (Portable Components) – как маяк для тех, кто ищет. . .	Паттерны проектирования GoF на C# UnmanagedCoder 13.05.2025 Вы наверняка сталкивались с ситуациями, когда код разрастается до неприличных размеров, а его поддержка становится настоящим испытанием. Именно в такие моменты на помощь приходят паттерны Gang of. . .	Создаем CLI приложение на Python с Prompt Toolkit py-thonny 13.05.2025 Современные командные интерфейсы давно перестали быть черно-белыми текстовыми программами, которые многие помнят по старым операционным системам. CLI сегодня – это мощные, интуитивные и даже. . .	Конвейеры ETL с Apache Airflow и Python AI_Generated 13.05.2025 ETL-конвейеры – это набор процессов, отвечающих за извлечение данных из различных источников (Extract), их преобразование в нужный формат (Transform) и загрузку в целевое хранилище (Load). . . .	Выполнение асинхронных задач в Python с asyncio py-thonny 12.05.2025 Современный мир программирования похож на оживлённый мегаполис – тысячи процессов одновременно требуют внимания, ресурсов и времени. В этих джунглях операций возникают ситуации, когда программа. . .

Наверх