binarytreefinal.cpp

#include <iostream>
#include <string>
#include <iomanip>

using namespace std;

class Leave {
  public:
    int idNumber;
    string name;
    int age;
    Leave* left;
    Leave* right;

    Leave(): idNumber(-1), name(""), age(0), left(NULL), right(NULL) {}

    Leave(int d, string n, int a, Leave* l = NULL, Leave* r = NULL) {
      this->idNumber = d;
      this->name = n;
      this->age = a;
      this->left = l;
      this->right = r;
    }
};

class Tree {
  private:
    Leave* search(Leave* r, int id) {
      if(r == NULL) {
        cout << "User does not exist" << endl;
        return NULL;
      }

      if(r->idNumber == id) {
        return r;
      } else {
        if(r->idNumber > id) {
          // go left
          this->search(r->left, id);
        } else if(r->idNumber < id) {
          // go right
          this->search(r->right, id);
        }
      }
    }

  public:
    Leave *root;

    Tree(): root(NULL) {}

    void preorder(Leave* r) {
      cout << "Id: " << r->idNumber;
      cout << "\tName: " << r->name;
      cout << "\tAge: " << r->age << endl;

      if(r->left != NULL) {
        this->preorder(r->left);
      }

      if(r->right != NULL) {
        this->preorder(r->right);
      }
    }

    void inorder(Leave* r) {
      if(r->left != NULL) {
        this->inorder(r->left);
      }

      cout << "Id: " << r->idNumber;
      cout << "\tName: " << r->name;
      cout << "\tAge: " << r->age << endl;

      if(r->right != NULL) {
        this->inorder(r->right);
      }
    }

    void postorder(Leave* r) {
      if(r->left != NULL) {
        this->postorder(r->left);
      }

      if(r->right != NULL) {
        this->postorder(r->right);
      }

      cout << "Id: " << r->idNumber;
      cout << "\tName: " << r->name;
      cout << "\tAge: " << r->age << endl;
    }

    Leave* search(int idNumber) {
      return this->search(this->root, idNumber);
    }

    void add(int idNumber, string name, int age) {
      if (this->root == NULL) {
        this->root = new Leave(idNumber, name, age);
      } else {
        Leave* r = this->root;

        while(r != NULL) {
          if (r->idNumber == idNumber) {
            cout << "Id already in use. Not inserted" << endl;
            r = NULL;
          } else if (r->idNumber > idNumber) {
            if (r->left == NULL) {
              r->left = new Leave(idNumber, name, age);
              r = NULL;
            } else {
              r = r->left;
            }
          } else if(r->idNumber < idNumber) {
            if(r->right == NULL) {
              r->right = new Leave(idNumber, name, age);
              r = NULL;
            } else {
              r = r->right;
            }
          }
        }
      }
    }

    void update(int idNumber, string name = "", int age = 0) {
      Leave* r = this->search(idNumber);

      if(r != NULL) {
        r->name = (name.empty() ? r->name : name);
        r->age = (age == 0 ? r->age : age);
        cout << "Element correctly updated" << endl;
      }
    }

    void insertLeave(Leave* r, Leave* n) {
      if (r->idNumber > n->idNumber) {
        if (r->left == NULL) {
          r->left = n;
        } else {
          this->insertLeave(r->left, n);
        }
      } else if(r->idNumber < n->idNumber) {
        if(r->right == NULL) {
          r->right = n;
        } else {
          this->insertLeave(r->right, n);
        }
      }
    }

    Leave* parentOf(Leave* l) {
      Leave* parent = NULL;

      if (this->root->idNumber == l->idNumber) {
        cout << "Leave specified does not have a parent" << endl;
      } else {
        parent = this->root;
        Leave* r = this->root;

        while (r != NULL) {
          if (r->idNumber > l->idNumber) {
            parent = r;
            r = r->left;
          } else if (r->idNumber < l->idNumber) {
            parent = r;
            r = r->right;
          } else if (r->idNumber == l->idNumber) {
            break;
          }
        }
      }

      return parent;
    }

    void deleteLeave(int idNumber) {
      Leave *r = this->search(idNumber);

      if(r != NULL && this->root->idNumber != idNumber) {
        Leave* parent = this->parentOf(r);
        
        if (parent->left->idNumber == r->idNumber) {
          parent->left = NULL;
        } else {
          parent->right = NULL;
        }

        if (r->right != NULL)
            this->insertLeave(parent, r->right);
            
        if(r->left != NULL)
            this->insertLeave(parent, r->left);

        delete r;
      }
    }


    int level(Leave* r) {
      int left = 0;
      int right = 0;

      if (r->left == NULL && r->right == NULL) {
        return 1;
      } else {
        if(r->left != NULL)
          left = 1 + this->level(r->left);

        if(r->right != NULL)
          right = 1 + this->level(r->right);

        if (left > right) {
          return left;
        } else {
          return right;
        }
      }
    }

    int grade(Leave* r) {
      int result = 0;
      result += r->left != NULL ? 1 : 0;
      result += r->right != NULL ? 1 : 0;

      return result;
    }

    int height() {
      return this->level(this->root);
    }

    void children(Leave* r) {
      if (r->left != NULL) {
        cout << "left " << r->left->idNumber << endl;
      }

      if(r->right != NULL) {
        cout << "right " << r->right->idNumber << endl;
      }
    }
};

int main()
{
  char letters[] = "abcdefghijklmnopqrstuvwxyz";
  int nodes[] = { 20, 10, 30, 5, 15, 25, 35, 2, 7, 12, 17, 6, 8, 13 };

  // int nodes[] = { 50, 27, 60, 20, 40, 55, 65, 10, 25, 35, 45, 24, 26, 37 };
  Tree* arbol = new Tree();
  // arbol->root = new Leave(25, "Esteban", 25);

  for(int i = 0; i < 14; i++) {
    arbol->add(nodes[i], string(1, letters[rand() % 26]), (int)(1 + rand() % 90));
  }

  while(true) {
    cout << "Ingrese opcion" << endl;
    int menu = -1;
    cout << "1. preorden\n2.inorder\n3.posorden\n4.buscar cedula\n5.eliminar persona\n6.insertar persona\n7.nivel de una cedula\n8.grado de una cedula\n9.Altura del arbol\n10.Padre de una cedula\n11.Hijos de cedula\0exit: " << endl;
    cin >> menu;
    switch (menu) {
        case 0:
            return 0;
        case 1:
            cout << "Arbol preorden" << endl;
            arbol->preorder(arbol->root);
            break;
        case 2:
            cout << "Arbol inorden" << endl;
            arbol->inorder(arbol->root);
            break;
        case 3:
            cout << "Arbol posorden" << endl;
            arbol->postorder(arbol->root);
            break;
        case 4:
            cout << "Ingrese cedula" << endl;
            int valor_x;
            cin >> valor_x;
            Leave* tmp_x;
            tmp_x = arbol->search(valor_x);
            if (tmp_x != NULL) {
                cout << "encontrado" << endl;
                cout << "Cedula: " << tmp_x->idNumber << "\tNombre: " << tmp_x->name << "\tEdad: " << tmp_x->age << endl;
            }
            break;
        case 5:
            cout << "Ingrese cedula" << endl;
            int valor_y;
            cin >> valor_y;
            arbol->deleteLeave(valor_y);
            break;
        case 6:
        {
            cout << "Ingrese cedula: ";
            int valor_z;
            cin >> valor_z;
            cout << "Ingrese nombre ";
            string name_x;
            cin >> name_x;
            cout << "Ingrese edad ";
            int edad_x;
            cin >> edad_x;
            arbol->add(valor_z, name_x, edad_x);
            break;
        }
        case 7:
        {
            cout << "Ingrese cedula" << endl;
            int valor;
            cin >> valor;
            
            Leave * tmp = arbol->search(valor);
            
            if(tmp)
                cout << "nivel cedula " << arbol->level(tmp) << endl;

            break;
        }
        case 8:
        {
            cout << "Ingrese cedula" << endl;
            int valor;
            cin >> valor;
            Leave *tmp = arbol->search(valor);
            
            if(tmp)
                cout << "Grado de cedula " << arbol->grade(tmp) << endl;
                
            break;
        }
        case 9:
        {
            cout << "Altura del arbol " << arbol->height() << endl;
            break;
        }
        case 10:
        {
            cout << "Ingrese cedula ";
            int valor;
            cin >> valor;
            Leave *tmp = arbol->search(valor);
            if(tmp)
                cout << "Padre es " << arbol->parentOf(tmp)->idNumber << endl;
            
            break;
        }
        case 11:
        {
            cout << "Ingrese cedula ";
            int valor;
            cin >> valor;
            Leave *tmp = arbol->search(valor);
            if(tmp)
                arbol->children(tmp);
            break;
        }
        default:
          break;
    }
  }

  return 0;
}