Drukowanie BST w konsoli

Witam, czy ktoś posiada gotową, działającą funkcję drukującą drzewko w jakiejś przejrzystej formie? Chodzi mi o odpowiednie operacje ze spacjami i enterami. Nie musi być kresek łączących, wystarczy żeby to wizualnie przypominało drzewo. Moja struktura zawiera tylko wskaźniki na synów. Coś rekurencyjnego chyba nie wchodzi w grę, prawda? Jakoś nie mogę trafić w internecie na jakiś gotowy model tego. Pomyślałem, że ktoś z Was już to ma.

Nie mam, ale podam prosty (tak mi się wydaje) sposób na jego zrealizowanie.
Ustawiasz kursor w jakieś pozycji x jak przeszukujesz binarne drzewo (rekurencyjnie) to robisz prosta zaleznosc

poczatek
WYSWIETL(tak po prostu)
zapamietaj w tmp wyswietlona pozycje
jezeli istnieje lewa strona to zrob x-2(czy jaka kolwiek inna liczba) i wywolaj funkcje rekurencjyjna dla lewej strony
ustaw X = tmp
jezeli istnieje prawa strona to zrob x+2 i wywolaj funkcje rekurencjyjna dla lewej strony

koniec

http://web.archive.org/web/20090617110918/http://www.openasthra.com/c-tidbits/printing-binary-trees-in-ascii/

Co myślisz nad skorzystaniem z tego gotowca? Chyba działa, bo ludzie dziękują za kod. Tylko wygląda trochę na wyolbrzymienie problemu, koleś natrzaskał tych funkcji, że fiu fiu...

A możesz wypisywać drzewo poziomo? Tzn. korzeń na lewo, dzieci na prawo (w przeciwieństwie do korzeń na górze, dzieci niżej)?

Jeśli tak to problem bardzo elegancko można rozwiązać za pomocą przeglądania wierzchołków drzewa inorder (http://pl.wikipedia.org/wiki/Przechodzenie_drzewa). Chętnie pomogę w implementacji jeśli tak, bo ciekawy jestem jak to by wyglądało ;]

void drzewko::_print(element *tmp,unsigned h,unsigned long long M) const
  {
   if(tmp->L) _print(s,tmp->L,h+1,M<<1); 
   for(unsigned i=h-2;i<h;--i)
     {
      unsigned long long m=(M>>i)&3;
      if((m==0)||(m==3)) cout<<" "; else cout<<"\xB3";
      cout<<" ";
     }
   if(h)
     {
      if(M&1) cout<<"\xC0"; else cout<<"\xDA";
      cout<<"\xC4";
     }
   cout<<"\xDB "<<tmp->dane<<endl;
   if(tmp->R) _print(s,tmp->R,h+1,(M<<1)|1);
  }

Odpalasz: _print(root,0,0);

Mógłbyś napisać jak będą wyglądały printfy zamiast coutów? Niestety nie mam c++ i nie ogarniam tych modyfikatorów druku.
Ogółem potrzebuję to w C, ale reszta jest analogiczna, no może jeszcze poza tym constem za funkcją, ale raczej to mi nie zrobi żadnego znaczenia, jeżeli to zwyczajnie usunę.

Wynik wygląda tak:

  ┌─█ 0
┌─█ 1
│ └─█ 2
█ 3
│ ┌─█ 4
└─█ 5
  └─█ 7

Przerobiłem w ten sposób:

void print(struct node *tmp,unsigned h,unsigned long long M)
  {
        unsigned int i;
   if(tmp->left) print(tmp->left,h+1,M<<1);
   for(i=h-2;i<h;--i)
     {
      unsigned long long m=(M>>i)&3;
      if((m==0)||(m==3)) printf(" "); else printf("\xB3");
      printf(" ");
     }
   if(h)
     {
      if(M&1) printf("\xC0"); else printf("\xDA");
      printf("\xC4");
     }
   printf("\xDB%d \n", tmp->value);
   if(tmp->right) print(tmp->right,h+1,(M<<1)|1);
  }

Niestety coś działa nie tak jak trzeba:

Ok, na konsoli windowsowej wszystko działa ok, tylko w putty się wykrzaczyło. :)
Mam pytanie odnośnie poprawności tego druku. Przecież lewy węzeł nie powinien mieć wartości większych od parenta. A tutaj jest wręcz odwrotnie.

Ok, zamieniłem sobie z ->left na ->right i odwrotnie, druk jest w porządku. Teraz mam jeszcze jedno pytanie. Mam ten wydruk zastosować dla drzew czerwono-czarnych. Czy dobrym rozwiązaniem będzie pokolorowanie tych bloczków na czerwono jeżeli odpowiednia wartość węzła wskazuje na kolor czerwony? Wykorzystałbym ncurses do tego.