給定一個二叉搜索樹，找到ocurrences

的最大值的節點我有一個BST聲明如下：給定一個二叉搜索樹，找到ocurrences

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

來源

2013-10-17 Wyvern666

這真的不是一個難題，你有沒有試圖自己解決它？如果不是，爲什麼不呢？如果是這樣，你能向我們展示你的嘗試嗎？ – Dukeling

您可能想要指定樹的定義排序順序（數據與ocurr），因爲這會對如何執行此操作產生巨大影響。 – WhozCraig

@WhozCraig根據數據值依次插入節點。 – Wyvern666

看起來您基本上有正確的想法，您只需要另外比較兒童與當前節點的最大值（即比較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-17 15:23:11 Dukeling

你能解釋一下你在做什麼嗎？，我真的不在乎簡化代碼，我需要理解的是遞歸的東西。 – Wyvern666

@ Wyvern666向我的代碼添加了一些註釋。 – Dukeling

不錯。謝謝 – Wyvern666

假設data是樹的種類來看，沒有有效的算法。您必須通過所有節點進行徹底迭代才能找到最高值ocurr。任何全樹遍歷算法都可以工作（深度優先，寬度優先等）。

來源

2013-10-17 14:39:32

如果這是一個經常被訪問的問題，你可以「嵌入」另一個BST的數據的頻率。這需要兩個額外的鏈接區：

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

您還需要另一個指針「occurances」 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-17 17:12:55

給定一個二叉搜索樹，找到ocurrences

回答

相關問題