С Новым годом! Форум программистов, компьютерный форум, киберфорум
Наши страницы

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
maks_b
4 / 4 / 0
Регистрация: 11.10.2011
Сообщений: 16
#1

Бинарные деревья - C++

26.02.2013, 18:57. Просмотров 690. Ответов 1
Метки нет (Все метки)

Здравствуйте! Подскажите, правильно ли написано правое удаление вершины дерева?
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
if(tree1->Right){
        if(tree1->Right->Left==NULL){
            tree1->key=tree1->Right->key;
            tree1->Right=tree1->Right->Right;
        }else{
            tree1->key=findRightMini(tree1->Right);
        }
    }
    else if(tree1->Right==NULL){
        tree1->key=tree1->Left->key;
        tree1->Right=tree1->Left->Right;
        tree1->Left=tree1->Left->Left;
    }
Добавлено через 1 минуту
findRightMini- это функция поиска минимального элемента
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
26.02.2013, 18:57
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Бинарные деревья (C++):

Бинарные деревья - C++
Доброго времени суток, нужна помощь, дали задание...Вершина бинарного дерева содержит ключ, строку и два указателя на потомков.Составить...

Бинарные деревья - C++
Подсчитать количество элементов на n-уровне бинарного дерева. Подскажите как можно решить используя любой обход в глубину но без...

Бинарные деревья - C++
Компилятор выдаёт ошибки в 9, 10 и 12, 13 строках: invalid conversion from 'int' to 'sNode*' Подскажите пожалуйста, что не так. ...

Бинарные деревья - C++
Возникла проблема с бинарными деревьями . Нужно определить K - количество узлов, ключ которых больше заданного числа N. Я дошёл только до...

Бинарные деревья - C++
Очень нужна помощь, вообще деревья не понимаю!!!:( Вершина дерева содержит указатель на строку и N указателей на потомков. Функция...

бинарные деревья - C++
Вершина двоичного дерева содержит указатель на строку и указатели на правое и левое поддеревья. Строки в дереве упорядочены по возрастанию....

1
anmartex
...
1708 / 1201 / 496
Регистрация: 12.02.2013
Сообщений: 1,978
26.02.2013, 20:22 #2
Я конечно давно деревьев не касался, но... Это же дерево, зачем вы копируете сами значения? Вы должны оперировать только указателями и не более того.

Рассмотри первую часть кода "если правый есть". При наличие правого поддерева, мы должны взять его крайнюю левую вершину.
Название: tree_right.png
Просмотров: 118

Размер: 3.4 Кб

Теперь на счёт кода "если правого нет". То мы просто напросто берём левое поддерево. Если даже его нет, то указатель Left будет равен NULL и всё.
Название: tree_right_null.PNG
Просмотров: 119

Размер: 1.6 Кб

Теперь как это примерно должно выглядеть:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
   // Запоминаем, чтобы удалить в дальнейшем
   auto node = tree1;
 
   if (tree1->Right)
   {
      // Курсор, который будет искать крайнуюю левую вершину
      auto cursor = tree->Right;
      // Хвостовой спутник курсора.
      // Сохраняет его предыдущую позицию.
      auto tail = tree->Right;
      
      // Ищем самый левый элемент
      while (cursor->Left)
      {
         tail = cursor;
         cursor = cursor->Left;
      }
      
      // Если хоть одна левая вершина была, то
      if (tail != cursor)
      {
         // Т.к. левую вершину ликведируем, то правую необходимо
         // передать выше. И она уже станет не правой, а левой
         // для вышерасположенной вершины
         tail->Left = cursor->Right;
         // А крайней левой вершине (правому его поддереву)
         // присваиваем всю правую ветку.
         cursor->Right= tree1->Right;
      }
      
      // Теперь в любом случае, или правому поддереву, или найденному
      // крайнему левому, присваиваем всю левую ветку основного дерева
      cursor->Left = tree1->Left;
      
      // Теперь указатель перемещаем уже на найденный нами элемент
      tree1 = cursor;
   }
   else if (tree1->Right == nullptr)
   {
      tree1 = tree1->Left;
   }
 
   // Удоляем узел
   delete node;

Что же касается вашего кода, в большей части он написан верно но:
  1. Как я уже отписался выше, вы оперируете значениями узлов, а не указателями. А куда хвосты у вас деваются после таких манипуляций?
  2. Вы так смело разадресовываете указатели на 11 и 12 строчках. А кто сказал, что tree1->Left не NULL? Или вы проверку уже выше сделали?
  3. Ну и строчка 6 вообще не верна по определению, ибо самый сложный случай вообще не реализован. Хотя, может есть какие-то тонкости в функции findRightMini и она выполняет ещё что-то кроме поиска?
1
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
26.02.2013, 20:22
Привет! Вот еще темы с ответами:

Бинарные деревья - C++
Вот задачка: Для заданного бинарного дерева поиска проверить условие: • для каждой вершины высота левого поддерева отличается от...

Бинарные деревья - C++
1)Написать программу подсчета числа вершин в бинарном дереве 2)Написать программу копирования одного бинарного дерева в другое ...

Бинарные деревья С++ - C++
Добрый день! Дали такое задание на лабораторную работу. кое-что получилось, а в остальном прошу Вас помочь... Из входной...

Бинарные деревья - C++
Здравствуйте господа. Очень нуждаюсь в вашей помощи по бинарным деревьям. Собственно, имеется задание: Создать бинарное дерево которое...


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

Или воспользуйтесь поиском по форуму:
2
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.