我无法从特定索引处的二叉树获取元素。我有问题的函数是通用的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 */
请说明您的具体问题,不是“我不能得到更好的它出于某种原因工作“。请提供[mcve],测试输入,预期行为和实际行为。回顾[我如何问一个好问题?](http://stackoverflow.com/help/how-to-ask)以获取有关如何改进问题的更多指导。 – kaylum
你的二叉树是如何构建的?它可以帮助我做出回答 – dvhh
@dvhh我把整个二叉树放在这里。我的问题是代码的最后一个功能。它不会返回任何内容,它只是在我尝试对其运行测试时发生故障。我很确定我的其他功能正在工作 –