Προς το περιεχόμενο

Δυαδικα Δεντρα και αποριες....

simfonos

Από τον simfonos
στο Προγραμματισμός

Προτεινόμενες αναρτήσεις

simfonos Proficient

simfonos

Δημοσ.
Δημοσ.

ΟΙ αποριες μου εχουν να κανουν με τα δυαδικα δεντρα γενικοτερα...

 

Πως θα μπορεσω βημα βημα να μετατρεψω π.χ την λεξη Ο , Ρ , Ι , Α , Κ , Ε , Σ σε ενα δυαδικο δεντρο ?

 

Μια απορια επισης...

 

Πως θα μπορεσω βημα βημα να μετατρεψω αριθμητικες πραξεις σε ενα διαδικο δεντρο και να τοποθετηθουν στο δεντρο αυτο τελεστες και τελεστεοι ?

 

Π.Χ (( 5 + 34 ) / ( 12 * 34 )) - 5

V.I.Smirnov Experienced

V.I.Smirnov

Δημοσ.
Δημοσ.

Δεν είναι κάτι που να μπορεί να απαντηθεί εδώ.

 

Π.χ. για να μετατραπεί μια παράσταση πρέπει πρώτα να αναλυθεί το string που την περιέχει.

Η παράσταση εισάγεται ως string, μετατρέπεται σε μορφή reverse polish notation και μετά

εισάγονται οι αριθμοί και οι τελεστές στους κόμβους του δέντρου.

Κανείς δεν γράφει παραστάσεις σε μορφή reverse polish notation. Αυτό για να γίνει αυτόματα

(αλλά και για να εξάγονται τα στοιχεία του string) πρέπει να φτιάξεις parser - τρέχα γύρευε δηλαδή...

 

Όσο για το πώς τίθενται τα γράμματα στους κόμβους ενός δέντρου, δες το παρακάτω απόσπασμα :

 

 

>
/* 
   fragment example of an OOP implementation of Binary Tree.

        ------------------------------
           written by V.I.Smirnov 
        ------------------------------
*/

#include <stdio.h>
#include <stdlib.h>

typedef int  BOOLEAN;
const   int  ROOT        = 0;
const   int  LEFT_CHILD  = 1;
const   int  RIGHT_CHILD = 2;
const   int  PARENT      = 3;
typedef char DATA_TYPE;  


class Tree 
{
 public:
   virtual BOOLEAN   is_empty (void) = 0;
   virtual void      build_tree (DATA_TYPE A[]) = 0;
   virtual void      add_node(DATA_TYPE node_data) = 0;
   virtual void      print_tree(void) = 0;
};

                             
class Binary_Tree : public Tree {
 private:
   typedef struct BT_NODE 
   {
      DATA_TYPE   data;
      BT_NODE     *left_childptr;
      BT_NODE     *right_childptr;
   } *TREE_PTR;
   
   TREE_PTR  root_ptr; 
   TREE_PTR  curr_ptr;  
   void      init_btree() { root_ptr = NULL; 
                            curr_ptr = NULL; }

   TREE_PTR  add_node1( TREE_PTR  curr_ptr,
                        DATA_TYPE new_data
                        int       node_location);

   void      delete_btree (TREE_PTR tree_ptr);

   void      Preorder_(TREE_PTR tree_ptr);
   void      Postorder_(TREE_PTR tree_ptr);
   void      Inorder_(TREE_PTR tree_ptr);

 public:
   Binary_Tree() { init_btree(); }
   ~Binary_Tree();

   BOOLEAN   is_empty() {return (root_ptr == NULL);}
   void      build_tree(DATA_TYPE string[]);
   void      add_node(DATA_TYPE node_data);
   void      print_tree(void) { Intorder_(root_ptr);}

   void      Preorder(void) { Preorder_(root_ptr); }
   void      Postorder(void){ Postorder_(root_ptr); }
   void      Inorder(void)  { Intorder_(root_ptr); }
   TREE_PTR  get_root(void) { return root_ptr;     }
};


void  Binary_Tree::delete_btree (TREE_PTR tree_ptr)
{
  if (tree_ptr != NULL) 
  {
     delete_btree (tree_ptr->left_childptr);  
     delete_btree (tree_ptr->right_childptr);  
     delete  tree_ptr;       
  }
}


Binary_Tree::~Binary_Tree()
{ delete_btree (root_ptr); }  


Binary_Tree::TREE_PTR  Binary_Tree::
  add_node1( TREE_PTR  curr_ptr, 
             DATA_TYPE new_data, 
             int       node_location )
{
   TREE_PTR  new_ptr = new BT_NODE;
   new_ptr->data   = new_data;  
   new_ptr->left_childptr  = NULL;
   new_ptr->right_childptr = NULL;

   switch (node_location) 
   {
     case ROOT:     
       if (root_ptr == NULL) 
       {
          root_ptr = new_ptr;
          curr_ptr = new_ptr;
          return (new_ptr);
       }
     case LEFT_CHILD:   
       if (curr_ptr->left_childptr == NULL) 
       {
          curr_ptr->left_childptr = new_ptr;
          curr_ptr = new_ptr;
          return (new_ptr);
       }
     case RIGHT_CHILD:  
       if (curr_ptr->right_childptr == NULL) 
       {
          curr_ptr->right_childptr = new_ptr;
          curr_ptr = new_ptr;
          return (new_ptr);
       }
     case PARENT:       
          break;
     default:   
       printf("\n add_node1: Invalid node location \n");
       exit (-1);
    }
    delete  new_ptr; 
    printf("\n add_node1: Fails; Node with %c %s\n", 
            new_data, "exists, or wrong location");
    return (NULL); 
} 


void  Binary_Tree::add_node(DATA_TYPE node_data)
{
   TREE_PTR tmp_ptr;
   int      node_loc;

   printf("\nTo add node, enter node location\n%s",
    "(ROOT=0, LEFT_CHILD=1, RIGHT_CHILD=2, PARENT=3): ");
   scanf("%d", &node_loc);
   tmp_ptr = add_node1(curr_ptr, node_data, node_loc);
   if (tmp_ptr != NULL && is_empty()) 
   {
       root_ptr = tmp_ptr;
       curr_ptr = tmp_ptr;
   }
   else if (tmp_ptr != NULL && !is_empty())
       curr_ptr =  tmp_ptr;
}


void Binary_Tree::build_tree(DATA_TYPE string[])
{
   TREE_PTR  tmp_ptr;

   if ((tmp_ptr = add_node1(curr_ptr, 'Α', 
                            ROOT)) != NULL) {
       curr_ptr = tmp_ptr;
       root_ptr = tmp_ptr;
   }
   if ((tmp_ptr = add_node1(root_ptr, 'Β', 
                            LEFT_CHILD)) != NULL)
       curr_ptr =  tmp_ptr;
   if ((tmp_ptr = add_node1(root_ptr, 'C',
                            RIGHT_CHILD)) != NULL)
       curr_ptr =  tmp_ptr;
   if ((tmp_ptr = add_node1(curr_ptr, 'D',
                            LEFT_CHILD)) != NULL)
       curr_ptr =  tmp_ptr;
   if ((tmp_ptr = add_node1(curr_ptr, 'E',
                            RIGHT_CHILD)) != NULL)
       curr_ptr =  tmp_ptr;
   if ((tmp_ptr = add_node1(curr_ptr, 'F',
                            LEFT_CHILD)) != NULL)
       curr_ptr =  tmp_ptr;
   if ((tmp_ptr = add_node1(curr_ptr, 'G',
                            RIGHT_CHILD)) != NULL)
       curr_ptr =  tmp_ptr;
}



void  Binary_Tree::Preorder_(TREE_PTR tree_ptr)
{
   if (tree_ptr != NULL) 
   {
      printf(" %c ", tree_ptr->data);
      Preorder_(tree_ptr->left_childptr);
      Preorder_(tree_ptr->right_childptr);
   }
}


void  Binary_Tree::Postorder_(TREE_PTR tree_ptr)
{
   if (tree_ptr != NULL) {
      Postorder_(tree_ptr->left_childptr);
      Postorder_(tree_ptr->right_childptr);
      printf(" %c ", tree_ptr->data);
   }
} 


void  Binary_Tree::Intorder_(TREE_PTR tree_ptr)
{
   if (tree_ptr != NULL) 
   {
      Intorder_(tree_ptr->left_childptr);
      printf(" %c ", tree_ptr->data);
      Intorder_(tree_ptr->right_childptr);
   }
}


void main(void)
{
   Binary_Tree  btree_obj;   

   btree_obj.build_tree ("ABCDEFG");
 
   printf("\nBinary Tree after PreOrder traversal:\n");
   btree_obj.Preorder();

   printf("\nBinary Tree after PostOrder traversal:\n");
   btree_obj.Postorder();

   printf("\nBinary Tree after InOrder traversal:\n");
   btree_obj.Inorder();

   printf("\n");
}

 

-

MitsakosGR Proficient

MitsakosGR

Δημοσ.
Δημοσ.

ΟΙ αποριες μου εχουν να κανουν με τα δυαδικα δεντρα γενικοτερα...

 

Πως θα μπορεσω βημα βημα να μετατρεψω π.χ την λεξη Ο , Ρ , Ι , Α , Κ , Ε , Σ σε ενα δυαδικο δεντρο ?

 

Μια απορια επισης...

 

Πως θα μπορεσω βημα βημα να μετατρεψω αριθμητικες πραξεις σε ενα διαδικο δεντρο και να τοποθετηθουν στο δεντρο αυτο τελεστες και τελεστεοι ?

 

Π.Χ (( 5 + 34 ) / ( 12 * 34 )) - 5

 

Για να τοποθετήσεις συμβολοσειρά σε δυαδικό δέντρο υπάρχουν πολλοί τρόποι. Εξαρτάται τι είδους δέντρο θέλεις να είναι...(δυαδικό απλό, αναζήτησης, ισοζυγισμένο κτλ). Πιστεύω ότι ο V.I.Smirnov σου έδωσε αρκετά για να το φτιάξεις.

 

Για τις αριθμητικές πράξεις βρήκα αυτό το παράδειγμα που μπορεί να σε βοηθήσει. Ο πιο εύκολος τρόπος για να τα βάλεις στο δέντρο (όπως στο παράδειγμα) είναι να μετατρέψεις την αριθμητική παράσταση πρώτα σε Prefix (Polish Notation) και μετά να τα εισάγεις στο δέντρο.

simfonos Proficient

simfonos

Δημοσ.
  • Μέλος
Δημοσ.

Μιλαω αποκλειστικα και μονο για δυαδικο δεντρο αναζητησης( sorry δεν το ανεφερα ).

Το παραδειγμα με τον κωδικα δεν λεω ναι μεν καλο αλλο νομιζω οτι με απλα λογια ισως θα μπορουσατε να βοηθησετε.Θελω να πω δηλαδη να μου περιγραφατε την σκεψη σας οταν θα επρεπε να λυσετε ενα τετοιο προβλημα.Πιστευω πως η λυση του ειναι σχετικα απλη απλα σε εμενα κατι χανετε και δεν μπορω να καταλαβω για ποιο λογο εχει την μορφη του επισηναπτομενου αρχειου που ειναι η λυση...

Οσο για το link MitsakosGR πιστευω πως ειναι αρκετα δυνατο....

Επίσης να πω οτι δεν αναφερετε πουθενα ποια μεθοδος διασχισης θα πρεπεινα ακολουθησω.( προδιατεταγμενη , μεταδιατεταγμενη , ενδοδιατεταγμενη ... )

post-211418-0-24433700-1293665426_thumb.png

V.I.Smirnov Experienced

V.I.Smirnov

Δημοσ.
Δημοσ.

Από τον τρόπο που ρωτάς υποδηλώνεται ότι δεν έχεις μελετήσει την θεωρία.

 

Για το δεύτερο :

Η εισαγωγή μιας αλγεβρικής παράστασης σε δυαδικό δέντρο θα σε δυσκολέψει.

Η λύση του προβλήματος ΔΕΝ είναι απλή διότι οι λεπτομέρειες της υλοποίησης είναι πολλές και δύσκολες.

 

Η σκέψη για την λύση ήδη περιγράφηκε σε αδρές γραμμές.

Καταρχήν, τα δέντρα είναι απλώς δυαδικά και όχι δυαδικά αναζήτησης όπως λαθεμένα γράφεις (εδώ αυτό δεν έχει νόημα).

Εισάγεις την αλγεβρική παράσταση ως string. Το string υφίσταται επεξεργασία για να εξαχθούν οι αριθμοί και οι τελεστές.

Επιπλέον πρέπει να καθοριστεί με ποιά μορφή θα εισαχθεί στο δέντρο.

Eγώ είχα δει πώς γίνεται όταν η παράσταση δίνεται σε μορφή post-fixed.

Έστω π.χ. ότι η παράσταση είναι η A*(B+C). Η μορφή της σε post fixed είναι ΑΒC+* .

 

Να τα βήματα όταν κατά την σάρωση της παράστασης συναντάς ένα αριθμό Α :

- φτιάχνεις ένα δέντρο με έναν κόμβο που κρατά τον αριθμό Α

- αποθηκεύεις το δέντρο σε ένα stack

 

Να τα βήματα όταν κατά την σάρωση της παράστασης συναντάς έναν τελεστή :

- κάνεις pop από το stack τα δύο τελευταία δέντρα C και B.

- φτιάχνεις ένα νέο δέντρο X που έχει τον τελεστή στην ρίζα του

- θέτεις το δέντρο C δεξιά του X

- θέτεις το δέντρο Β αριστερά του X

- το νέο δέντρο που δημιουργήθηκε το αποθηκεύεις (push) στο stack

 

Όταν τελειώσει η σάρωση του post-fixed string, στο stack απομένει ένα δέντρο που αντιπροσωπεύει ολόκληρη την αλγεβρική παράσταση.

Αναλογα με το πώς το σαρώνεις (pre-, in- ή post- order), η αλγεβρική παράσταση αναπαράγεται σε pre-, in- ή post- fixed μορφή.

Για την αποτίμηση της παράστασης, η πιο βολική σάρωση του δέντρου είναι η pre- ή post- order διότι τότε η αναπαραγωγή της παράστασης είναι

σε μορφή pre- ή post- fixed η οποία κρατά την προτεραιότητα των πράξεων (δηλ. το αποτέλεσμα προκύπτει σωστό χωρίς να τεθούν οι παρενθέσεις !) .

(Ο MitsakosGR και εγώ ήδη αναφέραμε την prefix polish notation).

Όπως βλέπεις η λύση δεν είναι απλή : σάρωση και επεξεργασία string, δέντρα που αποθηκεύονται σε stacks κλπ.

 

 

Για το πρώτο :

Για την εισαγωγή των γραμμάτων ενός string σε δυαδικό δέντρο αναζήτησης είναι εύκολα τα πράγματα και γίνεται όπως οι αριθμοί.

Η μικρογραφία που επισυνάπτεις δείχνει αυτό που κάνω κι' εγώ στο παραπάνω απόσπασμα. Στο δικό μου παράδειγμα το δέντρο είναι απλό δυαδικό.

Αν στη μικρογραφία το δέντρο είναι απλό δυαδικό, είναι μεν σωστό αλλά τα γράμματα έχουν τεθεί στην τύχη (δεν αναπαράγεται η λέξη με σάρωση του δέντρου).

Αν όμως είναι δυαδικό αναζήτησης, είναι λαθεμένη διότι θα έπρεπε να είναι ταξινομημένα.

Προφανώς, επειδή τα γράμματα ταξινομούνται, ένα δ. δέντρο αναζήτησης έχει νόημα, ενώ για αριθμητικές παραστάσεις όχι.

Η σάρωση γίνεται ανάλογα με το πώς θέλεις να δεις τελικά το string.

 

-

simfonos Proficient

simfonos

Δημοσ.
  • Μέλος
Δημοσ.

 

Η σάρωση γίνεται ανάλογα με το πώς θέλεις να δεις τελικά το string.

 

 

Για το πρωτο

Εννοεις οτι θα πρεπει να επιλεγει καποια μεθοδος ? και αν ναι ποια ειδη μεθοδον μπορουν να εφαρμοστουν σε ενα τετοιο προβλημα?

 

Επειδη μου τη "ειπες" κι ολας να σου πω οτι τωρα αρχιζω να τα μαθαινω οποτε καλα κανεις και διορθωνεις...Αναλυτικος και περιγραφικος!!

V.I.Smirnov Experienced

V.I.Smirnov

Δημοσ.
Δημοσ.

Για το πρωτο

Εννοεις οτι θα πρεπει να επιλεγει καποια μεθοδος ? και αν ναι ποια ειδη μεθοδον μπορουν να εφαρμοστουν σε ενα τετοιο προβλημα?

 

Επειδη μου τη "ειπες" κι ολας να σου πω οτι τωρα αρχιζω να τα μαθαινω οποτε καλα κανεις και διορθωνεις...

Αναλυτικος και περιγραφικος!!

 

Ανάλογα με την σάρωση (pre-, in-, post order) αλλάζει η σειρά επισκεψιμότητας των κόμβων, άρα και της απεικόνισης των δεδομένων τους.

Τρέξε το παράδειγμα που έδωσα να δεις πώς φαίνεται το αποθηκευμένο string στις τρεις περιπτώσεις - φαίνεται καθαρά εκεί.

 

-

Αρχειοθετημένο

Αυτό το θέμα έχει αρχειοθετηθεί και είναι κλειστό για περαιτέρω απαντήσεις.

Προς την λίστα θεμάτων
  • Δημιουργία νέου...