Como funciona uma árvore binária?

Uma árvore binária é uma estrutura de dados em forma de árvore, onde cada nó tem no máximo dois nós filhos: esquerdo e direito.

Princípios de funcionamento:

• Raiz: Nó superior da árvore.
• Nodos: Contêm dados e referências a nodos filhos.
• Folhas: Nodos sem nodos filhos.
• Conexões: Dirigidas do nodo pai para os filhos.

Operações principais:

• Inserção: Novos nodos são adicionados num local específico da árvore, mantendo a sua estrutura e regras (por exemplo, para uma árvore binária de pesquisa: valores menores à esquerda, maiores à direita).
• Procura: Percurso dos nodos para encontrar um elemento específico. Em uma árvore binária de pesquisa, a procura é eficiente devido à ordenação dos dados.
• Remoção: Remoção de um nodo com reestruturação da árvore.
• Percurso: Visitar todos os nodos da árvore numa ordem específica:
  • Pré-ordem: Raiz, subárvore esquerda, subárvore direita.
  • Pós-ordem: Subárvore esquerda, subárvore direita, raiz.
  • Em-ordem: Subárvore esquerda, raiz, subárvore direita (para uma árvore binária de pesquisa, fornece uma lista ordenada de elementos).

Vantagens:

• Procura, inserção e remoção eficientes (em árvores balanceadas).
• Usado para representar dados hierárquicos.

Exemplo de estrutura de um nodo em PHP:

<?php

class Node {
    public $data; // Dados do nodo
    public $left; // Nodo filho esquerdo
    public $right; // Nodo filho direito

    public function __construct($data) {
        $this->data = $data;
        $this->left = null;
        $this->right = null;
    }
}