Upload
vachel
View
37
Download
0
Embed Size (px)
DESCRIPTION
bp. b. 5 l r. 2 l r. 8 l r. Vorbereitung:. struct knoten { int x; struct knoten *l, *r; } *b, *bh, **bp;. b: Zeiger auf Wurzel bh: Hilfszeiger bp: Zeiger auf Zeiger auf knoten. - PowerPoint PPT Presentation
Citation preview
Vorbereitung:
struct knoten { int x; struct knoten *l, *r; } *b, *bh, **bp;
b: Zeiger auf Wurzel
bh: Hilfszeiger
bp: Zeiger auf Zeiger auf knoten
bbp 5 l r
2 l r 8 l r
int einf(struct knoten *b, struct knoten *bh, int y) { struct knoten *bvor; int k; while(b) { if (b x == y) return 1; bvor = b; if (b x > y) { k = -1; b = b l;} else { k = 1; b = b r;} } if (k == -1) bvor l = bh; else bvor r = bh; bh x = y; bh l=0; bh r=0; return 0; }
b 5 l r
2 l r 8 l r
Einfügen von 3:
einf(b, bh, 3);
bh ? ? ?
bvor = b;
bvor
5 > 3, daher k=-1, b umgelegt auf 2
b 5 l r
2 l r 8 l r
Einfügen von 3:
einf(b, bh, 3);
bh ? ? ?
bvor = b;
bvor
5 > 3, daher k=-1, b umgelegt auf 2
bvor = b;
b 5 l r
2 l r 8 l r
Einfügen von 3:
einf(b, bh, 3);
bh ? ? ?
bvor = b;
bvor
5 > 3, daher k=-1, b umgelegt auf 2
bvor = b;
2 < 3, daher k=1, b umgelegt auf NULL
b 5 l r
2 l r 8 l r
Einfügen von 3:
einf(b, bh, 3);
bh ? ? ?
bvor = b;
bvor
5 > 3, daher k=-1, b umgelegt auf 2
bvor = b;
2 < 3, daher k=1, b umgelegt auf NULL
While zu Ende
b 5 l r
2 l r 8 l r
Einfügen von 3:
einf(b, bh, 3);
bh ? ? ?
bvor
While zu Ende, k=1
bvor r = bh
b 5 l r
2 l r 8 l r
Einfügen von 3:
einf(b, bh, 3);
bh ? ? ?
bvor
While zu Ende, k=1
bvor r = bh
Daten setzen in bh:
b 5 l r
2 l r 8 l r
Einfügen von 3:
einf(b, bh, 3);
bh 3 l r
bvor
While zu Ende, k=1
bvor r = bh
Daten setzen in bh:
int insert(struct knoten **bp, int y) { while(*bp) { if ((*bp) x == y) return 1; if ((*bp) x > y) bp = &( ( *bp ) l ); else bp = &( ( *bp) r ); } *bp = (struct knoten *)malloc(sizeof(struct knoten)); if (*bp == 0) return 2; (*bp) x = y; (*bp) l = 0; (*bp) r = 0; return 0; }
Einfügen von 3:
insert(bp, 3);
b 5 l r
2 l r 8 l r
bp 5 > 3, *bp umgelegt auf linken Zeiger bei 5
b 5 l r
2 l r 8 l r
Einfügen von 3:
insert(bp, 3);
bp 5 > 3, *bp umgelegt auf linken Zeiger bei 5
2 < 3, *bp umgelegt auf rechten Zeiger bei 2
b 5 l r
2 l r 8 l r
Einfügen von 3:
insert(bp, 3);
bp 5 > 3, *bp umgelegt auf linken Zeiger bei 5
2 < 3, *bp umgelegt auf rechten Zeiger bei 2
*bp ist NULL, Daher wird nun eingefügt.
Schaffe neuen Knotenund lege *bp auf diesen
? ? ?
b 5 l r
2 l r 8 l r
Einfügen von 3:
insert(bp, 3);
bp 5 > 3, *bp umgelegt auf linken Zeiger bei 5
2 < 3, *bp umgelegt auf rechten Zeiger bei 2
*bp ist NULL, Daher wird nun eingefügt.
Schaffe neuen Knoten bhund lege *bp auf bh
3 l r
b 5 l r
2 l r 8 l r
Einfügen von 3:
insert(bp, 3);
Ergebnisbaum
3 l r