freestuff.gr αρχική σελίδα
 FAQFAQ    ΑναζήτησηΑναζήτηση   Λίστα ΜελώνΛίστα Μελών   Ομάδες ΜελώνΟμάδες Μελών   <b>Εγγραφή Μέλους</b>Εγγραφή Μέλους 
 ΠροφίλΠροφίλ   Επιλογές μέλους Επιλογές   Τα bookmarks μου Τα bookmarks μου   Προσωπικά μηνύματαΠροσωπικά μηνύματα 
  διαφήμιση  

Καλώς ήρθατε στο forum μας! Για να συμμετάσχετε στις συζητήσεις θα πρέπει να είσαστε μέλος. Γίνετε μέλος τώρα!.

δυαδικά δέντρα αναζήτησης


 Forum index » Δημιουργία Web Sites, Γραφικών & Προγραμματισμός » Γλώσσες Προγραμματισμού » C, C++
Moderators:  Super-Moderators, WebDev Moderators
Εισαγωγή νέου Θέματος   Απάντηση στο Θέμα Σελίδα 1 από 1 [2 Μηνύματα]      Bookmarks Tags: δέντρααναζήτησης Mark the topic unread :: Προηγούμενο θέμα :: Επόμενο θέμα
ΑποστολέαςΜήνυμα
koszerb


Μέλος από: 22 Νοε 2008
Μηνύματα: 8

View users profile
ΜήνυμαΣτις: 16 Δεκ 2008 18:20    Θέμα: δυαδικά δέντρα αναζήτησης
Περιγραφή θέματος: δυαδικά δέντρα αναζήτησης και διπλά συνδεδεμένες λίστες
Απάντηση με παράθεση  Mark this post and the followings unread

Καλησπέρα!
Θα ήθελα τη βοήθειά σας σε ένα θέμα που αντιμετωπίζω.
Το γενικότερο πρόβλημα είναι η διαχείριση αρχείων εικόνων μέσω δυαδικών δέντρων αναζήτησης και διπλά συνδεδεμένης λίστας.
Οι δομές ορίζονται ως εξής:
κώδικας:

// Double-linked list node definition. Multiple loaded images are stored in such lists
typedef struct image_entry
{
    IMAGE *image;
    char name[255];
    int changed;
    struct image_entry *next;
    struct image_entry *previous;
} IMAGE_ENTRY;

// A Binary Search Tree node, in order to index the images
typedef struct node
{
    IMAGE_ENTRY *image_entry;
    struct node *parent;
    struct node *left;
    struct node *right;
} NODE;


Το αρχείο bst.h είναι το παρακάτω:
κώδικας:

#ifndef BST_H
#define BST_H
#include "def.h"

NODE *bst_insert(NODE* root, IMAGE_ENTRY *image_entry);
NODE* bst_next(NODE *n);
NODE* bst_delete(NODE* root, NODE *n);
NODE *bst_find(NODE* root, char name[]);
void traverse_bst_az(NODE* n);
void traverse_bst_za(NODE* n);

#endif


έχουν ήδη οριστεί κάποιες από αυτές τις συναρτήσεις:
κώδικας:

NODE *bst_insert(NODE* root, IMAGE_ENTRY *image_entry)
{
    // Creating a new node...
    NODE *new_node=(NODE*) malloc(sizeof(NODE));
    if (new_node==NULL)
    {
        printf("Cannot create new BST entry. Unsufficient memory.\n"); return NULL;
    }
    // ... and initializing its fields
    new_node->parent=NULL;
    new_node->left=NULL;
    new_node->right=NULL;
    new_node->image_entry=image_entry;

    // Inserting the new node into the BST
    if (root==NULL)    root=new_node;
    else
    {
        NODE *current=root, *previous=NULL;
        while (current!=NULL)
        {
            previous=current;
            if (strcmp(current->image_entry->name, new_node->image_entry->name)<0)
                current=current->right;
            else
                current=current->left;
        }
        if (strcmp(previous->image_entry->name, new_node->image_entry->name)<0)
            previous->right=new_node;
        else
            previous->left=new_node;
        new_node->parent=previous;
    }
    return root;
}

και
κώδικας:

NODE *bst_find(NODE* root, char name[])
{
    if (root==NULL) { return NULL; }
    else
    {
        NODE *current=root;
        while (current!=NULL)
        {
            if (strcmp(current->image_entry->name,name)==0) { return current;}
            else if (strcmp(current->image_entry->name,name)<0) { current=current->right;   }
            else { current=current->left;   }
        }
    }
    return NULL;
}


εγώ έγραψα τις υπόλοιπες συναρτήσεις ως εξής:

κώδικας:

/* traverse the BST index in inorder way (αλφαβητικά)
 * Input: NODE *n : The root of the BST index,  the names of which will be displayed in inorder way.
 * Output:  No return  */

void traverse_bst_az(NODE* n)
{
   if(n==NULL) return;

   traverse_bst_az(n->left);
   printf("%d, ",n->image_entry);
   traverse_bst_az(n->right);
}
/**************************************/
/* ανάποδα αλφαβητικά */
void traverse_bst_za(NODE* n)
{
   if(n==NULL) return;

   traverse_bst_az(n->right);
   printf("%d, ",n->image_entry);
   traverse_bst_az(n->left);
}
/**************************************/
/* Given a node of the BST, this function returns its next one (according to the index key).
 * Input: NODE* n - A node of the BST
 * Output: NODE*  - Pointer to the next node  */

NODE* bst_next(NODE *n)
{
   NODE *next;
   if(n==NULL) return NULL;

   if(n->right != NULL)
      {
      next=n->right;
      while (next->left != NULL)
         next=next->left;
      }
   else
      {
      next=n;
      while (next->parent != NULL && next==next->parent->right)
         {
         next=next->parent;
         }
      next=next->parent;
      }
   return next;
}

/**************************************/
/ * delete an existing node from a BST and returns the new root.
 * Inputs:
 *    NODE* root: The root of the BST
 *    NODE *n: The node to be deleted
 * Output:  NODE*  -  The new root of the BST   */

NODE* bst_delete(NODE* root, NODE *n)
{
   if (root != NULL) return NULL;
   NODE *child=NULL;

   if(n->left==NULL || n->right==NULL)
   {
      if(n->left !=NULL) child=n->left;
      else if(n->right != NULL) child=n->right;
      free (n->image_entry);

      if(n->parent != NULL)
      {
         if(n==n->parent->left) n->parent->left=child;
         else n->parent->right=child;
      }
      else
      {   root=child;      }

      if (child !=NULL) child->parent=n->parent;
      free (n);
   }
   else //the node has two children
   {
      NODE *next;
      void *temp;

      next=n->right;
      while(next->left != NULL)
         next=next->left;

      temp=n->image_entry;
      n->image_entry=next->image_entry;
      next->image_entry=temp;

      bst_delete(root, next);
   }
   return root;
}


Χρειάζομαι τη βοήθειά σας για να μου πείτε αν έχω κάποιο λάθος στις 4 αυτές συναρτήσεις, και τι πρέπει να διορθώσω, ώστε να μπορέσω να προχωρήσω στα επόμενα βήματα του θέματος. Χωρίς την ολοκλήρωση του BST δεν μπορώ να κάνω τίποτα παρακάτω.
Με προβληματίζει ιδιαίτερα η συνάρτηση διαγραφής κόμβου. Πώς θα μπορούσα να τη γράψω καλύτερα; Θα μπορούσα ίσως να χρησιμοποιήσω για τη διαγραφή τη συνάρτηση του διαδόχου;;; Πώς;;;

Ευχαριστώ ιδιαιτέρως!
tix-3-


Μέλος από: 25 Μαρ 2004
Βοηθήματα: 1
Scripts: 1
Μηνύματα: 256+

Περιοχή: Θεσσαλονικη-Καβαλα-βεροια(το τριγωνο της καταρας)
View users profile Visit posters website
ΜήνυμαΣτις: 17 Δεκ 2008 14:16    Θέμα: Απάντηση με παράθεση  Mark this post and the followings unread

Χωρις να ειμαι σιγουρος γιατι περασαν και 3 χρονια.
Το πιο απλο που μπορεις να κανεις ειναι:
Βαζεις σε ενα node *next το επομενο απο το bst_next(n);
Και περνεις περιπτώσεις.
Αν ειναι leaf το κανεις απλα free
Αν εχει ενα παιδι μετακινεις το παιδι πανω και θετεις το parent του παιδιου ισο με το parent του n.
Αν εχει δυο παιδια δεν θυμαμαι τι πρεπει να κανεις οποτε θα περιμενεις να παω σπιτι για να διαβασω καποιο απο τα βιβλια μου Καλό ε! .
Το βασικο που πρεπει να εχεις στο νου σου ειναι οτι με την διαγραφη μπορει να χαλασεις το balance του tree οποτε να εχεις το νου σου.
Περισσοτερα το βραδακι που θα ειμαι σπιτι και θα μπορω να γραψω και λιγο κωδικα

_________________
Αν δεν υπήρχανε οι κνίτες κι'η ηρωίνη...
Εμφάνιση Μηνυμάτων:   
Εισαγωγή νέου Θέματος   Απάντηση στο Θέμα Σελίδα 1 από 1 [2 Μηνύματα] Mark the topic unread :: Προηγούμενο θέμα :: Επόμενο θέμα
 Forum index » Δημιουργία Web Sites, Γραφικών & Προγραμματισμός » Γλώσσες Προγραμματισμού » C, C++


Σχετικά θέματα
 Θέματα   Απ/σεις   Αποστολέας   Τελευταίο μήνυμα 
Πώς τα πάμε από λίστες??SOS 1 karetta_seaworld 23 Ιουλ 2015 10:12
gvre Εμφάνιση τελευταίου μηνύματος
 
Τώρα είναι 08 Δεκ 2016 09:52 | All times are UTC + 2


Email This Page to Someone! add to Favorites

     Powered by p h p B B © 2001,2005 p h p B B Group
Για άμεση επικοινωνία με τον διαχειριστή του freestuff.gr στο email: freestuff.gr(παπάκι)gmail.com


Copyright © 1999-2013 Freestuff.gr All Rights Reserved  
Version Aegean, designed by N. Tsaganos