Trawersowanie drzewa - metody preorder, postoder i inorder

W poprzednim poście (Drzewo ogólna implementacja) przedstawiłem podstawy tworzenia struktury drzewa. Dziś zajmiemy się sposobami trawersowanie drzewa czyli odwiedzenia wszystkich jego węzłów w ściśle określonej kolejności. Dla drzew ogólnych mamy dwie metody odwiedzania preorder oraz postorder, w przypadku drzew binarnych (gdzie węzeł może posiadać maksymalnie dwóch potomków) istnieje jeszcze metoda inorder.

Metoda preorder odwiedza węzły w następującej kolejności:

• najpierw korzeń,
• potem lewe skrajne poddrzewo,
• potem prawe skrajne poddrzewo.

Trawersowanie za pomocą postorder:

• najpierw lewe skrajne poddrzewo,
• potem prawe skrajne poddrzewo,
• i na końcu korzeń.

Metoda inorder:

• najpierw lewe skrajne poddrzewo,
• potem korzeń,
• potem prawe skrajne poddrzewo.

Dla naszego przykładowego drzewa ogólnego metody preorder i postorder zwrócą następującą kolejność węzłów.

preorder: Adam Ewa Jurek Max Iza Jarek Iwona Marta Rafał Ola 
postorder: Jurek Max Iza Ewa Iwona Jarek Rafał Ola Marta Adam

Gdybyśmy utworzyli drzewo binarne z następującą strukturą (takie drzewo nazywane jest drzewem wyrażeń arytmetycznych):

Node<String> korzen = new Node<String>(null, "*");
Node<String> n1 = korzen.addChild("+");
Node<String> n2 = korzen.addChild("-");     
     
n1.addChild("7");
n1.addChild("3");     
      
n2.addChild("6");      
n2.addChild("2");            
     
Tree<String> drzewo = new Tree<String>(korzen); 

to przejście przez wszystkie jego elementy wyglądałoby w następujący sposób:

preorder: * + 7 3 - 6 2 
postorder: 7 3 + 6 2 - * 
Inorder: 7 + 3 * 6 - 2 

Jak łatwo zauważyć dla drzew zawierających wyrażenia arytmetyczne poszczególne metody odwiedzania węzłów odpowiadają odpowiedniej notacji. Preorder to notacja prefiksowa (notacja polska), postorder to notacja postfiksowa (odwrotna notacja polska), a inorder to zwykła notacja infiksowa.

Poniżej trzy metody rekurencyjne realizujące poszczególne sposoby trawersowania drzewa (umieszczamy je w ciele klasy Tree<T> z poprzedniego postu).

/**
 * Metody trawersowania drzewa
 * @author kodatnik.blogspot.com 
 */ 

// metoda wyświetla węzły w kolejności preorder
public void preOrder(Node<T> n) {
 //najpierw korzeń
 System.out.print(n + " ");        
 // potem lewe skrajne poddrzewo, a później prawe
 Node<T> temp = n.getLeftMostChild();
 while (temp != null) {
  preOrder(temp);
  temp = temp.getRightSibling();
 }
}  
  
// metoda wyświetla węzły w kolejności postorder
public void postOrder(Node<T> n) {
 // najpierw lewe skrajne poddrzewo, potem prawe
 Node<T> temp = n.getLeftMostChild();
 while (temp != null) {
  postOrder(temp);
  temp = temp.getRightSibling();
 }
 // na końcu korzeń
 System.out.print(n + " ");
}  

// metoda wyświetla węzły w kolejności inorder
public void inOrder(Node<T> n) {
 if (n.isLeaf())
  System.out.print(n + " ");
 else {
  // najpierw lewe skrajne poddrzewo
  Node<T> temp = n.getLeftMostChild();
  inOrder(temp);
  // potem korzeń
  System.out.print(n + " ");  
  // potem prawe
  temp = temp.getRightSibling();   
  while (temp != null) {
   inOrder(temp);
   temp = temp.getRightSibling();
  }
 } 
}  

Mając już opanowane sposoby "chodzenia" po drzewie możemy zastanowić się nad prezentacją jego struktury na ekranie. To wszystko już w następnym poście.