Дарахти дугоӣ чӣ гуна кор мекунад?

Дарсади дугонаи дугона як сохтори маълумот дар шакли дараст аст, ки дар он ҳар як нод на бештар аз ду фарзанд дорад: чап ва рост.

Принсипҳои фаъолият:

• Тамос: Ноде дар болоии дараст.
• Нодҳо: Маъlumotҳоро нигоҳ медоранд ва ба нодҳои фарзанд ишора мекунанд.
• Баргҳо: Нодҳое, ки фарзанд надоранд.
• Пайвандҳо: Аз ноде ба нодҳои фарзанд равона шудаанд.

Оператсияҳои асосӣ:

• Илова кардан: Нодҳои нав дар ҷои муайян дар дараст гузошта мешаванд, бо нигоҳ доштани сохтор ва қоидаҳои он (масалан, барои дарахти ҷустуҷӯии дугона: арзишҳои хурдтар ба чап, калонтар ба рост).
• Ҷустуҷӯ: Гузариш дар нодҳо барои ёфтани унсури махсус. Дар дарахти ҷустуҷӯии дугона, ҷустуҷӯ самаранок аст бо сабаби тартиб додани маълумот.
• Баъд аз тоза кардан: Тоза кардани нод бо навсозии сохтори дараст.
• Гузариш: Визит кардани ҳамаи нодҳои дараст дар тартиби муайян:
  • Пеш-тартиб: Тамос, зер-дараҷаҳои чап, зер-дараҷаҳои рост.
  • Пас-тартиб: Зер-дараҷаҳои чап, зер-дараҷаҳои рост, тамос.
  • Дар-тартиб: Зер-дараҷаҳои чап, тамос, зер-дараҷаҳои рост (фаҳмидани рӯйхати сортшудаи унсурҳо).

Фоидаҳо:

• Ҷустуҷӯ, илова ва тоза самаранок (дар дарахтҳои баробарбаланд).
• Барои намоиши маълумоти ҳиерархӣ истифода мешавад.

Намунаи сохтори нод дар PHP:

<?php

class Node {
    public $data; // Маълумоти нод
    public $left; // Нод чап
    public $right; // Нод рост

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