C++：计数在BST中的重复项

我有一个BST为;C++：计数在BST中的重复项

我有以下代码，以计算在这里应该是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);

来源

2013-07-24 Ali

大概将遍历结果存储在一个向量中，然后在向量中查找重复项，如果你不需要这样做到位？ – taocp

@taocp我刚刚编辑了这个问题。谢谢你的提示！ – Ali

您是否*不计算多重复数（即，如果您的树中有* 3 *'6'值，它是否被认为是“具有重复项的单个值”或者应该被视为两个“重复项”在现实中*三*，这是一个更难解决的问题）？ – WhozCraig

在二叉搜索树，这取决于刀片是怎么写的，重复的将永远是对的左侧或右侧，看起来像留在你的情况。所以你需要的只是一个额外的变量，用来跟踪这些愚蠢的计数，在你的函数中追踪最后访问的节点，如果当前节点与最后一次访问的节点相同，则增加计数。

下面是一些代码免责声明：没有经过测试才知道它编译

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

通过我感应这是接受记者采访时类型的问题，但托马斯·马修斯是正确的方式，你的树不应该重复插入。

来源

2013-07-24 17:48:20 aaronman

要么，或作业。可能是家庭作业，所以我选择不提供代码:) – AlexK

@AlexK我甚至不知道它是否工作我所知道的是它编译 – aaronman

@AlexK我也回答了像30分钟前，没有紫外线如此计算我'd发布一些代码 – aaronman

让我们假设你的BST中的副本只能在节点的左边（它总是同一边，我们只需要选择约定并坚持下去）。只需在递归遍历中递增重复计数，并且值不会更改。确保你通过引用计数，而不是按值计数。在开始之前将它清零。尼斯面试问题，顺便说一句

来源

2013-07-24 18:08:23 AlexK

OP永远不会回来 – aaronman

C++：计数在BST中的重复项

回答

相关问题