c++ - 给定一棵二叉搜索树，找到出现次数最多的节点

Question

我有一个这样声明的 BST:

struct nodeABB {
   int data;
   int ocurr;
   nodeABB *left;
   nodeABB *right;
};

“ocurr”值保存相同数据在树中插入的次数。

我需要一个递归算法来找到具有最大“ocurr”值的节点，如果有两个具有相同值的节点，我的想法是返回具有最大数据的那个。

编辑:Mi 最后一次尝试:

trypedef nodeABB* ABB;
ABB Max(ABB a) {
ABB ret = NULL;
  if (!a) 
    return ret;

ABB a1 = Max(a->left);
ABB a2 = Max(a->right);

if (a1 && a2) {
    int n1 = a1->ocurr;
    int n2 = a2->ocurr;
    if (n1 > n2) 
        ret = a1;
    else if (n1 < n2)
        ret = a2;
    else
        ret = (a1->data < a2->data ? a1 : a2);
} else if (!a1 && a2)
     ret = a2;
else if (a1 && !a2)
    ret = a1;

return ret;
}

Answer 1

看起来你的想法基本上是正确的，你只需要额外比较子节点的最大值和当前节点(即比较ret和a)。

您的功能也可以稍微简化，这是我的做法:

ABB Max(ABB a) {
  // if the current node is NULL, just return NULL
  if (a == NULL)
    return NULL;

  // find the maximums in the left and right subtrees
  ABB a1 = Max(a->left);
  ABB a2 = Max(a->right);

  // make the current node the maximum
  ABB maxN = a;

  // if the current node has a left child and...
  if (a1 != NULL &&
  // the maximum in the left child's subtree > the current maximum or...
      (a1->ocurr > maxN->ocurr ||
  // the maximums are equal and the left subtree's maximum node's bigger
       (a1->ocurr == maxN->ocurr && a1->data > maxN->data)))
  {
    // set the new maximum to be the left subtree's maximum node
    maxN = a1;
  }

  // if the current node has a right child and...
  if (a2 != NULL &&
  // the maximum in the right child's subtree > the current maximum or...
      (a2->ocurr > maxN->ocurr ||
  // the maximums are equal and the right subtree's maximum node's bigger
       (a2->ocurr == maxN->ocurr && a2->data > maxN->data)))
  {
    // set the new maximum to be the right subtree's maximum node
    maxN = a2;
  }

  // return the maximum
  return maxN;
}