В двоичном дереве удалить все узлы, значения которых является простым числом

@newyork7776 · Регистрация: 21.05.2013

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

Задание:в двоичном дереве удалить все узлы, значения которых является простым числом.
Пожалуста можна + комментарии.
Спасиба!!!

Кликните здесь для просмотра всего текста

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
#include <iostream>
#include <time.h>
using namespace std;
struct  node
{
  int key;
  node *left;
  node *right;
};
 
class TREE
{
  private:
    node *tree; //Указатель на корень дерева.
    
  public: 
    TREE() {tree=NULL;}
    node** GetTree () {return &tree;} //Получение вершины дерева.
    void buildTree (int,node **);
    void CleanTree (node **);
    void Vyvod (node**,int);
    void searchInTree(int ,node **,int);
};
int l(1),q(0); 
void main ()
{
  TREE A;
    int numb;
    cout << "Enter number = ";
    cin >> numb;
  srand(time(NULL));
    A.buildTree (numb,A.GetTree());
  cout<<"\nWrite tree:\n";
  A.Vyvod (A.GetTree(),0);
  
    char symbol;
  do{
    cout << "\n Write symbol, or write 0 for exit ";
    cin >> symbol;
    cout << "\n Number " << symbol << " in tree ";
    A.searchInTree(numb,A.GetTree(),(int)symbol);
    if(q == 0) cout << "NOTHING"; 
    l = 1;
    q = 0;
  }
  while(symbol != '0');
 
 A.CleanTree (A.GetTree());
    cout << endl; 
 system("pause");
}
  
void TREE::buildTree (int x,node **p)
{
    int leftNodes,rightNodes;
    leftNodes = x / 2;
    rightNodes = x - leftNodes - 1;
    
    
  if  (*p==NULL)
  {
 
      *p = new(node);
    (**p).key = rand()%21;   
    (**p).left = NULL; (**p).right = NULL; 
  }
  if(leftNodes > 0) buildTree(leftNodes,&((**p).left));
  if(rightNodes > 0)  buildTree(rightNodes,&((**p).right));
}
 
void TREE::CleanTree (node **w)
{
  if  (*w!=NULL)
  { CleanTree (&((**w).left));
    CleanTree (&((**w).right));
    delete *w; }
}
 
void TREE::Vyvod (node **w,int l)
{
  int i;
 
  if  (*w!=NULL)
  { Vyvod (&((**w).right),l+1);
    for  (i=1; i<=l; i++) cout<<"   ";
    cout<<(**w).key << endl;
 
    Vyvod (&((**w).left),l+1);
  }
}
 
void TREE::searchInTree (int x,node **p,int s)
{
    int leftNodes,rightNodes;
    leftNodes = x / 2;
    rightNodes = x - leftNodes - 1;
    if((**p).key == s) 
    {   
            cout << l << " ";
            ++q;
    }
    ++l;
  if(leftNodes > 0) searchInTree(leftNodes,&((**p).left),s);
  if(rightNodes > 0)  searchInTree(rightNodes,&((**p).right),s);
    
 
}

вот мой код нужно только удаление прилепить

@ninja2 · 19.06.2013, 13:29

newyork7776, Да это задание не такое простое, нужно обходить дерево, затем сверять значение в узле простое оно число или нет, (простое число это число которое делится только на сомо себя), потом нужно написать функцию удаления, головняк это, там смотреть нужно есть ли в узле потомки, сколько их один потомок два, какой правый левый.

Да это трудоемкая задача.

@newyork7776 · 19.06.2013, 13:35 **[ТС]**

а єсли удалить парние елементы?

Добавлено через 1 минуту
у меня проблема в том что когда я нахожу елемент который нужно удалить у меня удаляет не елемент,а ветку

Добавлено через 3 минуты

Сообщение от ninja2

простое число это число которое делится только на сомо себя

ещо на 1

@Thinker · 19.06.2013, 13:36

Сообщение от newyork7776

у меня проблема в том что когда я нахожу елемент который нужно удалить у меня удаляет не елемент,а ветку

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

@newyork7776 · 19.06.2013, 13:41 **[ТС]**

Thinker,можна пример,а то в голове пока не укладиваеться

@Thinker · 19.06.2013, 13:44

например, надо удалить 3 в дереве

находите лист из левого поддерева данной вершины 1. ставите 1 вместо 3 и удаляете 1. получаете

и т.д.

@ninja2 · 19.06.2013, 15:37

newyork7776, я тебе просто подскажу, от ты нашол элемент (узел) который нужно удалить допустим. у тебя этот узел может быть корнем, этот узел может иметь два потомка может иметь один левый потомок и может иметь один правый потомок.
От делай функцию del(принимает указатель на узел который нужно удалить) и в функции уже проверку:
if узел у тебя корень? //если корень
** if в узле один правый потомок.
** else if в узле один левый потомок.
** else if в узле ни одного потомка.
else //узел не корень
** if в узле один правый потомок.
** else if в узле один левый потомок.
** else if в узле ни одного потомка.

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

@newyork7776 · 19.06.2013, 16:37 **[ТС]**

Кликните здесь для просмотра всего текста

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
#include <iostream>
#include <time.h>
using namespace std;
struct  node
{
  int key;
  node *left;
  node *right;
}; 
class TREE
{
  private:
    node *tree; //Вказівник на корінь дерева.
    
  public: 
    TREE() {tree=NULL;}
    node** GetTree () {return &tree;} //отримані вершини дерева.
    void buildTree (int,node **); //будуємо дерево
    void CleanTree (node **);//очистка дерева
    void ObhodLeft (node **);//обхід дерева
    void Vyvod (node**,int);//виводимо наше дерево на екран
    void searchInTree(int ,node **,int);//пошук в дереві
};
int l(1),q(0); 
void main ()
{
    setlocale(LC_ALL, "Russian");
 
    cout << "Напиш1ть к1льк1сть цифр = ";
  TREE A;
    int numb;
    cin >> numb;
  srand(time(NULL));
    A.buildTree (numb,A.GetTree());
  cout<<"\nЦе наше дерево\n";
  A.Vyvod (A.GetTree(),0);
 
  cout<<"\nНизх1дний порядок проходження дерева: ";
  A.ObhodLeft (A.GetTree());
  
    char symbol;
  do{
    cout << "\n Напиш1ть 0,щоб вийти з програми ";
    cin >> symbol;
    cout << "\n Цифра " << symbol << " в дерев1 \n";
    A.searchInTree(numb,A.GetTree(),(int)symbol);
    if(q == 0) cout << "Дерево очищенно"; 
    l = 1;
    q = 0;
  }
  while(symbol != '0');
 
 A.CleanTree (A.GetTree());
    cout << endl; 
 system("pause");
}  
void TREE::buildTree (int x,node **p)
{
    int leftNodes,rightNodes;
    leftNodes = x / 2;
    rightNodes = x - leftNodes - 1;
    
    
  if  (*p==NULL)
  {
 
      *p = new(node);
    (**p).key = rand()%21;   
    (**p).left = NULL; 
    (**p).right = NULL; 
  }
  if(leftNodes > 0) buildTree(leftNodes,&((**p).left));
  if(rightNodes > 0)  buildTree(rightNodes,&((**p).right));
} 
void TREE::ObhodLeft (node **w)
{
  if  (*w!=NULL)
  {
    cout<<(**w).key<<" ";
    ObhodLeft (&((**w).left));
    ObhodLeft (&((**w).right));
  }
}
void TREE::CleanTree (node **w)
{
  if  (*w!=NULL)
  { CleanTree (&((**w).left));
    CleanTree (&((**w).right));
    delete *w; }
} 
void TREE::Vyvod (node **w,int l)
{
  int i;
  if  (*w!=NULL)
    { 
      Vyvod (&((**w).right),l+1);
            for  (i=1; i<=l; i++) 
                    cout<<"   ";
            if ((**w).key % 2 != 0) 
                    cout<<(**w).key << endl;
    Vyvod (&((**w).left),l+1);
    }
}
void TREE::searchInTree (int x,node **p,int s)
{
    int leftNodes,rightNodes;
    leftNodes = x / 2;
    rightNodes = x - leftNodes - 1;
    if((**p).key == s) 
    {   
            cout << l << " ";
            ++q;
    }
    ++l;
  if(leftNodes > 0) searchInTree(leftNodes,&((**p).left),s);
  if(rightNodes > 0)  searchInTree(rightNodes,&((**p).right),s);
    
 
}

а я вот так решил задачу,конешно направельно,но результат вроде правильный

Добавлено через 2 минуты
на базе мого варианта можна как-то создать новое дерево и запихать туде елементы которие выводяться на екран?

Добавлено через 2 минуты
мой вариант только с парним елементом

Новые блоги и статьи Все статьи Все блоги /
Модель ЗдрввоСохранения 7: больше работников, больше ресурсов. anaschu 08.04.2026 работников и заданий может быть сколько угодно, но настроено всё так, что используется пока что только 20% kYBz3eJf3jQ	Дальние перспективы сервера - слоя сети с космологическим дизайном интефейса карты и логики. Hrethgir 07.04.2026 Дальнейшее ближайшее планирование вывело к размышлениям над дальними перспективами. И вот тут может быть даже будут нужны оценки специалистов, так как в дальних перспективах всё может очень сильно. . .	Горе от ума kumehtar 07.04.2026 Эта мне ментальная установка, что вот прямо сейчас, мол, мне для полного счастья не хватает (нужное вписать), и когда я этого достигну - тогда и полный кайф. Одна из самых сильных ловушек на пути. . . .	Использование значений реквизитов справочника в документе, с определенными условиями и правами Maks 07.04.2026 1. Контроль срока действия договора Алгоритм из решения ниже реализован на примере нетипового документа "ЗаявкаНаРаботу", разработанного в конфигурации КА2. Задача: уведомлять пользователя, если. . .
Доступность команды формы по условию Maks 07.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "СписаниеМатериалов", разработанного в конфигурации КА2. Задача: сделать доступной кнопку (команда формы "ЗавершитьСписание") при. . .	Уведомление о неверно выбранном значении справочника Maks 06.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "НарядПутевка", разработанного в конфигурации КА2. Задача: уведомлять пользователя, если в документе выбран неверный склад. . .	Установка Qt Creator для C и C++: ставим среду, CMake и MinGW без фреймворка Qt 8Observer8 05.04.2026 Среду разработки Qt Creator можно установить без фреймворка Qt. Есть отдельный репозиторий для этой среды: https:/ / github. com/ qt-creator/ qt-creator, где можно скачать установщик, на вкладке Releases:. . .	AkelPad-скрипты, структуры, и немного лирики.. testuser2 05.04.2026 Такая программа, как AkelPad существует уже давно, и также давно существуют скрипты под нее. Тем не менее, прога живет, периодически что-то не спеша дополняется, улучшается. Что меня в первую очередь. . .

@ninja2 979 / 196 / 33 Регистрация: 26.09.2012 Сообщений: 2,041
	19.06.2013, 13:29
	newyork7776, Да это задание не такое простое, нужно обходить дерево, затем сверять значение в узле простое оно число или нет, (простое число это число которое делится только на сомо себя), потом нужно написать функцию удаления, головняк это, там смотреть нужно есть ли в узле потомки, сколько их один потомок два, какой правый левый. Да это трудоемкая задача. 0

@newyork7776 351 / 344 / 279 Регистрация: 21.05.2013 Сообщений: 1,312
	19.06.2013, 13:41 [ТС]
	Thinker,можна пример,а то в голове пока не укладиваеться 0

@ninja2 979 / 196 / 33 Регистрация: 26.09.2012 Сообщений: 2,041
	19.06.2013, 15:37
	newyork7776, я тебе просто подскажу, от ты нашол элемент (узел) который нужно удалить допустим. у тебя этот узел может быть корнем, этот узел может иметь два потомка может иметь один левый потомок и может иметь один правый потомок. От делай функцию del(принимает указатель на узел который нужно удалить) и в функции уже проверку: if узел у тебя корень? //если корень if в узле один правый потомок. else if в узле один левый потомок. else if в узле ни одного потомка. else //узел не корень if в узле один правый потомок. else if в узле один левый потомок. else if в узле ни одного потомка. Вроде примерно как то так и так удаляй как нужно там для каждого условия по своему нужно вроде как удалять. Да я с ней тоже промучился когда делал, код занимал половину кода дерева и головняк покак оттестишь, то оно не то что надо удалит, то ветку не прицепит, в общем морочно все это. 0