9.  Stromy

9.3  Prehľadávanie binárneho stromu

So stromami môžeme vykonávať rôzne operácie, napr.: vytvorenie prázdneho stromu, pridanie nového vrcholu (ako syna určeného vrcholu), odstránenie určeného vrcholu, presun ukazovateľa na syna daného vrcholu (toho, ktorý vyhovuje nejakej podmienke) resp. presun ukazovateľa na otca a pod.

Za základnú operáciu sa však považuje prehľadávanie stromu (pohyb po strome). Vzhľadom na to, že strom je výhodne definovaný ako rekurzívna údajová štruktúra, aj na prehľadávanie sa využívajú rekurzívne metódy.

Pre binárne stromy sú to tri základné rekurzívne metódy:

• priame prehľadávanie - PREORDER
  Strom sa prehľadáva v poradí: koreň, ľavý podstrom, pravý podstrom (KLP)

  void preorder(TVrchol *koren)   
  {
     if (koren != NULL) {
       printf("%d", koren->hodnota);
       preorder(koren->ls); 
       preorder(koren->ps);
     }
  }

  ---

• stredové prehľadávanie - INORDER
  Strom sa prehľadáva v poradí: ľavý podstrom, koreň, pravý podstrom (LKP)

  void inorder(TVrchol *koren)   
  {
     if (koren != NULL) {
       inorder(koren->ls);
       printf("%d", koren->hodnota); 
       inorder(koren->ps);
     }
  }

  ---

• Spätné prehľadávanie - POSTORDER
  Strom sa prehľadáva v poradí: ľavý podstrom, pravý podstrom, koreň (LPK)

  void postorder(TVrchol *koren)   
  {
     if (koren != NULL) {
       postorder(koren->ls);
       postorder(koren->ps);
       printf("%d", koren->hodnota);      
     }
  }

  Pre binárny strom na obrázku, dostaneme použitím jednotlivých metód tieto rôzne výsledky:

preorder(strom);       OBRÁZOK KLP : 1, 2, 4, 5, 3, 6, 8, 7 inorder(strom); LKP : 4, 2, 5, 1, 6, 8, 3, 7 postorder(strom); LPK : 4, 5, 2, 8, 6, 7, 3, 1

  Pri prehľadávaní stromu samozrejme nemusíme vždy len vypisovať hodnoty vrcholov na obrazovku. Postupujeme takto vždy, keď chceme na vrcholoch stromu (či už všetkých, alebo len tých, ktoré vyhovujú určenej podmienke) vykonať nejakú operáciu. Alebo strom prehľadávame len preto, aby sme zistili, či sa príslušný vrchol v strome nachádza alebo nie.