Η σελίδα μας αναβαθμίστηκε, γι' αυτό τον λόγο τα μέλη μας θα πρέπει να ζητήσουν νέο κωδικό πρόσβασης από την υπηρεσία "Αποστολή κωδικού πρόσβασης".
Εάν το email με τον νέο κωδικό δεν έρθει στο inbox κοιτάξτε και στο spam folder. Ο server είναι φρέσκος και δεν έχει το reputation που του αξίζει.

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

Συζητήσεις για την γλώσσα C και C++

Συντονιστές: WebDev Moderators, Super-Moderators

Απάντηση
koszerb
Δημοσιεύσεις: 8
Εγγραφή: 22 Νοέμ 2008 17:51

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

Δημοσίευση από koszerb » 16 Δεκ 2008 18:20

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

Κώδικας: Επιλογή όλων

// 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 &#40;strcmp&#40;current->image_entry->name, new_node->image_entry->name&#41;<0&#41;
                current=current->right;
            else
                current=current->left;
        &#125;
        if &#40;strcmp&#40;previous->image_entry->name, new_node->image_entry->name&#41;<0&#41;
            previous->right=new_node;
        else
            previous->left=new_node;
        new_node->parent=previous;
    &#125;
    return root;
&#125;
και

Κώδικας: Επιλογή όλων

NODE *bst_find&#40;NODE* root, char name&#91;&#93;&#41;
&#123;
    if &#40;root==NULL&#41; &#123; return NULL; &#125;
    else
    &#123;
        NODE *current=root;
        while &#40;current!=NULL&#41;
        &#123;
            if &#40;strcmp&#40;current->image_entry->name,name&#41;==0&#41; &#123; return current;&#125;
            else if &#40;strcmp&#40;current->image_entry->name,name&#41;<0&#41; &#123; current=current->right;   &#125;
            else &#123; current=current->left;	&#125;
        &#125;
    &#125;
    return NULL;
&#125;
εγώ έγραψα τις υπόλοιπες συναρτήσεις ως εξής:

Κώδικας: Επιλογή όλων

/* traverse the BST index in inorder way &#40;αλφαβητικά&#41;
 * Input&#58; NODE *n &#58; The root of the BST index,  the names of which will be displayed in inorder way.
 * Output&#58;  No return  */

void traverse_bst_az&#40;NODE* n&#41;
&#123;
	if&#40;n==NULL&#41; return;

	traverse_bst_az&#40;n->left&#41;;
	printf&#40;"%d, ",n->image_entry&#41;;
	traverse_bst_az&#40;n->right&#41;;
&#125;
/**************************************/
/* ανάποδα αλφαβητικά */
void traverse_bst_za&#40;NODE* n&#41;
&#123;
	if&#40;n==NULL&#41; return;

	traverse_bst_az&#40;n->right&#41;;
	printf&#40;"%d, ",n->image_entry&#41;;
	traverse_bst_az&#40;n->left&#41;;
&#125;
/**************************************/
/* Given a node of the BST, this function returns its next one &#40;according to the index key&#41;.
 * Input&#58; NODE* n - A node of the BST
 * Output&#58; NODE*  - Pointer to the next node  */

NODE* bst_next&#40;NODE *n&#41;
&#123;
	NODE *next;
	if&#40;n==NULL&#41; return NULL;

	if&#40;n->right != NULL&#41;
		&#123;
		next=n->right;
		while &#40;next->left != NULL&#41;
			next=next->left;
		&#125;
	else
		&#123;
		next=n;
		while &#40;next->parent != NULL && next==next->parent->right&#41;
			&#123;
			next=next->parent;
			&#125;
		next=next->parent;
		&#125;
	return next;
&#125;

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

NODE* bst_delete&#40;NODE* root, NODE *n&#41;
&#123;
	if &#40;root != NULL&#41; return NULL;
	NODE *child=NULL;

	if&#40;n->left==NULL || n->right==NULL&#41;
	&#123;
		if&#40;n->left !=NULL&#41; child=n->left;
		else if&#40;n->right != NULL&#41; child=n->right;
		free &#40;n->image_entry&#41;;

		if&#40;n->parent != NULL&#41;
		&#123;
			if&#40;n==n->parent->left&#41; n->parent->left=child;
			else n->parent->right=child;
		&#125;
		else
		&#123;	root=child;		&#125;

		if &#40;child !=NULL&#41; child->parent=n->parent;
		free &#40;n&#41;;
	&#125;
	else //the node has two children
	&#123;
		NODE *next;
		void *temp;

		next=n->right;
		while&#40;next->left != NULL&#41;
			next=next->left;

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

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

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

Άβαταρ μέλους
tix-3-
Δημοσιεύσεις: 827
Εγγραφή: 25 Μαρ 2004 05:12
Τοποθεσία: Θεσσαλονικη-Καβαλα-βεροια(το τριγωνο της καταρας)
Επικοινωνία:

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

Δημοσίευση από tix-3- » 17 Δεκ 2008 14:16

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

Απάντηση

Επιστροφή στο “C, C++”

Μέλη σε σύνδεση

Μέλη σε αυτήν τη Δ. Συζήτηση: Δεν υπάρχουν εγγεγραμμένα μέλη και 1 επισκέπτης