Arvore Conjunto Fornecedores

// Copyright 2011 Universidade Federal de Minas Gerais (UFMG)
//CLASSE BINARYSEARCHTREE
#ifndef SET_SRC_BINARY_SEARCH_TREE_H_
#define SET_SRC_BINARY_SEARCH_TREE_H_
#include <stdlib.h>
#include "list/src/list.h"
// Implementa uma árvore binária de busca. template<class Type> class BinarySearchTree { public: // Cria uma árvore vazia em O(1).
BinarySearchTree() { right_ = left_ = this;
}
// Testa se a árvore é vazia em O(1). bool empty() { return left_ == this || right_ == this;
}
// Testa se a árvore é uma folha em O(1). bool leaf() { if (empty()) { return false;
} else { return left()->empty() && right()->empty();
}
}
// Retorna a raiz da árvore em O(1).
BinarySearchTree* root() { return this;
}
// Retorna a subárvore esquerda em O(1).
// A árvore não pode ser vazia.
BinarySearchTree* left() { return left_;
}
// Retorna a subarvore direita em O(1).
// A árvore não pode ser vazia.
BinarySearchTree* right() { return right_;
}
// Retorna a chave da árvore em O(1).
// A árvore não pode ser vazia.
Type key() { return key_;
}
// Altera a chave da árvore em O(1).
// Se a árvore for vazia, ela passa então a ser uma folha. void set_key(Type key) {

key_ = key; if (empty()) { left_ = new BinarySearchTree(); right_ = new BinarySearchTree();
}
} int size() { if (empty()) { return 0;
} else { return 1 + left()->size() + right()->size();
}
}
// Retorna o menor elemento da árvore em O(log n).
// A árvore não pode ser vazia.
BinarySearchTree* min() { if (left()->empty()) { return this;
} else { return left()->min();
}
}
// Retorna o menor elemento da árvore em O(log n).
// A árvore não pode ser vazia.
BinarySearchTree* max() { if (right()->empty()) { return this;
} else { return right()->max();
}
}
// Retorna a subárvore cuja chave é x, ou a árvore vazia onde x
// estaria se estivesse na árvore em O(log n).
BinarySearchTree* find(Type x) { if (empty() || x == key()) { return this;
} else if (x < key()) { return left()->find(x);
} else { // x > key() return right()->find(x);
}
}
//