如何在二叉搜索树中找到重复元素的数量

本文关键字：元素 搜索树 | 更新日期: 2023-09-27 18:16:50

  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);
    }

这个代码是重复的元素在二叉搜索树和多少时间一个元素重复，但它不能正常工作，你能告诉我这段代码有什么问题，我不确定我的代码是否正确......

如何在二叉搜索树中找到重复元素的数量

如果你InOrder遍历树，你会得到重复的元素在一起，所以你只需要检查一个值等于前一个值，以及这种情况发生了多少次

这里有一个方法可以帮助您解决这个问题:

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

你可以只遍历BST一次，保存哈希映射中的每个元素以及一个计数器，显示你遇到该元素的次数。

之后，遍历哈希映射并输出计数器大于1的所有元素。

时间复杂度:O(n)

相关文章：