Implementar a estrutura de dados da árvore binária em C++

1. Implementar a árvore binária usando a palavra-chave struct em C++
2. Implementar funções para calcular o tamanho e a altura da estrutura da árvore e uma função para imprimir elementos em C++

Este artigo explicará como implementar a estrutura de dados de árvore binária em C++.

Implementar a árvore binária usando a palavra-chave struct em C++

Árvores são estruturas de dados abstratas utilizadas em vários algoritmos fundamentais. Geralmente são estruturas hierárquicas em que é necessário haver um nó raiz e seus filhos formando subárvores. Além disso, existem vários tipos de estrutura de árvore, cada um adequado para necessidades específicas e fornecendo algumas vantagens e desvantagens.

Uma árvore binária é uma das subclasses das estruturas de dados em árvore e é definida como uma árvore em que cada nó deve ter no máximo dois filhos, incluindo nós filhos designados como left e right. Nesse caso, implementamos uma árvore binária usando a função struct, pois ela declara uma classe onde os membros são públicos por padrão. Um nó em uma árvore binária contém dois ponteiros para os nós esquerdo/direito e os dados conforme necessário. Observe que declaramos um único membro int para representar os dados armazenados no nó apenas para fins de explicação.

Definimos um construtor que recebe um inteiro como argumento e inicializa o membro data com seu valor. Em seguida, ele inicializa os ponteiros de dois nós com valores nullptr, que é uma forma comum de denotar os nós folha. O código do driver de exemplo constrói um gráfico de amostra e armazena inteiros aleatórios em cada nó. Existem vários subtipos de árvores binárias, por exemplo, uma árvore binária completa é uma estrutura em que cada nó tem 0 ou 2 filhos. Outra é chamada de árvore binária perfeita, em que todos os nós internos têm dois filhos e todos os nós folha têm profundidades idênticas.

#include <iostream>
#include <random>

using std::cout;
using std::endl;

struct BinTreeNode {
  int data;
  struct BinTreeNode *left;
  struct BinTreeNode *right;

  BinTreeNode() = default;
  explicit BinTreeNode(int d) : data(d) {
    left = nullptr;
    right = nullptr;
  }
};

constexpr int MIN = 1;
constexpr int MAX = 10000;

int main() {
  std::random_device rd;
  std::mt19937 eng(rd());
  std::uniform_int_distribution<int> distr(MIN, MAX);

  auto root = new BinTreeNode(distr(eng));
  root->left = new BinTreeNode(distr(eng));
  root->right = new BinTreeNode(distr(eng));
  root->right->left = new BinTreeNode(distr(eng));
  root->right->right = new BinTreeNode(distr(eng));

  return EXIT_SUCCESS;
}

Observe que o código acima resulta em uma estrutura de árvore binária completa, conforme exibido no gráfico a seguir. Alocamos cada nó usando o operador new e passamos um valor inicializador usando o gerador de números pseudo-aleatórios.

root / left right / \ / nullptr nullptr left right /   \ /
    nullptr nullptr nullptr nullptr

Implementar funções para calcular o tamanho e a altura da estrutura da árvore e uma função para imprimir elementos em C++

Uma vez que a estrutura em árvore é a forma na qual os algoritmos de divisão e conquista são executados, o último método é frequentemente utilizado para implementar as funções que manipulam seus elementos. A função treeSize recupera o tamanho da árvore que denota o número de todos os nós, incluindo a raiz. Observe que só precisamos usar uma recursão simples e retornar o tamanho do valor root (que é 1) mais os tamanhos dos nós esquerdo/direito.

A próxima função é treeHeight que recupera a altura da árvore, que é geralmente conhecida como a quantidade de nós no caminho mais longo de uma raiz a uma folha. Esta função também utiliza a recursão chamando a si mesma em ambos os nós filhos e retornando a altura do valor root (que é 1) mais o maior valor das chamadas anteriores.

Por outro lado, a função printData produz o membro data de cada nó para o fluxo cout. Existem várias maneiras de travessia para a estrutura de árvore binária: travessia em ordem, pré-ordem e pós-ordem.

No exemplo a seguir, a maneira de travessia em ordem é utilizada. O processo imprime os dados dos nós de folha mais à esquerda indo para a direita na mesma profundidade no início e depois passa para os níveis superiores. O próximo fragmento de código constrói uma árvore binária parcialmente aleatória e, em seguida, chama cada uma das funções acima nela. Se a natureza recursiva dessas funções parecer confusa à primeira vista, você deve tentar depurá-las passo a passo nos objetos de árvore menores e observar o comportamento em cada chamada de função recursiva.

#include <iostream>
#include <random>

using std::cout;
using std::endl;

struct BinTreeNode {
  int data;
  struct BinTreeNode *left;
  struct BinTreeNode *right;

  BinTreeNode() = default;
  explicit BinTreeNode(int d) : data(d) {
    left = nullptr;
    right = nullptr;
  }
};

int treeSize(BinTreeNode *n) {
  if (n == nullptr)
    return 0;
  else
    return 1 + treeSize(n->left) + treeSize(n->right);
}

int treeHeight(BinTreeNode *n) {
  int lh, rh;

  if (n == nullptr)
    return -1;
  else {
    lh = treeHeight(n->left);
    rh = treeHeight(n->right);
    return 1 + (lh > rh ? lh : rh);
  }
}

void printData(BinTreeNode *n) {
  if (n != nullptr) {
    printData(n->left);
    cout << n->data << "; ";
    printData(n->right);
  }
}

constexpr int MIN = 1;
constexpr int MAX = 10000;

int main() {
  std::random_device rd;
  std::mt19937 eng(rd());
  std::uniform_int_distribution<int> distr(MIN, MAX);

  auto root = new BinTreeNode(distr(eng));
  auto tmp = root;

  auto iter = 100;
  while (iter > 0) {
    auto val = distr(eng);
    if (val % 5 == 0) {
      tmp->left = new BinTreeNode(distr(eng));
      tmp = tmp->left;
    } else if (val % 4 == 0) {
      tmp->right = new BinTreeNode(distr(eng));
      tmp = tmp->right;
    } else if (val % 6 == 0) {
      tmp->left = new BinTreeNode(distr(eng));
    } else if (val % 100 == 0) {
      tmp = root;
    } else if (val % 2 == 0) {
      tmp->right = new BinTreeNode(distr(eng));
    }
    iter -= 1;
  }

  cout << "size of tree = " << treeSize(root) << endl;
  cout << "height of tree = " << treeHeight(root) << endl;
  printData(root);

  return EXIT_SUCCESS;
}

Resultado:

size of tree = 45 height of tree = 37 ...(elements in the tree)