0

我有一个这样声明的 BST：

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

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

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

编辑：我最后一次尝试：

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

3 回答 3

1

假设data是树的排序项，没有有效的算法。您必须对所有节点进行详尽的迭代才能找到 的最大值ocurr。任何全树遍历算法都可以工作（深度优先、广度优先等）。

于 2013-10-17T14:39:32.597 回答
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;
}
于 2013-10-17T15:23:11.907 回答
0

如果这是一个经常访问的问题，您可以为数据频率“嵌入”另一个 BST。这将需要两个额外的链接字段：

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

您还需要另一个指向“发生”BST 开头的指针：
nodeABB * occurance_bst;

另一种方法是让两个 BST 带有指向节点数据的指针和一个指向比较函数的指针：

struct data
{
  int data;
  int occurrences;
};

struct nodeABB; // forward declaration.
typedef bool (*Comparison_Function_Pointer)(nodeABB * a, nodeABB * b);
struct nodeABB
{
  data * p_data;
  nodeABB * left;
  nodeABB * right;
  Comparison_Function_Pointer compare_function;
};

该组织允许两个 BST，一个用于按数据排序；另一个用于按出现排序并为数据使用相同的结构。

两个 BST 代表相同数据的不同索引。

于 2013-10-17T17:12:55.790 回答