Traversare de ordine ulterioară pentru un arbore general (Programare, Java, Copac, Arbore Binar, Traversarea Arborelui, Postorder)

Mjall2 a intrebat.

Sunt în prezent un student a cărui temă de lucru implică adaptarea metodelor de arbore binar în metode de arbore general.Singura mea întrebare este dacă este corectă traversarea mea de ordin post pentru următorul arbore general?Dacă da, atunci știu că algoritmul meu funcționează, doar că nu reușesc să înțeleg corect traversarea de ordin post și m-am gândit că acest site ar putea ajuta.

                     B
--------------------|------------------
|                   |                 |
A             ------D-----         ---I---
             |      |    |        |       |
             C      E    G        H       L
                         |
                         F

Rezultatul meu este:A C E F F G D H L I B

2 răspunsuri
candied_orange

Răspunsul tău mi se pare corect.

Acest truc funcționează pentru arbori generalizați, nu doar pentru cei binari.

Urmează linia punctată și vizitează nodul atunci când găsești punctul negru.

Reutilizarea acestui grafic pentru traversarea preordinii este doar o chestiune de rotire a tuturor punctelor negre la 180 de grade. Traversarea în ordine ar fi de 90 de grade, dar este ambiguă dacă nu este vorba de un arbore binar.

A se vedea http://en.wikipedia.org/wiki/Tree_traversal

De la http://www.brpreiss.com/books/opus4/html/page259.html

parcurgerea în ordine inversă vizitează ultima rădăcină. Pentru a efectua o parcurgere postordine a unui arbore general:

Efectuați o parcurgere postordine a fiecăruia dintre subarborele rădăcinii, unul câte unul, în ordinea indicată; apoi vizitați rădăcina.

Comentarii

  • Rezultatul meu este A C E F G D H L I B Am făcut diagrama din post, nu am folosit diagrama wikipedia Mulțumesc pentru validarea răspunsului mulțumesc! –  > Por Mjall2.
murali krish

Tipărirea postorder poate fi făcută folosind recursivitatea. vă puteți vizualiza din funcția de recursivitate de mai jos. Nodul este tipărit după ce ambele funcții de mai sus sunt returnate funcției print(). Încercați să vă analizați manual pe hârtie arborele pe codul de mai jos și puteți constata că rezultatul este corect. Inițial, vizualizarea unei funcții de recursivitate ca aceasta ar fi dificilă, dar ar trebui să puteți vizualiza pentru a fi un programator bun, oricum încercați.

void postorder(node)
{
   if(node=NULL)
      return;
   postorder(node.left);
   postorder(node.right);
   print(node);
}