C++查找最大數目

號碼的二進制樹中，與節點結構C++查找最大數目

type def numbernode 
{ 
    unsigned value; 
    numbernode * left; 
    numbernode * right; 
}

和外部指針（根節點）在最大（numbernode *樹）寫的函數將如果樹不爲空，則返回樹中最大的數字。如果樹是空的，你的函數應該返回-1。

其測試練習題，我花了幾個小時試圖弄清楚，我需要一些代碼的幫助！

來源

2011-05-02 Becca

如果你已經花了幾個小時，向我們展示一些你已經嘗試過的，然後我們可以提供幫助。 – John 2011-05-02 18:17:28

只要走到樹的右側並返回最後一個非空節點。

來源

2011-05-02 18:17:18

它不會說二進制搜索樹，或者它以任何方式排序。 – corsiKa 2011-05-02 18:18:18

二叉樹不一定是有序的。你混淆了二叉樹和二叉搜索樹，我會說 – sehe 2011-05-02 18:19:07

首先在樹中存儲數字的意義是什麼？我知道這是我進入的一個假設，並且比較可能不是< >的比較。除此之外，採取了一點。 – 2011-05-02 18:54:24

你知道樹遍歷算法（按順序，預購，後序）嗎？

繪製一棵簡單的樹，並用鉛筆完成這些步驟。在子樹的某個點上，嘗試「推廣」一個適用於子樹的描述，然後看看你是否可以想出一個可以爲整個樹「保持」工作的描述。

來源

2011-05-02 18:18:13 sehe

只要使用任何已知的inorder，preorder或postorder方法遍歷樹。在遍歷期間，你必然遇到最大的元素。

來源

2011-05-02 18:19:05

一旦你開始考慮正確的方式，尤其是關於樹木，遞歸問題很容易解決。「樹上最大的數字是什麼？它是我自己，我的左孩子和我的右孩子的最高數字......我左邊孩子的最高數目是什麼？是孩子最高的，左邊的，還有它的最高點正確的......「等。

真的很簡單的遞歸問題。

int largest(node* root) 
{ 
    if (root == null) 
     return -1; 

    int left = largest(root->left); 
    int right = largest (root->right); 
    if(root->value > left && root->value > right) 
     return root->value; 
    else 
     return max (left, right); 
}

來源

2011-05-02 18:19:51

我明白了，所以我繼續並在 – 2011-05-02 18:45:35

遞歸是你的朋友 - 這裏的輪廓

int maxValue(Node n) { 

    if(n == null) return -1 // if this is a null node, get out with -1 

    // each time you call this, it spawns a new version of this function 
    // calling maxValue(root) could end up calling maxValue on a .left node 
    // dozens of times before it calls one on a .right node! 
    int left = maxValue(n.left) // get the left value's max 
    int right = maxValue(n.right) // get the right value's max 

    return max(this.value, left, right) // return the highest of the three values 
}

這是基本的想法。你沿着當前節點的孩子走下去，並得到結果，看看他們的結果是否比你的結果好。最高的價值將沿着鏈條向上發展。

P.S.我的代碼中的語法完全錯誤。例如，沒有分號。它也忽略指針或任何東西。把它看作僅僅是C++友好的僞代碼。

來源

2011-05-02 18:22:00 corsiKa

中添加了解釋，我正在挖掘這篇舊帖子，但如果樹中包含的所有值小於-1，我們該怎麼辦？ – 2012-11-18 13:16:57

C++查找最大數目

回答

相關問題