Метод Итератора для двоичного дерева в C

Question

Мне был предоставлен следующий код, чтобы сделать метод итератора для использования на двоичном дереве в C. Это значит применить функцию к каждому значению в двоичном дереве.

int bst_char_iterate(bst_char *t, char (*fun)(char item))

«Bst_char * т» приравнивания к указателю на дереве, «* забава» приравнивания к указателю на вызов функции и «элемент» является значением, которое функция вызывается после.

Я думал, что итераторы действительно должны выполняться как недействительные функции, поэтому я теряюсь относительно того, как подойти к этому.

Пожалуйста, помогите!

Edit: Команда у меня была следующая:

Добавить новый метод в библиотеку, которая применяет функцию к каждому значению в дереве. (Это метод итератора для деревьев.)

INT bst_char_iterate (bst_char * т, символ (* весело) (голец пункт))

NB: Свойство BST будет сохранен только этим методом, если переданная ему функция монотонна. Функция f является монотонной, когда

x < = y (стрелка) f (x) < = f (y).

Edit 2: Следующие не работает для меня:

int bst_char_iterate(bst_char *t, char (*fun)(char item)) { 
    assert(t!=NULL); 
    struct node * p = t->root; 
    if (p!=NULL) { 
     p->item = fun(p->item); 
     p->left->item = bst_char_iterate(t,fun(p->left)); 
     p->right->item = bst_char_iterate(t,fun(p->right)); 
    } else { 
     return 0; 
    } 
} 

С довольно много ошибок. Может ли кто-нибудь помочь?

Answer 1

Возможно, вам следует вернуть следующий элемент BST после данного элемента. Затем функция может быть вызвана снова с вновь возвращенным элементом, и она должна вернуть элемент после этого и так далее, пока вы не достигнете конца.

Поэтому вам нужно специальное значение, чтобы указать, что не осталось другого элемента; может быть 0?

Answer 2

Вы говорите, что хотите использовать метод «итератора», но затем вы описываете это как «применять функцию к каждому значению в дереве», что является методом «apply», а не «итератором». Метод итератора обычно ссылается на некоторый элемент структуры данных и возвращает ссылку на следующий элемент (или изменяет ссылку на место для ссылки на следующий элемент). Итак, вы хотите использовать настоящий метод итерации или хотите применить метод apply, который вы назовете «итерацией», таким образом запутав всех будущих читателей вашего кода?

Если последнее, вы хотите функцию, которая пересекает ваше дерево, вызывая функцию для каждого значения. Простой рекурсивный обход должен сделать трюк:

void bst_char_apply(bst_char *t, void (*fun)(char item)) { 
    if (t->left) bst_char_apply(t->left, fun); 
    fun(t->value); 
    if (t->right) bst_char_apply(t->right, fun); 
}