2016-07-29 9 views
-1

Ich habe Probleme, das Element aus dem Binärbaum bei einem bestimmten Index zu bekommen. Die Funktion, mit der ich Probleme habe, ist generic tree_get_at_index (tree_node * t, int index) { Die Zuweisung fordert mich auf, das Element an einem bestimmten Index in einem Binärbaum zu finden. Zum Beispiel sollte der 0-Index das niedrigste Element im Binärbaum und der Index = treesize das größte Element in der Struktur zurückgeben. Ich habe eine Größenfunktion in meinem Baum, die richtig funktioniert, aber ich kann die Indizierung aus irgendeinem Grund nicht funktionieren. jede Hilfe würde geschätzt werden. dankebinäre Suchbaum Indizierung

Gerade jetzt bekomme ich seg Fehler, nachdem der Baum einmal läuft.

#include "tree.h" 

#include <stdbool.h> 
#include <stdlib.h> 
#include <assert.h> 
#include <string.h> 
#include <stdio.h> 
    /* Memory Management */ 

/* This constructor returns a pointer to a new tree node that contains the 
* given element.*/ 
tree_node* new_tree_node(generic e) { 
    /*TODO: Complete this function!*/ 
    tree_node* to_return = malloc(sizeof(tree_node)); 
    to_return->element = e; 
    to_return->left = NULL; 
    to_return->right = NULL; 
    return to_return; 
} 

/* This function is expected to free the memory associated with a node and all 
* of its descendants.*/ 
void free_tree(tree_node* t) { 
    /*TODO: Complete this function!*/ 
    if (t != NULL){ 
     free_tree(t->left); 
     free_tree(t->right); 
     free(t); 
    } 
} 
    /* End Memory Management */ 




    /* Tree Storage and Access */ 


bool tree_contains(tree_node* t, generic e) { 
    /*TODO: Complete this function!*/ 
    /* 
    if (t == NULL || t->element != e) { 
     return false; 
    } 
    else if (t->element == e) { 
     return true; 
    } 
    return tree_contains(t,e); 
} 
*/ 
    if(t == NULL) 
     return false; 
    else if(t->element == e) 
     return true; 
    else if (e<t->element) 
     return tree_contains(t->left,e); 
    else 
     return tree_contains(t->right,e); 

} 


tree_node* tree_add(tree_node* t, generic e) { 
    /*TODO: Complete this function!*/ 

    if(t==NULL) 
    t = new_tree_node(e); 
    else if(e == t->element) 
     return t; 
    else if(e > (t->element)) 
     { 
      t->right = tree_add(t->right,e); 
     } 
    else if(e < (t->element)) 
     { 
      t->left = tree_add(t->left,e); 
     } 
    return t; 
} 

tree_node* tree_remove(tree_node* t, generic e) { 
    /*TODO: Complete this function!*/ 
    if (t == NULL) return t; 

    else if (e < t->element) 
     t->left = tree_remove(t->left, e); 
    else if (e > t->element) 
     t->right = tree_remove(t->right, e); 

    else 
    { 
     if (t->left == NULL) 
     { 
      tree_node *temp = t->right; 
      free(t); 
      return temp; 
     } 
     else if (t->right == NULL) 
     { 
      tree_node *temp = t->left; 
      free(t); 
      return temp; 
     } 
    else { 
      tree_node* current = t->right; 
      tree_node* temp = t->right; 

     while (current->left != NULL) 
      current = current->left; 
     t->element = current->element; 
     while (temp->left->left != NULL) 
      temp = temp->left; 
     temp->left = current->right; 
     free(current); 

    } 
    } 
    return t; 
} 
    /* End Tree Storage and Access */ 




    /* Size and Index */ 

/* Return the size of the tree rooted at the given node. 
* The size of a tree is the number of nodes it contains. 
* This function should work on subtrees, not just the root. 
* If t is NULL, it is to be treated as an empty tree and you should 
* return 0. 
* A single node is a tree of size 1.*/ 
int tree_size(tree_node* t) { 
    /*TODO: Complete this function!*/ 
    if (t==NULL) 
     return 0; 
    else  
     return(tree_size(t->left) + 1 + tree_size(t->right)); 
} 

/* Return the element at the given index in the given tree. 
* To be clear, imagine the tree is a sorted array, and you are 
* to return the element at the given index. 
* 
* Assume indexing is zero based; if index is zero then the minimum 
* element should be returned, for example. If index is one then 
* the second smallest element should bereturned, and so on.*/ 
generic tree_get_at_index(tree_node* t, int index) { 
    //assert(index >=0 && index < tree_size(t)); 
    /*TODO: Complete this function!*/ 
    //tree_node* new_node = t; 
// int min = 0; 
// int max = tree_size(t); 
// int current = (min+max)/2; 
int current = index; 
printf("tree size: %d \n", tree_size(t)); 

    //while(new_node != NULL){ 
     if(current == (tree_size(t)-1)){ 
      return t->element; 
      printf("index = tree size \n"); 
     } 

     else if(index < (tree_size(t->left))){ 
      //current--; 
     return tree_get_at_index(t->left, index); 
     printf("index < tree size \n");  //= new_node->right; 
     } 

     else if(index > (tree_size(t->left))){ 
     return tree_get_at_index(t->right, index); 
     printf("index > tree size \n"); 
     } 
     return t->element; 
    //return (generic)0; 

} 
    /* End Size and Index */ 
+0

Bitte beschreiben Sie Ihr Problem besser als „Ich kann nicht es funktioniert aus irgendeinem Grund ". Bitte geben Sie eine [mcve], Testeingabe, erwartetes Verhalten und tatsächliches Verhalten an. Überprüfen Sie [Wie stelle ich eine gute Frage?] (Http://stackoverflow.com/help/how-to-ask), um weitere Anleitungen zur Verbesserung Ihrer Frage zu erhalten. – kaylum

+0

Wie wurde Ihr Binärbaum aufgebaut? es könnte viel helfen mit einer Antwort – dvhh

+0

@dvhh ich legte den gesamten Binärbaum hier. Mein Problem ist mit der letzten Funktion des Codes. es gibt nichts zurück, es segelt nur Fehler, wenn ich versuche, Tests darauf durchzuführen. Ich bin mir ziemlich sicher, dass meine anderen Funktionen funktionieren –

Antwort

0

Wir werden versuchen, eine virtuelle Array füllen, wie Sie die Größe der einzelnen Teilstruktur kennen Sie könnten die Indizes überspringen

generic tree_get_at_index(tree_node* t, int index) { 
    // sanity check 
    assert(t); 
    assert(index > 0); 

    int leftCount=tree_size(t->left); 
    if(index < leftCount) { 
     // good chance that the node we seek is in the left children 
     return tree_get_at_index(t->left, index); 
    } 
    if(index==leftCount) { 
     // looking at the "middle" of the sub tree 
     return t->element; 
    } 
    // else look at the right sub tree as it was its own array 
    return tree_get_at_index(t->right, index - leftCount - 1); 
} 
+0

Es funktionierte perfekt. Danke soooooooo viel !!!! Ich fragte mich, ob ich am Ende etwas wie index-leftCount-1 machen musste, aber ich habe die 1 weggelassen, so dass ich Seg-Fehler bekam. DANKE SIR @dvhh! Schätze es wirklich! –

+0

Zwischen nur neugierig, wie wussten Sie, dass wir 1 von Index abziehen mussten - links zählen? –

+0

auf dem aktuellen Knoten, wenn Sie auf der rechten Teilbaum suchen, bedeutet das, dass Sie die linke Unterstruktur Anzahl der Knoten ('- leftCount') plus den aktuellen Knoten überspringen, die Sie betrachten (daher die' - 1'). – dvhh

0
generic tree_get_at_index(tree_node* t, int index) { 
assert(index >=0 && index <= tree_size(t));//I don't know how you define the tree_size function,but,according to the "if" below,you need to add equal mark 
printf("tree size: %d \n", tree_size(t)); 

//while(new_node != NULL){ 
    if(index == tree_size(t)){ 
     return t->element; 
    } 

    else if(index <= tree_size(t->left)){//I think you miss the equal situation here 
     //current--; 
    return tree_get_at_index(t->left, index); //= new_node->right; 
    } 

    else /*if(index > tree_size(t->left))*/{//do not need any condition here 
    return tree_get_at_index(t->right, index); 
    } 
// return t->element; //unnecessary 
//return (generic)0; 

} 
+0

danke Ich habe es versucht, aber es seg Fehler, wenn ich versuche Index –

Verwandte Themen