как найти номер повторяющегося элемента в бинарном дереве поиска

Question

  public void duplicate()
    {
        int repeatation = 0;
        Node current = root;
        Node duplicate = root;
        while (current == null)
        {
            if (duplicate == current || duplicate == current.right  ||  duplicate== current.left)
            {
                Console.WriteLine("node is repeated :" + duplicate);
                repeatation++;



            }

        }
        Console.WriteLine("number of repeatation is :"  + repeatation);

    }

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

Answer 1

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

Answer 2

Вот подход, который может помочь вам с этой проблемой:

1) Получите максимальное значение в вашем BST (просто идите направо, направо, ..., прямо, пока не достигнете листа)

2) следуйте этому псевдокоду:

for i = 0 to MAX_VALUE do
  currentNode = root;
  while(TRUE)
      if (currentNode.Value == i)
           apprearanceCount++;
      if (i > currentNode.Value)
           currentNode = currentNode.RightNode;
      else 
           currentNode = currentNode.LeftNode;
      if currentNode == NULL then break; // Don't forget to save appearance count

Answer 3

Вы можете просто пройти свой BST, сохранив каждый элемент в хэш-карте вместе со счетчиком того, сколько раз вы встречали этот элемент.

После этого перебирайте вашу хэш-карту и выводите каждый элемент со счетчиком больше 1.

Сложность времени: O (n)