Treesort

Thomas Wöhlke

Treesort

Problem: Sortieren einer Liste - Liste hat unbekannte Länge- Liste ist kein Array

Beispiel: Doppelt Zeiger-verkettete Liste

Lösung: Sortieren mit Treesort

Treesort

Algorithmus:

Phase 1: Aufbau eines Binär-Baumes aus denElementen der Liste.

Phase 2: Traversieren (inorder) des Baumes unddabei Neu-Aufbau der Liste.

=> Liste ist sortiert.

Phase 1: Binär-Baum aufbauen

DC F A G X V K

Baum aufbauen

DC F A G X V K

C

Baum aufbauen

DC F A G X V K

CF

Baum aufbauen

DC F A G X V K

CFA

Baum aufbauen

DC F A G X V K

CFA

G

Baum aufbauen

DC F A G X V K

CFA

GD

Baum aufbauen

DC F A G X V K

CFA

GDX

Baum aufbauen

DC F A G X V K

CFA

GDX

V

Baum aufbauen

DC F A G X V K

CFA

GDX

VK

Phase 2: Traversieren

A

CFA

GDX

VK

1

Phase 2: Traversieren

CA

CFA

GDX

VK

1

2

Phase 2: Traversieren

DCA

CFA

GDX

VK

1

3

2

Phase 2: Traversieren

DC FA

CFA

GDX

VK

1

3

4

2

Phase 2: Traversieren

DC FA G

CFA

GDX

VK

1

3

4

2

5

Phase 2: Traversieren

DC FA G K

CFA

GDX

VK

1

3

4

2

6

5

Phase 2: Traversieren

DC FA G VK

CFA

GDX

VK

1

3

4

2

7

6

5

Phase 2: Traversieren

DC FA G XVK

CFA

GDX

VK

1

3

4

2

7

6

5

8

Treesort

Thomas Wöhlke