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

Функция удаления листа (или ветки) бинарного дерева - C++

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Редактирование записи и печать односвязного списка http://www.cyberforum.ru/cpp-beginners/thread1179801.html
Задание звучит так: Разработать приложение, работающее с односвязным списком, содержащим данные о питомцах зоопарка. Элементом списка является структура, содержащая не менее 4-ех элементов. Выполнить добавление, удаление, редактирование элемента списка, распечатку всего списка. Не могу понять как сделать редактирование записи в списке и еще печать. Буду очень благодарна за помощь. #include...
C++ Решение систем линейных уравнений различными методами #include "stdafx.h" #include "iostream" #include "cmath" using namespace std; void input(float**A,float*B,float**C,float**R,int m,int n); float determ(float**A,int n); void Kramer(float**A,float*B,float**C,float*d,int n); void Gauss(float**A,float*B,float**C,float*X,int n); void Matrica(float **A,float*B,float*M,int n); int l_min(int a, int b); http://www.cyberforum.ru/cpp-beginners/thread1179800.html
C++ программа для расчетов
я начал делать но не понял помогите #include<iostream> #include<Windows.h> #include<math.h> using namespace std; void main() { SetConsoleCP(1251); SetConsoleCP(1251);
C++ Ошибки "Unresolved external '__InitVCL' referenced" и "Unresolved external '__ExitVCL' referenced"
Здравствуйте. При компиляции возникают такие ошибки: Unresolved external '__InitVCL' referenced from C:\PROGRAM FILES (X86)\BORLAND\CBUILDER6\LIB\CP32MTI.LIB|crtlvcl Unresolved external '__ExitVCL' referenced from C:\PROGRAM FILES (X86)\BORLAND\CBUILDER6\LIB\CP32MTI.LIB|crtlvcl Сам код программы(класс для работы со временем): Заголовочный файл. // ctime.h #include <iostream.h>
C++ Считывание структуры из бинарного файла http://www.cyberforum.ru/cpp-beginners/thread1179781.html
Привет всем, при считывании структуры одной строкой кода и последующим выводом ее на экран выводятся непонятные символы. подскажите, что делать :( #include <iostream> #include <fstream> #include <string> #include <windows.h> #pragma warning (disable: 996) using namespace std; struct Info {
C++ Найти корень заданного уравнения методом простой итерации с заданной точностью Найти корень заданного уравнения методом простой итерации с заданной точностью. Напомним, что в этом методе нужно уравнение свести к виду x=f(x) и очередное уточнение корня проводится по формуле xn+1 = f(xn) до тех пор, пока |xn+1 – xn| > E, где Е – заданная точность. Рядом с уравнением в скобках указано начальное приближение корня 5х – 8 ln x = 8, (4,32) подробнее

Показать сообщение отдельно
RaiaNKnight
96 / 70 / 7
Регистрация: 29.06.2011
Сообщений: 465
Записей в блоге: 1
18.05.2014, 19:24     Функция удаления листа (или ветки) бинарного дерева
Ваш код, подредактированный и работающий - всё узлы дерева последовательно удаляются, начиная с любого.

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
#include <iostream>
using namespace std;
 
 
struct Node { 
    int value;
    Node *left; 
    Node *right; 
};
 
void add(Node*& p, int value);
void print( Node* p, int level=1 );
Node *del(Node* p,int key);
 
void main() { 
    Node *root = NULL;
    int b[] = {10, 25, 20, 6, 21, 8, 1, 30};
    //cout <<"vvedite 4isla ";
    for( int i = 0; i < 8; i++ ) {
        add(root, b[i]);
    }
 
    for( int i = 0; i < 8; i++ ) {
        cout <<"\n\n"; 
        root = del(root, b[i]);
        print(root);
    }
       
    system("pause");
}
 
void add(Node*& p, int value) { 
    if (p == NULL) {
        p = new Node; 
        p->left = NULL; 
        p->right = NULL; 
        p->value = value; 
    } else { 
        if( value < p->value ) {
            add(p->left, value);  
        } else if( value > p->value ) {
            add(p->right, value);  
        }
    }
}
 
void print( Node* p, int level ) { 
    if( p != NULL ) {
        cout << "Level " << level << ", Value: " << p->value << endl;
    } else if( level == 1 ){
        cout << "Empty tree!" << endl;
        return;
    }
    if( p->left != NULL ) {
        print(p->left, level + 1);
    }
    if( p->right != NULL ) {
        print(p->right, level + 1);
    }
}
 
Node* search(Node* p, int key) {
    if( p == NULL ) { 
        return NULL;
    }
 
    if( key == p->value ) {
        return p;
    } else if( key < p->value ) {
        return search(p->left, key);
    } else {
        return search(p->right, key);
    }
}
 
Node *parent(Node *p, Node *del_p, int key) {
    if( p == NULL ) {
        return NULL;
    }
    if( p->left == del_p || p->right == del_p || p == del_p ) {
        return p;
    }
 
    if( key < p->value ) {
        return parent(p->left, del_p, key);
    } else {
        return parent(p->right, del_p, key);
    }
}
 
Node* find_ld(Node *p) {
    if( p == NULL ) {
        return NULL;
    }
    if( p->left != NULL ) {
        return find_ld(p->left);
    }
    return p;
}
 
Node *del(Node* p, int key) {
    if( p->left == NULL && p->right == NULL ) {
        delete p;
        return NULL;
    }
 
    Node *root = p;
 
    Node* del_p = search(p, key);
    Node* pd = parent(p, del_p, key);
 
    Node* ld = find_ld(del_p->right);
    
    if( ld == NULL ) {
        if( pd->left == del_p ) {
            pd->left = del_p->left;
        } else {
            pd->right = del_p->right;
        }
 
        delete del_p;
        return p;
    }
    Node* pld = parent(p, ld, ld->value);
    
    if( pd == del_p ) {
        pd = ld;
        root = NULL;
    } else if( pd->left == del_p ) {
        pd->left = ld;
    } else {
        pd->right = ld;
    }
 
    if( pld->left == ld ) {
        pld->left = ld->right;
        ld->left = del_p->left;
        ld->right = del_p->right;
    } else {
        pld->right = ld->right;
        ld->left = del_p->left;
    }
 
    delete del_p;
    return (root == NULL)? pd: root;
}
P.S. Для удаления узла, если прямой ссылки на родителя нет (как в данном случае), необходимо знать следующие узлы:
1) Узел, который удаляем
2) Родительский узел узла 1
3) Самый левый лист в правой поддереве узла 1
4) Родительский узел узла 3

P.P.S. Лучшее объяснение двоичных деревьев находил в Кормене когда-то давно.
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru