Sökträd

TRÄDBYGGEN¶


* Insättning av 4 2 1 6 3 7 5 ger trädet

4 2 6 1 3 5 7 Binärt sökträd: ja Balanserat: ja

Insättning av 5 7 3 6 1 4 2 ger trädet

5 3 7 1 4 6 2 Binärt sökträd: jaBalanserat: ja

¶
* POSTORDERTRÄD
* Skriv ut något av träden i inordning och bygg upp ett nytt träd från denna talföljd.
* Skriv sedan ut dom i preordning och bygg upp nya träd från dessa talföljder.
* Skriv slutligen ut dom i postorder och bygg upp nya träd från dessa talföljder.

Inordning + nybygge

Båda träden ger 1 2 3 4 5 6 7 8 i inordning Nya trädet bli en tarm, ytterst obalanserat.

1 2 3 4 5 6 7 Preordning + nybygge Första trädet i preordning ger 4 2 1 3 6 5 7 och nytt träd blir

4 2 6 1 3 5 7 (samma som ursprungsträdet)

Andra trädet i preorder ger 5 3 1 2 4 7 6 och nytt träd blir

5 3 7 1 4 6 2 (samma som ursprungsträdet)

Postorder + nybygge

Första trädet i postorder ger 1 3 2 5 7 6 4 och nytt träd blir

1 3 2 5 4 7 6 Andra trädet i postorder ger 2 1 4 3 6 7 5 och nytt träd blir

2 1 4 3 6 5 7