INE5408-03208A|INE5609-03238B (20181) - Estruturas de Dados Arvore Binária de Busca com Percursos Descrição

Arquivos requeridos: binary_tree.h, array_list.h ( Baixar)
Número máximo de arquivos: 10
Tipo de trabalho: Trabalho individual

Implemente uma classe ArvoreBinária todas as operações vistas;
Implemente a arvore usando Templates
Implemente a arvore com um numero de elementos variável definido na instanciação
Use as melhores práticas de orientação a objetos
Documente todas as classes, métodos e atributos.
Aplique os testes unitários disponíveis no moodle da disciplina para validar sua estrutura de dados.

Arquivos requeridos

binary_tree.h

#include "array_list.h"


namespace structures {

class BinaryTree {
public:
    ~BinaryTree();

    void insert(const T& data);

    void remove(const T& data);

    bool contains(const T& data) const;

    bool empty() const;

    std::size_t size() const;

    ArrayList<T> pre_order() const;

    ArrayList<T> in_order() const;

    ArrayList<T> post_order() const;

private:
    struct Node {
        Node(const T& data);

        T data;
        Node* left;
        Node* right;

        void insert(const T& data_);

        bool remove(const T& data_);

        bool contains(const T& data_) const;

        void pre_order(ArrayList<T>& v) const;

        void in_order(ArrayList<T>& v) const;

        void post_order(ArrayList<T>& v) const;
    };

    Node* root;
    std::size_t size_;
};

}

Carregando

array_list.h

#ifndef STRUCTURES_ARRAY_LIST_H
#define STRUCTURES_ARRAY_LIST_H

#include <cstdint>


namespace structures {

template<typename T>
class ArrayList {
public:
    ArrayList();
    ArrayList(std::size_t max_size);
    ~ArrayList();

    void clear();
    void push_back(T data);
    void push_front(T data);
    void insert(T data, std::size_t index);
    void insert_sorted(T data);
    T pop(std::size_t index);
    T pop_back();
    T pop_front();
    void remove(T data);
    bool full() const;
    bool empty() const;
    bool contains(const T& data) const;
    std::size_t find(const T& data) const;
    std::size_t size() const;
    std::size_t max_size() const;
    T& at(std::size_t index);
    T& operator[](std::size_t index);
    const T& at(std::size_t index) const;
    const T& operator[](std::size_t index) const;

private:
    T* contents;
    std::size_t size_;
    std::size_t max_size_;

    const static auto DEFAULT_MAX = 10u;
};

}

#endif

Carregando

VPL