Как найти все узлы с одинаковым значением дерева - PullRequest
Новая
       69

Как найти все узлы с одинаковым значением дерева

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

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

Я создал две функции unordered_set и key_set (), которые обходят все узлы в дереве и рекурсивно добавляют id в unordered_set. 

template <class T, class K>
class Node
{
public:
    Color color = BLACK; //color
    T id; //key
    K value = NULL; //value
    K pom;
    int p;
    int max;
    int sum;
    Node* parent; //parent
    Node* left; //left child
    Node* right; //right child
}

template <class T, class K>
void RBTree<T, K>::key_set(unordered_set<T> lower_set, unordered_set<T> higher_set, Node<T, K>* node, K value)
{
    if ((node->value != NULL))
    {
        if (node->value <= value && node->p == 1)
            lower_set.insert(node->id);
        else if (node->value >= value && node->p == -1)
            higher_set.insert(node->id);
        key_set(lower_set, higher_set, node->left, value);
        key_set(lower_set, higher_set, node->right, value);
    }
}

Я думаю, что из-за области действия или других причин, наборы всегда будут иметь размер, равный нулю, который должен иметь такой же размер, как и максимум корневого узла.

...