二叉搜索树索引 [英] binary search tree indexing

问题描述

我无法从特定索引处的二叉树中获取元素.我遇到问题的函数是通用 tree_get_at_index(tree_node* t, int index) {作业要求我在二叉树中的特定索引处找到元素.例如，0 索引应该返回二叉树中最低的元素，而 index = treesize 应该返回树中最大的元素.我的树中有一个大小函数，它可以正常工作，但由于某种原因我无法使索引正常工作.任何帮助，将不胜感激.谢谢

I am having trouble getting the element from the binary tree at a specific index. The function that i am having trouble with is generic tree_get_at_index(tree_node* t, int index) { The assignment asks me to find the element at a particular index in a binary tree. For example the 0 index should return the lowest element in the binary tree and the index = treesize should return the largest element in the tree. i have a size function in my tree which works correctly but i cannot get the indexing to work for some reason. any help would be appreciated. thank you

现在我在树运行一次后遇到段错误.

Right now i am getting seg fault after the tree runs once.

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

推荐答案

我们将尝试填充一个虚拟数组，因为你知道可以跳过索引的每个子树的大小

We will try filling a virtual array, as you know the size of each subtree you could skip the indexes

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

这篇关于二叉搜索树索引的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！