Ошибка удаления из двоичного дерева

Question

Я написал небольшой код для определения наибольшего числа в двоичном дереве, он работает просто отлично, просто, он уходит далеко вниз до последнего правого узла (лист в случае), а затем я просто cout << it, Теперь я хотел бы удалить его, я посмотрел через какой-то похожий вопрос, но мне нужно только удалить номер, который я получил от поиска, но моя прога просто падает, после того, как я запускаю ее, список дерева получает номер, удаляет и пытается перечислите это снова. </p>

Вот мой поиск:

    T Remove( Node* theRoot)
        {
        if ( root == NULL )
        {
             cout<<"There is no tree";
             return -1;
        }

        if (theRoot->rChildptr != NULL)
            return Largest(theRoot->rChildptr);
        else
             delete theRoot;
             return theRoot->data;

    } 

Вот полный код:

#include <iostream>
#include <string>
#include <cstdlib> 


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);
            }
        }
        T Largest( Node* theRoot)
            {
            if ( root == NULL )
            {
                 cout<<"There is no tree";
                 return -1;
            }

            if (theRoot->rChildptr != NULL)
                return Largest(theRoot->rChildptr);
            else
                 delete theRoot;
                 return theRoot->data;

        }
        T Remove(Node* theRoot)
        {
            if ( root == NULL )
            {
                 cout<<"There is no tree";
                 return -1;
            }

            if (theRoot->rChildptr != NULL)
                return Largest(theRoot->rChildptr);
            else
                delete theRoot;
                 return ;
        };

    public:
        BinaryTree()
        {
            root = NULL;
        }

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

        void PrintTree()
        {
            PrintTree(root);
        }
        T Largest()
        {
            return Largest(root);
        }
        //void Remove()
        //{
        //  Remove(root);
        //}

    };

    int main()
    {
        BinaryTree<int> *myBT = new BinaryTree<int>();
        myBT->AddItem(2);
        myBT->AddItem(20);
        myBT->AddItem(5);
        myBT->AddItem(1);
        myBT->AddItem(10);
        myBT->AddItem(15);
            //for(int i = 0; i < 10; i++)           //randommal tolti fel
                //myBT->AddItem(rand() % 100);
        cout << "BinaryTree:" << endl;              //kilistazaa a fat
        myBT->PrintTree();
        cout << "Largest element: " << myBT->Largest() << endl;  //visszaadja a legnagyobb elemet
        //myBT->Remove();
        myBT->PrintTree();
  }

фактическая функция удаления находится в // комментариях, чтобы я мог запустить прогу.

Answer 1

Вы удаляете theRoot, а затем пытаетесь разыменовать его. Если вы хотите вернуть значение, хранящееся в узле, вам сначала нужно сделать локальную копию, например:

T value = theRoot->data;
delete theRoot;
return value;

Предполагается, что строка return thetRoot->data; является частью оператора else? Если это так, вам нужно добавить скобки вокруг этого следующим образом:

if (theRoot->rChildptr != NULL)
{
    return Largest(theRoot->rChildptr);
}
else
{
    T value = theRoot->data;
    delete theRoot;
    return value;
}

Или просто полностью удалите регистр else (поскольку вы всегда возвращаете, если дочерний указатель равен нулю):

if (theRoot->rChildptr != NULL)
{
    return Largest(theRoot->rChildptr);
}

T value = theRoot->data;
delete theRoot;
return value;

Вам также необходимо убедиться, что родительский узел по-прежнему не указывает на удаленный дочерний элемент (трудно точно понять, что происходит, потому что вы не опубликовали много кода).

Answer 2

Вы не можете просто delete объект, который вам не нужен - вы также должны удалить ссылку, которую вы использовали для поиска узла, который вы удаляете.И, если у узла есть какие-либо дочерние элементы, вы должны присоединить дочерние узлы в другом месте к дереву, чтобы они оставались доступными.

То, что делает его таким сложным, заключается в том, что вы должны правильно обновить: ссылка родителя наудаляемый узел;один из указателей 'child' для одного из потомков удаленного узла;и родительские ссылки от обоих дочерних элементов удаленного узла.Если вы выполняете обновления не по порядку, вы прочтете устаревший указатель и, возможно, испорченную память, поэтому вам придется подождать, чтобы удалить узлы, пока вам не понадобятся дополнительные ссылки внутри узла, и вы удалили ссылки к узлу из другого места.

Обновление

Не забывайте, что "последний правый узел" на самом деле может быть корнем вашего дерева:

    5
   4
  3
 2
1

5 - это самый большой, самый правый узел вашего дерева, и если вы удалите его, вы потеряете все свое дерево.

Если вы не делаетенекоторая перебалансировка, которую мы не видим здесь;если да, убедитесь, что вы также обрабатываете этот случай:

 2
1

Наши друзья из Wikipedia очень любезно проанализировали, как удалить узел из бинарного дерева поиска:

• Удаление листа (узел без дочерних элементов): удалить лист легко, поскольку мы можем просто удалить его из дерева.
• Удаление узла с одним дочерним элементом: Удалитьузел и замените его своим дочерним элементом.
• Удаление узла с двумя дочерними элементами: вызовите узел, который нужно удалить N. Не удаляйте N. Вместо этого выберите либо его преемный узел-преемник, либо его порядокузел предшественника R. Замените значение N значением R, затем удалите R.

Код удаления должен обрабатывать все три этих случая.Не забывайте, что удаляемый вами узел может быть корнем дерева и не иметь родительского узла.

Answer 3

Можете ли вы опубликовать всю программу, чтобы ее можно было скомпилировать.Но в основном проблема в том, что когда theRoot-> rChildptr равен NULL, вы удаляете theRoot, а затем ваш оператор return пытается вернуть данные theRoot->, которые указывают на никуда.