Műhold

Utasítások

Képzeld el, hogy egy bináris fát kell átküldened egy műholdra, amely az Alpha Centauri felé közeledik, és korlátozott a sávszélességed. Mivel a fában nincsenek ismétlődő elemek, egyértelműen reprezentálható a preorder és inorder bejárásaival.

Írd meg a szoftvert a műholdnak, hogy a bejárásokból újraépítse a fát.

A preorder bejárás előbb beolvassa az aktuális csúcs értékét, mielőtt a bal részfát preorder módon bejárná (innen a „pre” elnevezés). Ezután a jobb részfa preorder bejárása következik.

Az inorder bejárás először a bal részfát járja be inorder módon, majd az aktuális csúcsot olvassa be, végül pedig a jobb részfát is inorder módon. Tehát balról jobbra haladva.

Például ennek a fának a preorder bejárása: [a, i, x, f, r]. Az inorder bejárása pedig: [i, a, f, x, r]

  a
 / \
i   x
   / \
  f   r

Megjegyzés: a preorder bejárás első eleme mindig a gyökér.