Jämför preorder, inorder, postorder och nivåordning

Trädtraversering bestämmer när en nod besöks, inte hur trädet lagras. Preorder, inorder och postorder är vanliga djupet-först-varianter för binära träd. Nivåordning är bredden-först.

Samma träd, fyra resultat

Exemplet har roten A, barnen B, C och löven D, E, F, G.

Metod	Regel	Resultat
Preorder	Rot, Vänster, Höger	A B D E C F G
Inorder	Vänster, Rot, Höger	D B E A F C G
Postorder	Vänster, Höger, Rot	D E B F G C A
Nivåordning (BFS)	Kö, grundare nivåer först	A B C D E F G

Besöksordning hittills: –

Rekursionsstack: –

FöregåendeNästa stegBörja om

Försök förutsäga nästa nod innan du trycker på Nästa steg. Inorder är definierat för träd med vänster och höger barn.

Varför spelar ordningen roll?

Preorder behandlar föräldern före efterkommande och passar för serialisering och prefixnotation. Inorder ger sorterade nycklar bara om trädet följer ett binärt sökträds sorteringsregler. Postorder behandlar barnen före föräldern, till exempel vid utvärdering eller borttagning av delträd. Nivåordning går brett fram och passar när närmaste noder på träddjup ska undersökas först.

I ett generellt träd med flera barn fungerar preorder och postorder om barnens ordning är definierad. Inorder kräver däremot en avgränsning mellan vänster och höger och har ingen universell definition för godtyckligt antal barn.

Tid och minne

Alla fyra besöker n noder en gång: O(n) tid. Rekursiv DFS använder O(h) stackutrymme för höjd h. Nivåordning kräver en kö med upp till O(w) noder för maximal bredd w. Att lagra hela besöksordningen kräver O(n), oavsett metod.

Öva: Förutsäg resultaten om A har ett vänsterbarn B men inget högerbarn. Prova sedan samma idé i visualiseringen och fundera över vad som händer för ett kedjeformat träd.

Referenser: GeeksforGeeks-jämförelse, W3Schools traversal.