Форум программистов, компьютерный форум CyberForum.ru

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

Восстановить пароль Регистрация
 
maks_b
4 / 4 / 0
Регистрация: 11.10.2011
Сообщений: 15
26.02.2013, 18:57     Бинарные деревья #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- это функция поиска минимального элемента
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
26.02.2013, 18:57     Бинарные деревья
Посмотрите здесь:

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

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
anmartex
...
 Аватар для anmartex
1700 / 1193 / 494
Регистрация: 12.02.2013
Сообщений: 1,978
26.02.2013, 20:22     Бинарные деревья #2
Я конечно давно деревьев не касался, но... Это же дерево, зачем вы копируете сами значения? Вы должны оперировать только указателями и не более того.

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

Размер: 3.4 Кб

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

Размер: 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 и она выполняет ещё что-то кроме поиска?
Yandex
Объявления
26.02.2013, 20:22     Бинарные деревья
Ответ Создать тему
Опции темы

Текущее время: 01:39. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru