|
TwojePC.pl © 2001 - 2024
|
 |
A R C H I W A L N A W I A D O M O Ś Ć |
 |
| |
|
[C] Problem z kodem (drzewko BST) , Adamusss 6/11/06 00:10
Witam
Mam problem z napisaniem kodu drzewa BST - ponizej ten kod
#include <stdio.h>
#include <stdlib.h>
struct wezel {
int key;
struct wezel *parent;
struct wezel *left;
struct wezel *right;
};
struct wezel *tree_insert(struct wezel *root, int key);
void print_preorder(struct wezel *root);
void print_inorder(struct wezel *root);
void print_postorder(struct wezel *root);
void usun(struct wezel *w);
int i,wybor;
int values[10];
struct wezel *root = NULL;
int main()
{
system("clear");
while(wybor!=5)
{
printf("\nBST\n\n 1. Dodaj liczby\n 2. Wyswietl liczby metoda preorder\n 3. Wyswietl liczby metoda inorder\n 4. Usun liczbe \n 5. Zakoncz program\n\n Wybierz opcje: \n");
scanf("%d",&wybor);
switch(wybor)
{
case 1:
scanf("%d",&values[0]);
scanf("%d",&values[1]);
scanf("%d",&values[2]);
scanf("%d",&values[3]);
scanf("%d",&values[4]);
scanf("%d",&values[5]);
scanf("%d",&values[6]);
scanf("%d",&values[7]);
scanf("%d",&values[8]);
scanf("%d",&values[9]);
for(i = 0; i < 10; i++)
{
root = tree_insert(root, values[i]);
}
break;
case 2:
printf("Preorder: ");
print_preorder(root);
break;
case 3:
printf("Inorder: ");
print_inorder(root);
break;
case 4:
printf("usuwanie");
usun(w); //JAK ZAIMPLEMENTOWAC FUNKCJE USUN W MAIN ?
break;
}
}
return 0;
}
struct wezel *tree_insert(struct wezel *root, int key)
{
struct wezel *walker = root;
struct wezel *new, *parent = NULL;
new = malloc(sizeof(struct wezel));
new->key = key;
new->left = new->right = NULL;
while (walker != NULL) {
parent = walker;
if (key < walker->key) {
walker = walker->left;
} else {
walker = walker->right;
}
}
if (parent) {
if (new->key < parent->key) {
parent->left = new;
} else {
parent->right = new;
}
} else {
root = new;
}
return root;
}
void print_preorder(struct wezel *root)
{
if(root) {
printf("%d, ", root->key);
print_preorder(root->left);
print_preorder(root->right);
}
}
void print_inorder(struct wezel *root)
{
if(root) {
print_inorder(root->left);
printf("%d, ", root->key);
print_inorder(root->right);
}
}
void usun(struct wezel *w)
{
if(w=w->parent->left) w->parent->left;
if(w=w->parent->right) w->parent->right;
usun(w->left);
usun(w->right);
free(w);
}
Pytania:
1. Jak zaimplementowac funkcje usun? tj. jak sprawic aby dzialala, z jakim parametrem ja wywolywac ? ;) chodzi mi o to ze po podaniu liczby np 4 liczba ta zostala wykasowana z drzewa........ scanf("%d",jakas_liczba); usun(jakas_liczba);
2. Radzono mi abym przy tworzeniu danego potomka ustawił mu wskaznik do rodzica - w ktorym miejscu dokladnie umiescic ten wskaznik (tak powinne wygladac te wskazniki ? parent *left, parent *right ?) ?
pytania sa prawdopodobnie banalne, ale dla mnie - totalne laika w C - sa kosmiczne ;)
z gory dziekuje za kazda ewentualna pomoc :)
pozdrawiam
Adam- ten tego rekordowo dlugi post :) , biEski 6/11/06 01:06
co do pytania 1 to sam sobie odpowiedziales jak chcesz cos usunac to musisz wiedziec co:>
a pozatym to
http://pl.wikipedia.org/...szukiwa%C5%84_binarnych
http://www.michalszkutnik.one.pl/cplusplus/
a najelpiej to
http://www.google.pl/search?q=drzewo+BST - re... , Umek 7/11/06 20:40
1. znaleźć węzeł idąc po drzewie (szukaj) i wywołać jego usunięcie korzystając juz z jego wskaźnika (usuń)
2. wskaźnik rodzic jest w celu uproszczenia implementacji (masz porządek (ułatwienie) - czyli z węzła możliwość dostania się w każdą stronę - potomkowie (L,P)+rodzic).
O ile pamietam - usuwanie czasem wiązało się z lokalną przebudową drzewa, tylko czy to dotyczy BST - niestety nie pamiętam. Poczytaj sobie...
|
|
|
|
 |
All rights reserved ® Copyright and Design 2001-2024, TwojePC.PL |
 |
|
|
|
