二分查找樹索引

Question

我無法從特定索引處的二叉樹獲取元素。我有問題的函數是通用的tree_get_at_index（tree_node * t，int index）{ 該作業要求我在二叉樹的特定索引處查找元素。例如，0索引應返回二叉樹中最低的元素，index = treesize應返回樹中最大的元素。我在我的樹中有一個尺寸函數，它能正常工作，但我無法使索引因某些原因而工作。任何幫助，將不勝感激。謝謝

現在我在樹運行一次後就出現seg錯誤。

#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 */ 

Answer 1

我們將努力填補虛擬陣列，你知道每個子樹的大小，你可以跳過指標

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); 
} 

Answer 2

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; 

}