Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 5.00/6: Рейтинг темы: голосов - 6, средняя оценка - 5.00
0 / 0 / 0
Регистрация: 25.04.2019
Сообщений: 4
1

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

25.04.2019, 09:51. Показов 1184. Ответов 2

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

DEV++

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
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
#include<Windows.h>
#include<stdio.h>
#include<stdlib.h>
#include<conio.h>
#include<malloc.h>
#include<time.h>
typedef int T; // òèï ýëåìåíòà
#define compLT(a,b) (a < b) 
#define compEQ(a,b) (a == b) 
typedef struct Node_  
{
    T data;  // значение узла  
    Node_ *left;// евый потомок    
    Node_ *right;// правый потомок    
    Node_ *parent;// родитель  
    } Node;
    Node *root = NULL; //корень бинарного дерева поиска
    Node* insertNode(T data); 
    void deleteNode(Node *z); 
    Node* findNode(T data); 
    void printTree(Node *node, int l = 0);
    int main()
    { 
    SetConsoleCP(1251);   
    SetConsoleOutputCP(1251);
    int i, *a, *b, j, maxnum2, maxnum;  
    printf("Введите количество элементов maxnum : ");   
    scanf("%d",&maxnum);   
    printf("\n");
     a = (int*) malloc(sizeof(int)*maxnum);     
     srand(time(NULL)); 
     // ãåíåðàöèÿ ìàññèâà
     for (i = 0; i < maxnum; i++)     
     a[i] = rand() % 100;     
     printf("Вывод сгенерированной последовательности\n");
     for (i = 0; i < maxnum; i++)     
     printf("%d \n\n",a[i]); 
     
    printf("Введите количество элементов maxnum2 : ");   
    scanf("%d",&maxnum2);   
    printf("\n");
     b = (int*) malloc(sizeof(int)*maxnum2);     
     srand(time(NULL)); 
     // ãåíåðàöèÿ ìàññèâà
     for (j = 0; j < maxnum2; j++)     
     b[j] = rand() % 100;     
     printf("Вывод сгенерированной последовательности\n");
     for (j = 0; j < maxnum2; j++)     
     printf("%d \n\n",b[j]);
     // добавление элементов в бинарное дерево поиска
     for (i = 0; i < maxnum; i++)      
     insertNode(a[i]);
     printf("Âûâîä áèíàðíîãî äåðåâà ïîèñêà\n");   
     printTree(root);   
     printf("\n"); 
     
     //поиск всех элементов по бинарному дереву поиска
        for (i = maxnum-1; i >= 0; i--)
        findNode(a[i]);
     
     
     
     //удаление бинарного дерева поиска из памяти
     for (i = 0; i < maxnum; i++)      
     deleteNode(findNode(a[i]));   
     getch(); 
     return 0;
     }
     //функция выделения памяти для нового узла и вставка в дерево* 
     Node* insertNode(T data)
     { 
     Node *x, *current, *parent;   
     current = root;   
     parent = 0; 
     while (current) {
        if ( data == current->data ) return (current);       
         parent = current;       
         current = data < current->data ?        
         current->left : current->right;
          }
     x = (Node*) malloc(sizeof(Node));   
     x->data = data;   
     x->parent = parent;  
     x->left = NULL;   
     x->right = NULL;
     if(parent) 
     if( x->data < parent->data )       
       parent->left = x;
       else    
       parent->right = x;
     else    
     root = x; 
     return(x);
     }
     //функция удаления узла из дерева
     void deleteNode(Node *z) {
        Node *x, *y; 
         if (!z || z == NULL) return; 
         if (z->left == NULL || z->right == NULL)     
         y = z;
         else {     
         y = z->right; 
         while (y->left != NULL) y = y->left;
         } if (y->left != NULL)     
            x = y->left;
         else    
            x = y->right;
         if (x) x->parent = y->parent; 
         if (y->parent) 
         if (y == y->parent->left)       
            y->parent->left = x;
         else     
            y->parent->right = x;
            else    
            root = x; 
            if (y != z) {     
            y->left = z->left; 
            if (y->left) y->left->parent = y;       
            y->right = z->right; 
            if (y->right) y->right->parent = y;       
            y->parent = z->parent; 
            if (z->parent) 
            if (z == z->parent->left)         
            z->parent->left = y; 
            else        
            z->parent->right = y; 
            else      
            root = y;       
            free (z);
            }  
            else {
                free (y);   
                }
            } 
        //функция поиска узла, содержащего data
        Node* findNode(T data) {   
         Node *current = root; 
         while(current != NULL)
         if(compEQ(data, current->data)) 
         return (current);
         else      
           current = compLT(data, current->data) ?                  
           current->left : current->right; 
           return(0);
           }
        //функция вывода бинарного дерева поиска
        void printTree(Node *node, int l){
            int i; 
            if (node != NULL) {
                printTree(node->right, l+1); 
                for (i=0; i < l; i++)
                printf("    ");     
                printf ("%4ld", node->data);     
                printTree(node->left, l+1);
                } 
                else printf("\n"); 
    }
0

Помощь в написании контрольных, курсовых и дипломных работ здесь.

Лучшие ответы (1)
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
25.04.2019, 09:51
Ответы с готовыми решениями:

Для чего предназначено бинарное дерево, что оно делает?
народ подскажите пожалуйста для чего предназначено бинарное дерево? что оно делает? (надо делать...

Для каждого слова первого предложения определить, входит ли оно во второе предложение
Здравствуйте. Я нуб в программировании, только начинаю осваивать. Помогите пожалуйста составить...

Для каждого слова из первого предложения определить, входит ли оно во второе предложение
Даны два предложения. Для каждого слова первого предложения ( в том числе для повторяющихся в этом...

Для каждого слова первого предложения определить, входит ли оно во второе предложение
даны два предложения. Для каждого слова первого предложения (в том числе для повторяющихся в этом...

2
1480 / 944 / 811
Регистрация: 30.04.2016
Сообщений: 3,298
26.04.2019, 23:13 2
Лучший ответ Сообщение было отмечено Tolsty1221 как решение

Решение

Tolsty1221, здравствуйте! Вот решение:

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
/*
Даны две последовательности чисел. Построить бинарное дерево, содержащее числа первой последовательности. 
Для каждого числа второй последовательности узнать, входит ли оно в дерево.
*/
 
#include <iostream> 
 
    using namespace std;
    
struct BTree { 
    int data;
    BTree* left;
    BTree* right;
};
    
BTree* add(int data) {
  BTree* node = new BTree; 
  node->data = data;
  node->left = NULL; 
  node->right = NULL;
  return node;
}
 
BTree* insert(BTree* node, int key) { 
    if (node == NULL) 
        return add(key);
    if (key < node->data)
        node->left = insert(node->left, key);
    else if (key >= node->data)
        node->right = insert(node->right, key); 
    return node;
}
 
bool find_node(BTree* node, int key) { 
    if (node == NULL)
        return false;
    if (key < node->data) {
        return find_node(node->left, key);
    } else if (key > node->data) {
        return find_node(node->right, key);
    }
    return true; 
}
 
int main() {
    int n, m;
    BTree* root = NULL;
    cout << "Enter the 1-st sequence size:\n";
    cout << "n = ";
    cin >> n;
    cout << "Enter the 2-nd sequence size:\n";
    cout << "m = ";
    cin >> m;
    int* a = new int[n];
    int* b = new int[m];
    cout << "Enter the 1-st sequence of numbers:\n";
    for (int i = 0; i < n; i++) {
        cout << i + 1 << " => ";
        cin >> a[i];
        if (i == 0) {
            root = insert(root, a[i]);
        } else {
            insert(root, a[i]);
        }
    }
    cout << "Enter the 2-nd sequence of numbers:\n";
    for (int i = 0; i < m; i++) {
        cout << i + 1 << " => ";
        cin >> b[i];
    }
    cout << "Output of the program:\n";
    for (int i = 0; i < m; i++) {
        if (find_node(root, b[i])) {
            cout << b[i] << ": " << "Yes!\n";
        } else {
            cout << b[i] << ": " << "No!\n";
        }
    }
    delete [] a;
    delete [] b;
    system("pause");
    return 0;
}
2
0 / 0 / 0
Регистрация: 25.04.2019
Сообщений: 4
30.04.2019, 06:43  [ТС] 3
Огромное спасибо!! направил меня в правильное русло и дописал свой код и все получилось
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
30.04.2019, 06:43

Для каждого слова первого предложения определить, входит ли оно во второе предложение
Здравствуйте, помогите пожалуйста! Задача: Даны два предложения. Для каждого слова первого...

Строки. Для каждого слова первого предложения определить, входит ли оно во второе
даны 2 предложения.для каждого слова первого предложения(в том числе для повторяющихся...

Для каждого слова первого предложения определить, входит ли оно во второе предложение
Помогите решить!Даны два предложения. Для каждого слова первого предложения (в том чис-ле для...

Для каждого слова первого предложения определить, входит ли оно во второе предложение
Решить задачу в консольном режиме : Даны 2 предложения. Для каждого слова первого предложения...


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

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

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