Sortowanie tablic z użyciem struktur danych – implementacja drzewa BST

Założenie: Zbudujemy binarne drzewo poszukiwań (BST) w PHP i wykorzystamy je do posortowania tablicy liczb.

Krok po kroku:

1. Definicja klasy Node: Każdy węzeł drzewa będzie reprezentowany przez klasę Node. Zawiera ona wartość, lewe i prawe poddrzewo.

class Node {
    public $data;
    public $left;
    public $right;

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

2. Definicja klasy BST: Klasa BST będzie zarządzać operacjami na drzewie.

class BST {
    public $root;

    public function __construct() {
        $this->root = null;
    }

    public function insert($data) {
        $this->root = $this->_insert($this->root, $data);
    }

    private function _insert($node, $data) {
        if ($node === null) {
            return new Node($data);
        }

        if ($data < $node->data) {
            $node->left = $this->_insert($node->left, $data);
        } else {
            $node->right = $this->_insert($node->right, $data);
        }

        return $node;
    }

    public function inorderTraversal() {
        $result = [];
        $this->_inorderTraversal($this->root, $result);
        return $result;
    }

    private function _inorderTraversal($node, &$result) {
        if ($node !== null) {
            $this->_inorderTraversal($node->left, $result);
            $result[] = $node->data;
            $this->_inorderTraversal($node->right, $result);
        }
    }
}
				

3. Użycie klasy BST: Tworzymy instancję klasy BST, wstawiamy elementy i wyświetlamy posortowaną tablicę.

$bst = new BST();
$numbers = [5, 2, 8, 1, 3, 7, 9, 4, 6];

foreach ($numbers as $number) {
    $bst->insert($number);
}

$sortedNumbers = $bst->inorderTraversal();
print_r($sortedNumbers); // Wyświetli: Array ( [0] => 1 [1] => 2 [2] => 3 [3] => 4 [4] => 5 [5] => 6 [6] => 7 [7] => 8 [8] => 9 )
				

Powyższy kod demonstruje podstawową implementację binarnego drzewa poszukiwań i jego zastosowanie do sortowania. Metoda inorderTraversal zwraca posortowaną tablicę w porządku rosnącym.

Zachęcamy do dalszego zgłębiania tematu struktur danych i algorytmów w PHP!