Arbol dinámico

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;
}

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());

}

#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*/