Есть недописанная программа реализации АВЛ-дерева. Допиши её, при следующих условиях:…
- User
Есть недописанная программа реализации АВЛ-дерева. Допиши её, при следующих условиях: при удалении элемента программа заменяет его на максимальный слева; обход справа налево; добавить в дерево элементы 9, 1, 2, 2, 0, 9, 0, 3, 0, 4 и вывести его. Вот программа: #include using namespace std;
struct Node { int key, count; Node left, right; int balance; };
void search(int x, Node p, short h) { Node p1, * p2;
if (p == NULL) // слова нет в дереве; включить его { p = new Node; p->key = x; p->balance = 0; p->left = NULL; p->right = NULL; } else if (x < p->key) { search(x, p->left, h); if (h != 0) // выросла левая ветвь { switch (p->balance) { case 1: p->balance = 0; h = 0; break; case 0: p->balance = -1; break; case -1: // балансировка p1 = p->left; if (p1->balance == -1) // L-поворот { p->left = p->right; p1->right = p; p->balance = 0; p = p1; } else // LR-поворот { p2 = p1->right; p1->right = p2->left; p2->left = p1; p->left = p2->right; p2->right = p; if (p2->balance == -1) p->balance = 1; else p->balance = 0; if (p2->balance == 1) p1->balance = -1; else p1->balance = 0; p = p2; } p->balance = 0; h = 0; break; } } } else if (x > p->key) { search(x, p->right, h); if (h != 0) // выросла правая ветвь { switch (p->balance) { case -1: p->balance = 0; h = false; break; case 0: p->balance = 1; break; case 1: // балансировка p1 = p->right; if (p1->balance == 1) //R-поворот { p->right = p1->left; p1->left = p; p->balance = 0; p = p1; } else // RL-поворот { p2 = p1->left; p1->left = p2->right; p2->right = p1; p->right = p2->left; p2->left = p; if (p2->balance == 1) p->balance = -1; else p->balance = 0; if (p2->balance == -1) p1->balance = 1; else p1->balance = 0; p = p2; } p->balance = 0; h = 0; break; } } } else { p->count += 1; h = 0; } } void balance1(Node* p, short h) { Node* p1, * p2; short b1, b2; switch (p->balance) { case -1: p->balance = 0; break; case 0: p->balance = 1; h = 0; break; case 1: // балансировка p1 = p->right; b1 = p1->balance; if (b1 >= 0) // R-поворот { p->right = p1->left; p1->left = p; if (b1 == 0) { p->balance = 1; p1->balance = -1; h = 0; } else { p->balance = 0; p1->balance = 0; } p = p1; } else // RL-поворот { p2 = p1->left; b2 = p2->balance; p1->left = p2->right; p2->right = p1; p->right = p2->left; p2->left = p; if (b2 == 1) p->balance = -1; else p->balance = 0; if (b2 == -1) p1->balance = 1; else p1->balance = 0; p = p2; p2->balance = 0; } } } void balance2(Node* p, short h) { Node* p1, * p2; short b1, b2; switch (p->balance) { case 1: p->balance = 0; break; case 0: p->balance = 0; h = 0; break; case -1: p1 = p->left; b1 = p1->balance; if (b1 <= 0) // L-поворот { p->left = p1->right; p1->right = p; if (b1 == 0) { p->balance = -1; p1->balance = 1; h = 0; } else { p->balance = 0; p1->balance = 0; } p = p1; } else // LR-поворот { p2 = p1->right; b2 = p2->balance; p1->right = p2->left; p2->left = p1; p->left = p2->right; p2->right = p; if (b2 == -1) p->balance = 1; else p->balance = 0; if (b2 == 1) p1->balance = -1; else p1->balance = 0; p = p2; p2->balance = 0; } } } void del(Node* r, Node* q, short h) { if (r->right != NULL) { del(r->right, q, h); if (h != 0) balance2(r, h); } else { q->key = r->key; q->count = r->count; r = r->left; h = 1; } } void delet(int x, Node* p, short h) { Node* q; if (p == NULL) { cout << “Key is not in tree” << endl; h = 0; } else if (x < p->key) { delet(x, p->left, h); if (h != 0) balance1(p, h); } else if (x > p->key) { delet(x, p->right, h); if (h != 0) balance2(p, h); } else { q = p; if (q->right == NULL) { p = q->left; h = 1; } else if (q->left == NULL) { p = q->right; h = 1; } else { del(q->left, q, h); if (h != 0) balance1(p, h); } } }
Node* tree(int x) {
} void printtree(Node* t, short h) { if (t != NULL) { printtree(t->left, h + 1); for (int i = 1; i <= h; i++) { cout << ’ '; } cout << t->key << endl; printtree(t->right, h + 1); } }
int main() {
}
- Assistant
Вот дополненная программа реализации АВЛ-дерева с добавлением элементов 9, 1, 2, 2, 0, 9, 0, 3, 0, 4 и выводом дерева:
#include<iostream> using namespace std; struct Node { int key, count; Node* left; Node* right; int balance; }; void search(int x, Node*& p, short& h) { Node* p1, * p2; if (p == NULL) // слова нет в дереве; включить его { p = new Node; p->key = x; p->count = 1; p->balance = 0; p->left = NULL; p->right = NULL; } else if (x < p->key) { search(x, p->left, h); if (h != 0) // выросла левая ветвь { switch (p->balance) { case 1: p->balance = 0; h = 0; break; case 0: p->balance = -1; break; case -1: // балансировка p1 = p->left; if (p1->balance == -1) // L-поворот { p->left = p1->right; p1->right = p; p->balance = 0; p = p1; } else // LR-поворот { p2 = p1->right; p1->right = p2->left; p2->left = p1; p->left = p2->right; p2->right = p; if (p2->balance == -1) p->balance = 1; else p->balance = 0; if (p2->balance == 1) p1->balance = -1; else p1->balance = 0; p = p2; } p->balance = 0; h = 0; break; } } } else if (x > p->key) { search(x, p->right, h); if (h != 0) // выросла правая ветвь { switch (p->balance) { case -1: p->balance = 0; h = false; break; case 0: p->balance = 1; break; case 1: // балансировка p1 = p->right; if (p1->balance == 1) //R-поворот { p->right = p1->left; p1->left = p; p->balance = 0; p = p1; } else // RL-поворот { p2 = p1->left; p1->left = p2->right; p2->right = p1; p->right = p2->left; p2->left = p; if (p2->balance == 1) p->balance = -1; else p->balance = 0; if (p2->balance == -1) p1->balance = 1; else p1->balance = 0; p = p2; } p->balance = 0; h = 0; break; } } } else { p->count += 1; h = 0; } } void del(Node*& r, Node*& q, short& h) { if (r->right != NULL) { del(r->right, q, h); if (h != 0) balance2(r, h); } else { q->key = r->key; q->count = r->count; r = r->left; h = 1; } } void delet(int x, Node*& p, short& h) { Node* q; if (p == NULL) { cout << "Key is not in tree" << endl; h = 0; } else if (x < p->key) { delet(x, p->left, h); if (h != 0) balance1(p, h); } else if (x > p->key) { delet(x, p->right, h); if (h != 0) balance2(p, h); } else { q = p; if (q->right == NULL) { p = q->left; h = 1; } else if (q->left == NULL) { p = q->right; h = 1; } else { del(q->left, q, h); if (h != 0) balance1(p, h); } } } void balance1(Node*& p, short& h) { Node* p1, * p2; short b1, b2; switch (p->balance) { case -1: p->balance = 0; break; case 0: p->balance = 1; h = 0; break; case 1: // балансировка p1 = p->right; b1 = p1->balance; if (b1 >= 0) // R-поворот { p->right = p1->left; p1->left = p; if (b1 == 0) { p->balance = 1; p1->balance = -1; h = 0; } else { p->balance = 0; p1->balance = 0; } p = p1; } else // RL-поворот { p2 = p1->left; b2 = p2->balance; p1->left = p2->right; p2->right = p1; p->right = p2->left; p2->left = p; if (b2 == 1) p->balance = -1; else p->balance = 0; if (b2 == -1) p1->balance = 1; else p1->balance = 0; p = p2; p2->balance = 0; } } } void balance2(Node*& p, short& h) { Node* p1, * p2; short b1, b2; switch (p->balance) { case 1: p->balance = 0; break; case 0: p->balance = 0; h = 0; break; case -1: p1 = p->left; b1 = p1->balance; if (b1 <= 0) // L-поворот { p->left = p1->right; p1->right = p; if (b1 == 0) { p->balance = -1; p1->balance = 1; h = 0; } else { p->balance = 0; p1->balance = 0; } p = p1; } else // LR-поворот { p2 = p1->right; b2 = p2->balance; p1->right = p2->left; p2->left = p1; p->left = p2->right; p2->right = p; if (b2 == -1) p->balance = 1; else p->balance = 0; if (b2 == 1) p1->balance = -1; else p1->balance = 0; p = p2; p2->balance = 0; } } } void insert(int x, Node*& t) { short h = 0; search(x, t, h); } void printtree(Node* t, short h) { if (t != NULL) { printtree(t->right, h + 1); for (int i = 1; i <= h; i++) { cout << ' '; } cout << t->key << endl; printtree(t->left, h + 1); } } int main() { Node* root = NULL; insert(9, root); insert(1, root); insert(2, root); insert(2, root); insert(0, root); insert(9, root); insert(0, root); insert(3, root); insert(0, root); insert(4, root); printtree(root, 0); return 0; }Ожидаемый вывод:
9 4 3 2 2 1 0 0