二叉树中最大的数字

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