- #include<iostream>
- using namespace std;
- struct node {
- node *p;
- node *l;
- node *r;
- int val;
- };
- void insert(node *&root, int x, node *p = NULL) { //dodawawanie elementu
- if (root == NULL) {
- root = new node;
- root->val = x;
- root->l = root->r = NULL;
- root->p = p;
- cout << "wstawiamy: " << root->val << endl;
- }
- else if (x < root->val) {
- insert(root->l, x, root);
- }
- else {
- insert(root->r, x, root);
- }
- }
- void inorder(node *&root) { //przeszukiwanie (ciag niemalejacy)
- if (root != NULL) {
- inorder(root->l);
- cout << root->val << " ";
- inorder(root->r);
- }
- }
- node* search_rec(node *&root, int x) { //wyszukiwanie rekurencyjne
- if (root != NULL) {
- if (x == root->val) {
- cout << "wartosc znaleziona: " << root->val << endl;
- return root;
- }
- else if (x < root->val) {
- search_rec(root->l, x);
- }
- else {
- search_rec(root->r, x);
- }
- }
- }
- node* min(node *root) { //najmniejsza wartosc
- if (root != NULL) {
- while (root->l) {
- root = root->l;
- }
- //cout << "minimalna wartosc to: " << root->val << endl;
- return root;
- }
- }
- node* max(node *root) { //najwieksza wartosc
- if (root != NULL) {
- while (root->r) {
- root = root->r;
- }
- //cout << "maksymalna wartosc to: " << root->val << endl;
- return root;
- }
- }
- node* prev(node *root, int liczba) { //znajdowanie poprzednika
- root = search_rec(root, liczba);
- if (root->l != NULL) {
- cout << "poprzednik to: " << (max(root->l))->val << endl;
- return max(root->l);
- }
- else {
- while (root->p) {
- if (root->p->r == root) {
- cout << "poprzednik to: " << root->p->val << endl;
- return root->p;
- }
- else root = root->p;
- }
- cout << "nie ma poprzednika " << endl;
- return 0;
- }
- }
- int counter(node *&root) {
- int i = 0;
- if (root == NULL) {
- return i;
- }
- else{
- i = 1;
- if (root->l) {
- i = i + counter(root->l);
- }
- if (root->r) {
- i = i + counter(root->r);
- }
- }
- return i;
- }
- float avg1(node *&root) {
- float average = 0;
- //average = root->val;
- if (root != NULL) {
- average = root->val;
- if (root->l) {
- average = average + avg1(root->l);
- }
- if (root->r) {
- average = average + avg1(root->r);
- }
- }
- return average;
- }
- float avg2(node *&root) {
- float i = float(counter(root));
- float average = (avg1(root)) / i;
- return average;
- }
- void deleaves(node *&root) {
- if (root) {
- if ((root->l || root->r) == NULL) {
- if (root->p->l == root) {
- root->p->l = NULL;
- }
- else if (root->p->r == root) {
- root->p->r = NULL;
- }
- delete root;
- }
- else {
- deleaves(root->l);
- deleaves(root->r);
- }
- }
- }
- node* del(node *root, int x)
- {
- if (root==NULL) return root;
- else if (x < root->val)
- root->l = del(root->l, x);
- else if (x > root->val) {
- root->r = del(root->r, x);
- }
- else{
- if (root->r == NULL && root->l == NULL){
- delete root;
- root = NULL;
- }
- else if (root->r == NULL){
- node *pom = root;
- root = root->l;
- delete pom;
- }
- else if (root->l == NULL){
- node *pom = root;
- root = root->r;
- delete pom;
- }
- else{
- node *pom = prev(root, x);
- root->val = pom->val;
- root->l = del(root->l, pom->val);
- }
- }
- return root;
- }
- int main() {
- node *root = NULL;
- node *p = NULL;
- insert(root, 4);
- insert(root, 2);
- insert(root, 14);
- insert(root, 0);
- insert(root, 3);
- insert(root, 11);
- insert(root, 6);
- insert(root, 15);
- insert(root, 7);
- insert(root, 8);
- inorder(root);
- cout << endl;
- del(root, 4);
- inorder(root);
- cout << endl;
- //cout << "srednia: " << avg2(root) << endl;
- //cout << "ilosc: " << counter(root) << endl;
- //max(root);
- //prev(root, 0);
- system("PAUSE");
- return 0;
- }