Передача указателя по ссылке не работает должным образом

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

Psrt моего кода BST заключается в следующем. (Это не код для чего-то, что я бы реализовал или использовал. Просто упражнение. Я выбрал BST в качестве примера для реализации некоторых вещей, которые я хотел опробовать на языке)

Заголовок —

//BST.h
class TNode
{
public:
TNode():data(0), left(0), right(0) {}
int data;
TNode* left;
TNode* right;
};

class BST
{
private:
TNode* Head;

public:
BST();

void InsertData(int data);
void InsertNode(TNode* node);
void DeleteData(int data);

private:
void InsertDataPrivate(int data, TNode* &root);
void InsertNodePrivate(TNode* node, TNode* &root);
void DeleteDataPrivate(int data, TNode* &root);
};

CPP —

//BST.cpp
#include "BST.h"
BST::BST(): Head(0)
{

}

void BST::InsertData(int data)
{
InsertDataPrivate(data, Head);
}

void BST::InsertNode(TNode* node)
{
InsertNodePrivate(node, Head);
}

void BST::DeleteData(int data)
{
DeleteDataPrivate(data, Head);
}void BST::InsertDataPrivate(int data, TNode* &root)
{
if(root == 0)
{
root = new TNode();
root->data = data;
}
else if(data < root->data) InsertDataPrivate(data, root->left);
else if(data > root->data) InsertDataPrivate(data, root->right);
}

void BST::InsertNodePrivate(TNode* node, TNode* &root)
{
if(root == 0) // Deep Copy
{
root = new TNode();
root->data = node->data;
}

else if(node->data < root->data) InsertNodePrivate(node, root->left);
else if(node->data > root->data) InsertNodePrivate(node, root->right);
}

void BST::DeleteDataPrivate(int data, TNode* &root)
{
if( 0 == root ) return;

if( root->data == data )
{
if(0 == root->left && 0 == root->right)
{
delete root;
root = 0;
}
else if(0 == root->left)
{
TNode* current = root;
root = root->right;
delete current;
current = 0;
}
else if(0 == root->right)
{
TNode* current = root;
root = root->left;
delete current;
current = 0;
}
else
{
TNode* biggestOnLeft = root->left;
TNode* smallestOnRight = root->right;
int i = 0;
while (biggestOnLeft->right) // check if left subtree is longer than right subtree
{
biggestOnLeft = biggestOnLeft->right;
--i;
}
while (smallestOnRight->left)
{
smallestOnRight = smallestOnRight->left;
++i;
}
if(i < 0) // left subtree is longer than right subtree
{
root->data = biggestOnLeft->data;
DeleteDataPrivate(biggestOnLeft->data, biggestOnLeft);
}
else // right subtree is longer than or equal in size to left subtree
{
root->data = smallestOnRight->data;
DeleteDataPrivate(smallestOnRight->data, smallestOnRight);
}
}
}
else if(data < root->data && 0 !=root->left)
{
DeleteDataPrivate(data, root->left);
}
else if(data > root->data && 0 !=root->right)
{
DeleteDataPrivate(data, root->right);
}
}

и мой тестовый код выглядит следующим образом —

//TestMain.cpp
#include "stdafx.h"#include "BST.h"

int _tmain(int argc, _TCHAR* argv[])
{
BST bst;

bst.InsertData(32);
bst.InsertData(46);
bst.InsertData(3463);
bst.InsertData(32);
bst.InsertData(856);
bst.InsertData(8098);
bst.InsertData(345);
bst.InsertData(234554);
bst.InsertData(77);
bst.InsertData(9);
bst.InsertData(15);
bst.InsertData(390);
bst.InsertData(350);
bst.InsertData(400);
bst.InsertData(76);
bst.InsertData(78);
bst.InsertData(355);
bst.DeleteData(77);

return 0;
}

На последнем шаге, где я говорю bst.DeleteData(77); У меня проблема. Узел с ’77’ удаляется правильно и заменяется на ’78’ так, как вы удаляете узел с двумя дочерними элементами из BST. Однако после удаления узла, у которого было «78», до удаления родительского узла, у которого было «77», все еще указывается на ненулевое местоположение.

Я называю свою личную функцию DeleteDataPrivate(int data, TNode* &root); который устанавливает указатель TNode в NULL после его удаления. Также я передаю указатель по ссылке в функции, так что значение NULL присваивается указателю удаленного узла, когда стек рекурсии разворачивается обратно. Такого не бывает. Может кто-нибудь объяснить, что я здесь делаю не так?

Спасибо.

Chinmay

ОБНОВИТЬ

Согласно приведенному ниже комментарию Дэна, проблема заключалась в том, что значения передавались локальным переменным, которые делали копии моих указателей и не были назначены обратно ни к чему. Я изменил свою функцию, чтобы учесть это, используя указатель на указатель так, чтобы значение указателя TNode, возвращаемое рекурсией разматывания, сохранялось в правильном месте в памяти, а не в некоторой копии указателя TNode.

Модифицированная функция выглядит следующим образом

void BST::DeleteDataPrivate(int data, TNode* &root)
{
if( 0 == root ) return;

if( root->data == data )
{
if(0 == root->left && 0 == root->right)
{
delete root;
root = 0;
}
else if(0 == root->left)
{
TNode* current = root;
root = root->right;
delete current;
current = 0;
}
else if(0 == root->right)
{
TNode* current = root;
root = root->left;
delete current;
current = 0;
}
else
{
TNode* biggestOnLeft = root->left;
TNode* smallestOnRight = root->right;
int i = 0;
while (biggestOnLeft->right) // check if left subtree is longer than right subtree
{
biggestOnLeft = biggestOnLeft->right;
--i;
}
while (smallestOnRight->left)
{
smallestOnRight = smallestOnRight->left;
++i;
}
TNode** locationOfDeletedNode = 0;
if(i < 0) // left subtree is longer than right subtree
{

locationOfDeletedNode = &(root->left);
while(*locationOfDeletedNode != biggestOnLeft) locationOfDeletedNode = &((*locationOfDeletedNode)->right);
}
else // right subtree is longer than or equal in size to left subtree
{
locationOfDeletedNode = &(root->right);
while(*locationOfDeletedNode != smallestOnRight) locationOfDeletedNode = &((*locationOfDeletedNode)->left);

}
root->data = (*locationOfDeletedNode)->data;
DeleteDataPrivate((*locationOfDeletedNode)->data, *locationOfDeletedNode);
}
}
else if(data < root->data && 0 !=root->left)
{
DeleteDataPrivate(data, root->left);
}
else if(data > root->data && 0 !=root->right)
{
DeleteDataPrivate(data, root->right);
}
}

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

0

Решение

Когда вы звоните

DeleteDataPrivate(biggestOnLeft->data, biggestOnLeft);

Он просто присваивается локальной переменной biggestOnLeft, он не присваивается ни одному члену объекта.

Потому что, когда вы делаете

TNode* biggestOnLeft = root->left;

Это создает новую переменную, которая является копия из root->leftне то же самое.

Исправить идеи

Вы можете попробовать начать biggestOnLeft а также smallestOnRight в корне, и делает

while (biggestOnLeft->right->right)

Тогда вы можете позвонить

DeleteDataPrivate(biggestOnLeft->data, biggestOnLeft->right);

ОТКАЗ ОТ ОТВЕТСТВЕННОСТИ: Я не проверял это, и мог бы сделать опечатку или что-то.

5

Другие решения

Вы не можете присвоить NULL указателю по ссылочному TNode, поскольку ссылочная переменная не может быть NULL. Посмотри пожалуйста C ++ передает указатель по ссылке и присваивает значение по умолчанию

-2

По вопросам рекламы ammmcru@yandex.ru
Adblock
detector