У меня возникли проблемы с получением элемента из двоичного дерева по определенному индексу. Функция, с которой у меня возникают проблемы, является generic tree_get_at_index (tree_node * t, int index) { Уступка просит меня найти элемент по определенному индексу в двоичном дереве. Например, индекс 0 должен возвращать наименьший элемент в двоичном дереве, а index = treeize должен возвращать наибольший элемент в дереве. У меня есть функция размера в моем дереве, которая работает правильно, но я не могу заставить индексирование работать по какой-то причине. любая помощь будет оценена по достоинству. спасибоиндексация двоичного дерева поиска
Прямо сейчас я получаю 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. Здесь я помещаю здесь все двоичное дерево. моя проблема связана с последней функцией кода. он ничего не возвращает, это просто seg faults, когда я пытаюсь запустить тесты на нем. Я уверен, что мои другие функции работают –