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)

Dodaj komentarz

Twój adres e-mail nie zostanie opublikowany. Pola, których wypełnienie jest wymagane, są oznaczone symbolem *

Możesz użyć następujących tagów oraz atrybutów HTML-a: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>