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*/
Top comments (0)