Es gibt noch mehr Wege binäre Bäume zu implementieren und das Travesieren des Baumes zu Erleichertern. Ich will Ihnen in diesem Kapitel 2 Anregungen dazu geben. Im Kapitel Binäre Bäume Teil 2 haben sie ja das Durchlaufen der Bäume mittels Preorder-Travesierung und Inorder - Travesierung gesehen.

Zeiger auf dem Elternknoten

Wenn man aber nun das Durchlaufen (Travesieren) eines Baumes Interativ und nicht mehr rekursiv machen will (muss) müssen wir unsere Struktur vom Kapitel zuvor um einen Zeiger zum Elternknoten erweitern........

struct binaer_knoten{
                      char ort[255];
                      unsigned int plz;
                      struct binaer_knoten *links;
                      struct binaer_knoten *rechts;
                      struct binaer_knoten *eltern;
                    };  

Nun kann nun jeder Knoten kontrollieren was um Ihn herum ist. Dieser Eltern-Zeiger macht nun das Travesieren des Baumes einfacher aber auch den Schreibaufwand des Programms erheblicher. Außerdem wir damit auch das Einfügen und Löschen eines Elementes verlangsamt, da ein Zeiger mehr erneuert werden muss.

Threads

Mit Threads (threading) haben wir die Möglichkeit einen Baum noch schneller zu Travesieren. Denn anstatt zu überprüfen ob der linke oder recht Teil eines Knoten leer (NULL) ist, was zu einer schlechteren Laufzeit führen könnte, brauchen wir nur 2 Extra-Bits in unsere Struktur einzufügen......

struct binaer_knoten{
                      char ort[255];
                      unsigned int plz;
                      struct binaer_knoten *links;
                      struct binaer_knoten *rechts;
                      unsigned linker_thread:1;
                      unsigned rechter_thread:1;
                    };  

Wenn nun beispielsweise auf der Linke Seite eines Knoten ein weitere Knoten ist steht das Bit linker_tread auf 1, falls sich dort kein Knoten mehr befindet auf 0. Natürlich lässt sich damit ein pauschale Beurteilung einer besseren Laufzeit nicht garantieren, da dies davon abhängt wie der Compiler Bit-Felder optimiert. Aber ein Erleichterung dürfte dies auf jeden Fall darstellen.