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

Исправить код бинарного дерева - C++

Восстановить пароль Регистрация
 
Artishok
ЧакЭ одобряЭ
 Аватар для Artishok
277 / 276 / 32
Регистрация: 27.12.2009
Сообщений: 1,767
25.11.2010, 00:32     Исправить код бинарного дерева #1
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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
#include <stdlib.h>
#include <iostream>
 
 
 
struct uzel
{
   int key;//хранится в вершине ключ-значение
   struct uzel *left, *right;//указатели на правое и левое поддерево
};
 
uzel* not(int val)
{
  uzel *nod=new uzel;
  nod->key=val;
  nod->left=0;
  nod->right=0;
  return nod;
}
 
void add_tree(uzel *root, int val)//добавление элемента
{
  if (root==0) root = not(val);//если 0 создаем новую голову
  if (val < root->key)//если меньше значения то влево
  {
   if (root->left==0)//если 0 то просто запишем в левый узел элемент
     root->left = not(val);
   else
     add_tree(root->left, val);//иначе надо добавть влево влево
  }
  if (val > root->key)//если больше то вправо
  {
   if (root->right==0)
     root->right = not(val);//достаточно записать туда элемент
   else
     add_tree(root->right, val);//в правое правое поддерево
  }
     
 // return;
}
 
uzel* find_tree(uzel *root, int val)//поиск элемента
{
  if (root==0)//если нет ни одного элемента то вернуть 0
    return 0;
  if (val == root->key)//нашли - вот и славно
    return root;
  if (val < root->key)//если меньше то искать в левом поддереве
    return find_tree(root->left, val);
  if (val > root->key)//иначе вправом
    return find_tree(root->right, val);
}
 
int rightmost(uzel *root)//самый правый
{
  while (root->right != NULL)//пока не дойдет до правого с ссылкой 0
    root = root->right;//по правым подузлам шагать
  return root->key;//верняем то что туда затесалось
}
 
uzel* del_tree(uzel *root, int val)//удаление
{
  if (root==0) return 0;//если 0 так 0
  if (root->key == val) //если нашли то
  {
        //это элемент-лист
     if (root->left==0 && root->right==0) 
     {
      delete root;//достаточно просто удалить
      return 0;
     }
     if (root->right==0 && root->left != 0)//если есть один потомок левый 
     {
      uzel *temp = root->left;//то переменной типа "узел" запишем значение узла-потомка слева
      delete root;
      return temp;
     }
     if (root->left==0 && root->right != 0) //то же для правого
     {
      uzel *temp = root->right;
      delete root;
      return temp;
     }
     root->key = rightmost(root->left);//теперь в удаляемой позиции будет стоять элемент самый правый левого поддерева
     root->left = del_tree(root->left, root->key);//левым потомком удаляемого будет элемент левый левого поддерева с этим ключом
     return root;
  }
  if (val < root->key)//если значение меньше того что в корне то выполнить все необходимые операция для левого поддерева 
  {
   root->left = del_tree(root->left, val);
   return root;
  }
  if (val > root->key)//то же для правого 
  { 
   root->right = del_tree(root->right, val);
   return root;
  }
 return root;
}
 
void print_tree(uzel *root)//вывести дерево
{
 if (root != 0) 
 {
   print_tree(root->left);
   cout<<root->key<<" ";
   print_tree(root->right);
 }
}
 
int main()
{
    uzel *trie=0;
    int elem;
    cout<<"Insert elem"<<endl;
    cin>>elem;
    add_tree(trie,elem);
    print_tree(trie);
    return 0;
}
прога либо не выводит элемент либо не добавляет т.к. в результате не выводит ничего.
в чем проблема?
Лучшие ответы (1)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
25.11.2010, 00:32     Исправить код бинарного дерева
Посмотрите здесь:

Прошивка бинарного дерева на С++ C++
Копирование бинарного дерева C++
C++ Обход бинарного дерева
C++ Код Хаффмана реализованный через построение бинарного дерева
C++ Высота бинарного дерева
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
ForEveR
Модератор
Эксперт C++
 Аватар для ForEveR
7927 / 4709 / 318
Регистрация: 24.06.2010
Сообщений: 10,524
Завершенные тесты: 3
25.11.2010, 00:40     Исправить код бинарного дерева #2
Я конечно могу быть не прав... Но ведь тут бесконечная рекурсия. И ничего не печатается, т.к. после входа в функцию, если корень существует, то идет рекурсивный вызов print_tree(root->left) и дальше функция просто не идет. Все начинается по новой.
C++
1
2
3
4
5
6
7
8
9
void print_tree(uzel *root)//вывести дерево
{
 if (root != 0) 
 {
   print_tree(root->left);
   cout<<root->key<<" ";
   print_tree(root->right);
 }
}
Artishok
ЧакЭ одобряЭ
 Аватар для Artishok
277 / 276 / 32
Регистрация: 27.12.2009
Сообщений: 1,767
25.11.2010, 00:44  [ТС]     Исправить код бинарного дерева #3
ну теоретически должно дойти до 0 узла т.е. пройдя все узлы перемещаясь по ссылкам(как в списке while(cur!=0) cur=cur->next)
ForEveR
Модератор
Эксперт C++
 Аватар для ForEveR
7927 / 4709 / 318
Регистрация: 24.06.2010
Сообщений: 10,524
Завершенные тесты: 3
25.11.2010, 00:47     Исправить код бинарного дерева #4
Artishok, Это замечательно. Но вывода все равно не будет. Дойдя до нуля - выйдет из функции.
Artishok
ЧакЭ одобряЭ
 Аватар для Artishok
277 / 276 / 32
Регистрация: 27.12.2009
Сообщений: 1,767
25.11.2010, 00:51  [ТС]     Исправить код бинарного дерева #5
Цитата Сообщение от ForEveR Посмотреть сообщение
Но вывода все равно не будет. Дойдя до нуля - выйдет из функции.
но почему?(То есть то что выйдет из функции понятно а почему не выведет?)

ага...если будет нулевой потомк выйдет и ничего не выведет.

на паскале нечто аналогичное работает
Pascal
1
2
3
4
5
6
7
8
procedure lkr(t: trie);//левый корень правый
begin
  if t = nil then
    exit;
  lkr(t^.left);
  write(t^.val, ' ');
  lkr(t^.right);
end;
C++
1
2
3
4
5
6
7
8
void print_tree(uzel *root)//âûâåñòè äåðåâî
{
 if (root == 0) 
    return;
   print_tree(root->left);
   cout<<root->key<<" ";
   print_tree(root->right);
}
эффект один
ForEveR
Модератор
Эксперт C++
 Аватар для ForEveR
7927 / 4709 / 318
Регистрация: 24.06.2010
Сообщений: 10,524
Завершенные тесты: 3
25.11.2010, 00:59     Исправить код бинарного дерева #6
Сообщение было отмечено автором темы, экспертом или модератором как ответ
Artishok, Нашел вашу главную ошибку.

Функция insert не меняла значение. Лучше будет полагаю так.

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void add_tree(uzel **root, int val)//добавление элемента
{
  if (*root==0) *root = not(val);//если 0 создаем новую голову
  if (val < (*root)->key)//если меньше значения то влево
  {
   if ((*root)->left==0)//если 0 то просто запишем в левый узел элемент
     (*root)->left = not(val);
   else
     add_tree(&(*root)->left, val);//иначе надо добавть влево влево
  }
  if (val > (*root)->key)//если больше то вправо
  {
   if ((*root)->right==0)
     (*root)->right = not(val);//достаточно записать туда элемент
   else
     add_tree(&(*root)->right, val);//в правое правое поддерево
  }
     
 // return;
}
В функцию посылать из main соответственно адрес элемента. Можно сделать и через ссылку на указатель.

Добавлено через 4 минуты
Вот. Можете сами убедиться, что работает ввод и вывод. С деревьями дел никогда не имел посему остальное переделаете сами, если понадобится.

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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
#include <stdlib.h>
#include <iostream>
 
using namespace std;
 
struct uzel
{
   int key;//хранится в вершине ключ-значение
   struct uzel *left, *right;//указатели на правое и левое поддерево
};
 
uzel* not(int val)
{
  uzel *nod=new uzel;
  nod->key=val;
  nod->left=0;
  nod->right=0;
  return nod;
}
 
void add_tree(uzel **root, int val)//добавление элемента
{
  if (*root==0) *root = not(val);//если 0 создаем новую голову
  if (val < (*root)->key)//если меньше значения то влево
  {
   if ((*root)->left==0)//если 0 то просто запишем в левый узел элемент
     (*root)->left = not(val);
   else
     add_tree(&(*root)->left, val);//иначе надо добавть влево влево
  }
  if (val > (*root)->key)//если больше то вправо
  {
   if ((*root)->right==0)
     (*root)->right = not(val);//достаточно записать туда элемент
   else
     add_tree(&(*root)->right, val);//в правое правое поддерево
  }
     
 // return;
}
 
uzel* find_tree(uzel *root, int val)//поиск элемента
{
  if (root==0)//если нет ни одного элемента то вернуть 0
    return 0;
  if (val == root->key)//нашли - вот и славно
    return root;
  if (val < root->key)//если меньше то искать в левом поддереве
    return find_tree(root->left, val);
  if (val > root->key)//иначе вправом
    return find_tree(root->right, val);
}
 
int rightmost(uzel *root)//самый правый
{
  while (root->right != NULL)//пока не дойдет до правого с ссылкой 0
    root = root->right;//по правым подузлам шагать
  return root->key;//верняем то что туда затесалось
}
 
uzel* del_tree(uzel *root, int val)//удаление
{
  if (root==0) return 0;//если 0 так 0
  if (root->key == val) //если нашли то
  {
                //это элемент-лист
     if (root->left==0 && root->right==0) 
         {
      delete root;//достаточно просто удалить
      return 0;
     }
     if (root->right==0 && root->left != 0)//если есть один потомок левый 
         {
      uzel *temp = root->left;//то переменной типа "узел" запишем значение узла-потомка слева
      delete root;
      return temp;
     }
     if (root->left==0 && root->right != 0) //то же для правого
     {
      uzel *temp = root->right;
      delete root;
      return temp;
     }
     root->key = rightmost(root->left);//теперь в удаляемой позиции будет стоять элемент самый правый левого поддерева
     root->left = del_tree(root->left, root->key);//левым потомком удаляемого будет элемент левый левого поддерева с этим ключом
     return root;
  }
  if (val < root->key)//если значение меньше того что в корне то выполнить все необходимые операция для левого поддерева 
  {
   root->left = del_tree(root->left, val);
   return root;
  }
  if (val > root->key)//то же для правого 
  {     
   root->right = del_tree(root->right, val);
   return root;
  }
 return root;
}
 
void print_tree(uzel *root)//вывести дерево
{
 if (root != 0) 
 {
   cout<<root->key<<" ";
   print_tree(root->left);
   print_tree(root->right);
 }
}
 
int main()
{
        uzel *trie=0;
        int elem;
        cout<<"Insert elem"<<endl;
        cin>>elem;
        add_tree(&trie,elem);
        add_tree(&trie, 10);
        add_tree(&trie, 0);
        add_tree(&trie, 15);
        add_tree(&trie, 8);
        print_tree(trie);
        return 0;
}
Artishok
ЧакЭ одобряЭ
 Аватар для Artishok
277 / 276 / 32
Регистрация: 27.12.2009
Сообщений: 1,767
25.11.2010, 01:02  [ТС]     Исправить код бинарного дерева #7
ну функцию ввода я изменил так что весь код вставлять не было необходимости.
а почему надо передавать двойной указатель?
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
25.11.2010, 01:04     Исправить код бинарного дерева
Еще ссылки по теме:

C++ Запись бинарного дерева
Удаление из бинарного дерева C++
C++ Обход Бинарного дерева

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

Или воспользуйтесь поиском по форуму:
ForEveR
Модератор
Эксперт C++
 Аватар для ForEveR
7927 / 4709 / 318
Регистрация: 24.06.2010
Сообщений: 10,524
Завершенные тесты: 3
25.11.2010, 01:04     Исправить код бинарного дерева #8
Artishok, Чтобы изменялось значение в main. Поэтому дерево создается нормально. Собственно, можно еще раз говорю передавать ссылку на указатель или указатель на ссылку, не помню как правильно сказать.
Yandex
Объявления
25.11.2010, 01:04     Исправить код бинарного дерева
Ответ Создать тему
Опции темы

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