C++: подсчет дубликатов в BST

У меня есть BST as;

    8
   / \
  4  12
   \
    6
   /
   6

У меня есть следующий код, чтобы рассчитать количество дубликатов, которое здесь должно быть 1 (6 имеет дубликат);

struct Node
{
    int data;
    Node *left, *right;
};


void inorder(Node *root, Node *previous, int count)
{
    if(root != NULL)
    {
        if(root != previous && root->data == previous->data)
            count++;
        previous = root;
        inorder(root->left, previous, count);
        cout<<root->data<<" ";
        inorder(root->right, previous, count);
    }
}

Я должен сделать это, используя постоянное дополнительное пространство.Я знаю, что это далеко не так, но идея, которую я имею, состоит в том, чтобы отслеживать предыдущий узел и проверять наличие дубликатов, а в конце возвращать количество. Но мне не удалось вернуть целочисленное значение при выполнении по порядку обхода BST. Кроме того, был бы лучший способ подсчета дубликатов в BST. я инициирую;

inorder(a, a, 0);

c++ recursion algorithm traversal binary-search-tree
person Ali    schedule 24.07.2013    source источник
comment
Вероятно, хранить результаты обхода в векторе, а затем находить дубликаты в векторе, если от вас не требуется делать это на месте?   -  person taocp    schedule 24.07.2013
comment
@taocp Я только что отредактировал вопрос. Спасибо за чаевые!   -  person Ali    schedule 24.07.2013
comment
Вы не считаете несколько дубликатов (т. е. если у вас есть три значения 6 в дереве, предполагается ли, что оно считается одним значением с дубликатами или должно считаться двумя? дубликаты (а на самом деле три, что гораздо сложнее решить)?   -  person WhozCraig    schedule 24.07.2013
comment
Почему ваш BST допускает дублирование?   -  person Thomas Matthews    schedule 24.07.2013
comment
@Ali Я отредактировал вашу проблему, чтобы использовать постоянное дополнительное пространство, это правильная терминология для того, что вы хотите.   -  person aaronman    schedule 24.07.2013

Ответы (2)


arrow_upward
1
arrow_downward

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

Вот некоторый код Отказ от ответственности, полностью непроверенный, просто знайте, что он компилируется

int count_dupes(Node * root, Node * last = nullptr) {
    int is_dupe = 0;
    if (root->value == last->value) is_dupe = 1;
    return is_dupe + (root->right != nullptr? count_dupes(root->right,root):0)
        + (root->left!= nullptr? count_dupes(root->left,root):0);
}

Кстати, я чувствую, что это вопрос типа интервью, но Томас Мэтьюз прав, в вашем дереве не должно быть вставленных дубликатов.

person aaronman    schedule 24.07.2013
comment
Либо это, либо домашнее задание. Вероятно, домашнее задание, поэтому я решил не предоставлять код :) - person AlexK; 24.07.2013
comment
@AlexK Я даже не знаю, работает ли это, все, что я знаю, это компилируется - person aaronman; 24.07.2013
comment
@AlexK также я ответил около 30 минут назад, и никаких UV, поэтому я решил опубликовать код - person aaronman; 24.07.2013
comment
Мне кажется, что сравнение root-›value == last-›value в строке 2, когда last отправляется как nullptr, вызовет ошибку seg... - person confundido; 05.06.2020

arrow_upward
1
arrow_downward

Предположим, в вашем BST дубликат может быть только слева от узла (это всегда одна и та же сторона, нам просто нужно выбрать соглашение и придерживаться его). Просто увеличивайте количество дубликатов по мере того, как вы рекурсируете влево в своем обходе по порядку, и значение не меняется. Убедитесь, что вы передаете count по ссылке, а не по значению. Обнулите его перед запуском. Хороший вопрос для интервью, кстати

person AlexK    schedule 24.07.2013
comment
ОП так и не вернулся - person aaronman; 25.07.2013