Common BoardReply to message- Messages should be written in English and correspond to the matter of the website.
- Messages should not contain offences and obscene words.
- Messages should not contain correct solutions.
Двоичное дерево поиска: не могу найти ошибку в функции, которая удаляет вершину. Помогите пожалуйста. #include <bits/stdc++.h> #define pb push_back #define fs first #define sc second #define INF (1e9+7) #define forn(i,z,n) for( auto (i) = (z); (i) < (n); ++i) using namespace std; typedef long long ll; typedef unsigned long long ull; typedef long double ld; struct node { int key; node *left, *right, *parent; node(int q, node *x, node *y, node *p) { key = q; left = x; right = y; parent = p; } }; node *tree = NULL, *f = NULL; void add_n( node *j, node *&z) { if( z == NULL) { z = new node(j->key,NULL,NULL,NULL); return ; } if( z->key >= j->key) { if( z->left) { add_n(j, z->left); } else { z->left = j; j->parent = z; } } else { if( z->right) { add_n(j,z->right); } else { j->parent = z; z->right = j; } } } void show( node *x) { if( x != NULL) { show(x->left); cout << x->key << ' '; show(x->right); } else return ; } node *find_min( node *root) { if( root->left != NULL) { return find_min(root->left); } else { return root; } } void delete_n(node *root, int val ) { if( root == NULL) return ; else if( val < root->key) delete_n( root->left, val); else if( val > root->key) delete_n(root->right, val); else { if( root->left == NULL && root->right ==NULL) { //delete root; root = NULL; } else if( root->left == NULL) { root->right->parent = root->parent; root = root->right; //delete root->right; root->right = NULL; } else if( root->right == NULL) { root->left->parent = root->parent; root = root->left; //delete root->left; root->left = NULL; } else { node *temp = find_min( root->right); temp->parent = root->parent; root = temp; delete_n( root->right, temp->key); } } return ; } void post( node *x) { if( x != NULL) { post(x->right); post(x->left); cout << x->key << ' '; } } void show_parents( node *z) { if(z != NULL) { show_parents(z->left); show_parents(z->right); if( z->parent != NULL) cout << z->key << ' ' << (z->parent->key) << endl; } } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n; cin >> n; vector <int> v; forn(i,0, n) { int x; cin >> x; v.pb(x); } for(int i = 0; i <n; ++i) { node *help = new node(v[i], NULL, NULL,NULL); add_n( help, tree); } show(tree); // в невозрастающем порядке delete_n(tree, 3); cout << endl; show(tree); return 0; }
|