Arbol dinámico

main.cpp

#include <iostream>
#include "btree.hpp"

int main() {

  srand((unsigned) time(nullptr));

  int n = 20;

  btree btree(n);

  while (!btree.full()) {

    int x = rand() % n * 10 + 1;


    btree.ins(x);
    cout << "x: " << x << " ";
    btree.print();
  }

  return 0;
}

ctree.cpp

#include "btree.hpp"

btree::btree(int cap): n(cap), s(0){

  r = nullptr;
}

void btree::ins(int x) {

  assert(!full());

  if (empty()){

    r = new node(x);
    s++;

  }else {

    node *p = r;
    node *q = nullptr;

    while (p and p -> data() != x){

      q = p;

      p = x < p -> data() ? p -> left() : p -> right();
    }

    if (p == nullptr) {

      if (x < q -> data()) q -> left(new node(x));
      else q -> right(new node(x));

      s++;
    }
  }

}

void btree::print() {

  cout << "[ ";
  order(r);
  cout << " ]";
}

void btree::order(node *p) {

  if (p == nullptr) return;

  order(p -> left());
  cout << p -> data() << " ";
  order(p -> right());

}

ctree.hpp

#ifndef btree_hpp
#define btree_hpp

#include<iostream>
#include<cassert>

using namespace std;

class btree{

  class node {

    int _data;

    node *lft;
    node *rgt;

    public:

    node(int x): lft(nullptr), rgt(nullptr) { _data = x; }

    int data() const { return _data; }

    node *left() const { return lft; }
    node *right() const { return rgt; }

    void left(node *p) { lft = p; }
    void right(node *p) { rgt = p; }
  };

  node *r;

int n; //Capacidad
int s; //Tamaño

void order(node *);


public:

  btree(int);
  ~btree(){}

  void ins(int);

  int capacity() const { return n; }
  int size() const { return s;}

  bool empty() const { return s == 0; }
  bool full() const { return s == n; }

  void print();
};

#endif /* btree_hpp*/