我有一个这样声明的 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;
}
最佳答案
看起来你的想法基本上是正确的,你只需要额外比较子节点的最大值和当前节点(即比较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;
}
关于c++ - 给定一棵二叉搜索树,找到出现次数最多的节点,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/19429510/