Die letzten 5 Beiträge |
Shizmo |
Okay super, vielen Dank!!!
|
eulerscheZahl |
Stimmt, das letzte Beispiel ist auch falsch. |
Shizmo |
Vielen Dank für deine Antwort.
Also könnte man damit argumentieren, dass wenn es ein Kind ohne Nachfolger (mit Ausnahme der 363) gibt, die Suchsequenz nicht richtig sein kann?
Dann sollte aber das letzte Beispiel auch falsch sein:
code: |
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
|
935
/
278
\
347
/ \
299 621
/
392
/
358
\
363 |
|
LG |
eulerscheZahl |
code: |
1:
|
925, 202, 911, 240, 912, 245, 363 |
|
von der 911 geht es nach links. Also können nur noch Werte gefunden werden, die kleiner als 911 sind. 912 darf nicht vorkommen.
Das passt auch nicht: 500, 250, 499, 12, 300, 370, 363 |
Shizmo |
Suche in einem binären Suchbaum
Hallo, ich steh grad auf dem Schlauch:
Zitat: |
Angenommen es werden die Zahlen von 1 bis 1000 in einem binären Suchbaum verwaltet. Darin soll die Zahl 363 gesucht werden. Welche der folgenden Sequenzen kann nicht aus dem zuvor beschriebenen Baum beim Suchen entstanden sein? Begründen Sie ihre Antwort.
- 2, 252, 401, 398, 330, 344, 397, 363
- 924, 220, 911, 244, 898, 258, 362, 363
- 2, 399, 387, 219, 266, 382, 381, 278, 363
- 925, 202, 911, 240, 912, 245, 363
- 500, 250, 499, 12, 300, 370, 363
- 935, 278, 347, 621, 299, 392, 358, 363
|
Hmm, also ich weiß was ein binärer Suchbaum ist, zB Beispiel1, wenn die Zahlen 2, 252, 401, 398, 330, 344, 397, 363 so eingefügt werden und danach die übrigen Zahlen von 1-1000, dann würde das in etwa so ausschauen:
code: |
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
|
2
\
252
\
401
/
398
/
330
\
344
\
397
/
363 |
|
So und jetzt noch die übrigen Zahlen von 1-1000.
Die Eigenschaften vom Suchbaum sind nicht verletzt und die Suche kann auch ganz normal stattfinden bis ich zum Element 363 komme.
Der Pseudocode von Baumsuche(x,k) schaut nämlich so aus:
code: |
1:
2:
3:
4:
5:
6:
7:
|
if x==Nil or k==x.key
return x
if k<x.kex
return Baumsuche(x.left,k)
else
return Baumsuche(x.right,k) |
|
Und irgendwie schaut es bei den anderen Beispielen nicht anders aus.
Meine Strategie geht nicht auf irgendwo hab ich einen Denkfehler
LG |
|
|