Archiwa tagu: C++

Jednoznaczny print Binary Search Tree w konsoli

Prawdę mówiąc szukałem i szukałem jakiegoś prostego rozwiązania na jednoznaczne wyświetlenie drzewa w konsoli i o ile problem wydaje się trywialny to nie znalazłem nic zadowalającego mnie. W takim wypadku należało samemu napisać coś prostego.

Mój pomysł jest banalny, ale wydaje się skuteczny – w jednoznaczny sposób z zapisu w konsoli jestem w stanie odczytać jakie drzewo mam zapisane w pamięci.

Oto kod:

void inorder(BinarySearchTreeNode* p)
{
	if(p != nullptr)
    {
		if (p != root && (p->left || p->right) ) cout << "{";
		if(p->left) 
        {
            inorder(p->left);
            cout << "<-";
        }

		cout << p->value;

        if(p->right)
        {
            cout << "->";
            inorder(p->right);
        }
		if (p != root && (p->left || p->right)) cout << "}";
   }
}

Kilka słów wyjaśnienia – w tym celu przykład:

{{0<-1->2}<-3->{4<-5->6}}<-7->{{8<-9->10}<-11->{12<-13->14}}

Żeby rozszyfrować to przykładowe drzewo muszę zawsze wziąć element nie zawarty w żadnym nawiasie (najwyżej) i potraktować go jako korzeń drzewa. W tym przypadku będzie to 7. Potem strzałeczki w lewo i prawo to jego poddrzewa – każde poddrzewo zawarte w nawiasie traktuje jako kolejne drzewo i rozpoczynam cały proces od początku. Jeżeli nie ma nawiasu to znaczy że doszliśmy do liścia. Koniec ;-)


(wybaczcie jakość rysunku, ale nie znalazłem żadnego narzędzia prostego do rysowania grafów xD)