二叉樹中最大的數字

Question

所以我試圖找到我的二叉樹中最大的數字，所以我可以刪除它，但它不會運行，插入部分，我正在尋找最大的數字，樹工作得很好，沒有這部分。

這裏是我得到了現在的代碼：

#include <iostream> 
#include <string> 


using namespace std; 


template<class T> 
class BinaryTree 
{ 

struct Node 
    { 
     T data; 
     Node* lChildptr; 
     Node* rChildptr; 

     Node(T dataNew) 
     { 
      data = dataNew; 
      lChildptr = NULL; 
      rChildptr = NULL; 

     } 
    }; 
private: 
    Node* root; 

     void Insert(T newData, Node* &theRoot) 
     { 
      if(theRoot == NULL) 
      { 
       theRoot = new Node(newData); 
       return; 
      } 

      if(newData < theRoot->data) 
       Insert(newData, theRoot->lChildptr); 
      else 
       Insert(newData, theRoot->rChildptr);; 
     } 

     void PrintTree(Node* theRoot) 
     { 
      if(theRoot != NULL) 
      { 
       PrintTree(theRoot->lChildptr); 
       cout<< theRoot->data<<" \n";; 
       PrintTree(theRoot->rChildptr); 
      } 
     } 
     void Largest(Node* theRoot, T max) 
     { 
      if (theRoot == null) 
      return -1; 

      int left = Largest(theRoot->lChildptr); 
      int right = Largest (theRoot->rChildptr); 
     if(theRoot->data > left && theRoot->data > right) 
     return theRoot->data; 
      else 
     return max (left, right); 
}; 

    public: 
     BinaryTree() 
     { 
      root = NULL; 
     } 

     void AddItem(T newData) 
     { 
      Insert(newData, root); 
     } 

     void PrintTree() 
     { 
      PrintTree(root); 
     } 
     void Largest() 
     { 
      Largest(root); 
     } 
    }; 

    int main() 
    { 
     BinaryTree<int> *myBT = new BinaryTree<int>(); 
     myBT->AddItem(2); 
     myBT->AddItem(5); 
     myBT->AddItem(1); 
     myBT->AddItem(10); 
     myBT->AddItem(8); 
     myBT->PrintTree(); 
     myBT->Largest(); 
    } 

Answer 1

樹中的最大數量將在樹中最右邊的節點。所以繼續往前走，直到你不能再走了。

//刪除代碼，因爲這可能是一個問題的功課

Answer 2

看來你撒謊刪除最大的右孩子。

除了返回類型和arities，你讓它有點太複雜。 Wikipedia說：

節點的左子樹只包含鍵小於節點的關鍵節點。

Answer 3

由於二叉搜索樹意味着左側子節點小於節點，右側子節點大於或等於節點。

我想你只需要找到最合適的孩子找到最大的節點。

無論如何，你有2個版本BinaryTree :: Largest，一個取0個參數，一個取2個參數。

在void BinaryTree :: Largest（）中，您調用Largest（root），但沒有最大隻接受一個參數。也許你打算傳遞一個模板對象？

我看到的另一個問題是，其他Largest函數返回void而不是數字，並且使用模板對象（max），如果它不是（它是您的示例中的int），它就是一個函數。稍後你返回模板，當函數聲明它返回void時。

我建議你改變Largest返回模板而不是void。

T Largest(Node* theRoot)//<-- Notice returning of the template, not void 
{ 
    if (theRoot == null) 
     return -1; 

    T left = Largest(theRoot->lChildptr); 
    T right = Largest (theRoot->rChildptr); 
    if(theRoot->data > left && theRoot->data > right) 
     return theRoot->data; 
    else if (left < right)//<-- max was not a function, manual compare 
     return right; 
    else 
     return left; 
}//<--You were missing a "}" here too 

//... 

T Largest() 
{ 
    return Largest(root); 
}