Наибольшее число в двоичном дереве

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

Поскольку бинарное дерево поиска означает, что левый дочерний элемент меньше, чем узел, правый дочерний объект больше или равен узлу.

Я думаю, что вам нужно будет найти только самый правый дочерний элемент, чтобы найти самый большой узел.

В любом случае, у вас есть 2 версии BinaryTree :: Largest, одна из которых принимает 0 аргументов, а другая - 2 аргумента.

В void BinaryTree :: Largest () вы вызываете Largest (root), но там нет Largest, который принимает только один аргумент.Возможно, вы намеревались передать один из объектов шаблона в?

Другая проблема, которую я вижу, состоит в том, что другая функция 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);
}

Answer 3

Кажется, вы солгали об удалении самого большого правого потомка.

Помимо типов возврата и арностей, вы делаете это слишком сложным. Википедия говорит:

Левое поддерево узла содержит только узлы с ключами, меньшими, чем ключ узла.