konsolacja Temat założony przez niniejszego użytkownika |
[C] BST teksty, co w sytuacji, kiedy mamy dwóch synów w funkcji usuwającej? » 2016-09-19 11:21:03 Witajcie mam problem z drzewem BST z tekstami, jestem w trakcie tworzenia w funckji usuwajacej, w sytuacji gdy mamy dwóch synów. Pomożecie? #include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct Node {
struct Node * left;
struct Node * right;
char * value;
} Node;
Node * NewNode( const char * text ) {
Node * newNode =( Node * ) malloc( sizeof( Node ) );
newNode->value = text;
newNode->left = NULL;
newNode->right = NULL;
return newNode;
}
Node * root;
void add( const char * text )
{
printf( "Dodawanie %s\n", text );
Node * lastNode = root;
Node * currentNode = root;
int b;
while( currentNode != NULL ) {
printf( "porownywanie %s z %s\n", currentNode->value, text );
lastNode = currentNode;
if( stricmp( currentNode->value, text ) > 0 ) {
b = 1;
printf( "lewo > prawo\n" );
currentNode = currentNode->left;
}
else {
b = - 1;
printf( "lewo < prawo\n" );
currentNode = currentNode->right;
}
}
printf( "Dodawanie nowego elementu: Sukces\n\n" );
Node * newNode = NewNode( text );
currentNode = newNode;
if( b == 1 ) {
lastNode->left = newNode;
}
else {
lastNode->right = newNode;
}
}
void print( Node * x )
{
if( x->left != NULL ) print( x->left );
printf( "%s \n", x->value );
if( x->right != NULL ) print( x->right );
}
Node * tree_minumum( Node * x )
{
while( x->left != NULL )
{
x = x->left;
}
return x;
}
void delete( const char * text )
{
Node * currentNode = root;
Node * lastNode = root;
while( currentNode != NULL )
{
if( stricmp( currentNode->value, text ) == 0 )
{
if(( currentNode->left == NULL ) &&( currentNode->right == NULL ) )
{
if( stricmp( currentNode->value, lastNode->value ) < 0 )
lastNode->left = NULL;
else
lastNode->right = NULL;
free( currentNode );
return;
}
if(( currentNode->left == NULL ) && currentNode->right != NULL )
{
if( stricmp( currentNode->value, lastNode->value ) > 0 )
lastNode->right = currentNode->right;
else lastNode->left = currentNode->right;
free( currentNode );
return;
}
if(( currentNode->left != NULL ) && currentNode->right == NULL )
{
if( stricmp( currentNode->value, lastNode->value ) > 0 )
lastNode->right = currentNode->left;
else lastNode->left = currentNode->left;
free( currentNode );
return;
}
if(( currentNode->left != NULL ) && currentNode->right != NULL )
{
}
}
lastNode = currentNode;
if( stricmp( currentNode->value, text ) < 0 )
{
currentNode = currentNode->right;
}
else
currentNode = currentNode->left;
}
}
char * min()
{
Node * currentNode = root;
while( currentNode->left != NULL )
{
currentNode = currentNode->left;
}
return currentNode->value;
}
int contains( const char * text )
{
Node * currentNode = root;
while( currentNode != NULL )
{
if( stricmp( currentNode->value, text ) == 0 ) return 1;
if( stricmp( currentNode->value, text ) < 0 )
{
currentNode = currentNode->right;
}
else
currentNode = currentNode->left;
}
return 0;
}
int main()
{
root = NewNode( "abx" );
add( "abcd" );
printf( "Metoda inorder \n" );
print( root );
printf( "element najmniejszy: %s\n", min() );
printf( "\n" );
delete( "abcd" );
print( root );
return 0;
}
|
|
pekfos |
» 2016-09-19 12:30:30 Wstaw w ten węzeł wartość następnika i usuń węzeł, z którego tą wartość wziąłeś. |
|
konsolacja Temat założony przez niniejszego użytkownika |
A mogę Cie prosić? » 2016-09-19 16:11:02 Siema, dzięki za pomoc, a miałbyś chwile czasu by mi to napisać? Główkuję nad tym i nie mogę tego rozgryźć.. a potrzebuję na zaliczenie ćwiczeń, tylko ta jedna modyfikacja :( |
|
pekfos |
» 2016-09-19 16:17:41 Nie. |
|
mateczek |
» 2016-09-19 16:25:20 przecież skoro jedziesz od dołu to nie może być sytuacji że masz i po prawej i po lewej obiekt do usunięcia. więc nie bardzo rozumiem o co chodzi z tym "dwóch synów" |
|
konsolacja Temat założony przez niniejszego użytkownika |
» 2016-09-19 16:25:36 :( @up Następniki, jest po prostu tak w algorytmie, że jezeli element usuwany ma po sobie dzieci po lewej i prawej stronie to usuwa się w bardziej skomplikowany sposób. "Usuwanie elementów: Jeżeli usuwany element nie ma następników to można zwolnić przydzieloną mu pamięć. Jeśli element do usunięcia ma jeden następnik należy go połączyć (następnik) z poprzednikiem usuwanego elementu. Jeśli element ma dwa następniki można go usunąć na dwa sposoby: połączyć poprzednik elementu z wierzchołkiem o najmniejszej wartości z prawego poddrzewa usuwanego połączyć poprzednik elementu z wierzchołkiem o największej wartości z lewego poddrzewa " mam jeszcze ze stronki http://www.algolist.net/Data_structures/Binary_search_tree/Removal cos takiego, ale to jest w C++ bool BinarySearchTree::remove( int value ) {
if( root == NULL )
return false;
else {
if( root->getValue() == value ) {
BSTNode auxRoot( 0 );
auxRoot.setLeftChild( root );
BSTNode * removedNode = root->remove( value, & auxRoot );
root = auxRoot.getLeft();
if( removedNode != NULL ) {
delete removedNode;
return true;
} else
return false;
} else {
BSTNode * removedNode = root->remove( value, NULL );
if( removedNode != NULL ) {
delete removedNode;
return true;
} else
return false;
}
}
}
BSTNode * BSTNode::remove( int value, BSTNode * parent ) {
if( value < this->value ) {
if( left != NULL )
return left->remove( value, this );
else
return NULL;
} else if( value > this->value ) {
if( right != NULL )
return right->remove( value, this );
else
return NULL;
} else {
if( left != NULL && right != NULL ) {
this->value = right->minValue();
return right->remove( this->value, this );
} else if( parent->left == this ) {
parent->left =( left != NULL ) ? left
: right;
return this;
} else if( parent->right == this ) {
parent->right =( left != NULL ) ? left
: right;
return this;
}
}
}
int BSTNode::minValue() {
if( left == NULL )
return value;
else
return left->minValue();
} |
|
mateczek |
» 2016-09-19 17:02:36 sorki ubzdurałem sobie, że to zwykła lista dwukierunkowa. więc pytanie co chcesz zrobić z gałęziami
/c /d
A--B
\e
po usunięciu elementu "B" element "A" powinien mieć 3 odnogi !!!! w takiej koncepcji moim zdaniem nie możliwe !! to samo poniżej gdy chcesz wyalić element B pierwszy z listy !!!
/d
B
\e
|
|
konsolacja Temat założony przez niniejszego użytkownika |
» 2016-09-19 18:07:55 takie miałem polecenie:
Zaimplementuj drzewo wyszukiwań binarnych dla tekstów.
Węzeł drzewa może mieć postać:
typedef struct Node {
struct Node* left;
struct Node* right;
char* value;
} node;
Zaimplementuj metody (1 pkt za każdą):
void add(const char* text) - dodającą węzeł o zadanej wartości do drzewa
void delete(const char* text) - usuwającą węzeł o zadanej wartości z drzewa
void print() - wypisującą wszystkie wartości dodane do drzewa w porządku leksykograficznym
int contains(const char* text) - zwracającą 1 jeśli wartość jest w drzewie, 0 w p.p.
char* min() - zwracającą najmniejszy leksykograficznie element drzewa
algorytm mi każe takie metody usuwania robić,
bo gdy dodaje elementy i usuwam
root = NewNode("e");
add("b");
add("a");
add("c");
add("z");
add("u");
add("w");
delete("b");
delete("z");
to wyskakuje mi tak:
a b c e u w z
a po usuwaniu
a b c e u w
b się nie kasuje, to jest problem, bo jest w wyzej w drzewie i nie udaje się
|
|
| « 1 » 2 |