как реализовать функцию фильтра с O (n) и O (1) пробелом в бинарном дереве поиска - PullRequest
Новая
       0

как реализовать функцию фильтра с O (n) и O (1) пробелом в бинарном дереве поиска

0 голосов
/ 19 октября 2019

У меня есть бинарное дерево поиска, у каждого узла есть указатель на lChild и rChild. Теперь я хочу реализовать функцию: Filter: удаляет все узлы, которые не имеют желаемого свойства, оставляя только те, у которых есть свойство. Это должно быть O (n). Обеспечить эффективную реализацию памяти, т. Е. Пространство O (1).

Как я должен это сделать?

Как я знаю, использование рекурсии для реализации фильтра является неправильным способом. 

struct Node 
{
    Node *lChild;
    Node *rChild;
    int data;
};

void filter(function<bool (const int)> isIn)
{
} //TODO O(n)running time O(1)space
...