Вставка дерева двоичного поиска C++ с помощью рекурсии
-
03-07-2019 - |
Вопрос
Итак, мой код ниже.Я не получаю никаких ошибок, и все отлично помещается в узел.Но, судя по моим отладочным инструкциям, каждый раз, когда что-либо вставляется, оно находит корень.Я не уверен, что это правильно.Но в соответствии с выходным файлом задания мои ответы различаются, когда дело касается высоты дерева и обходов, и у меня все еще возникают проблемы с функцией подсчета листьев.Хотя другая история.
Судя по отладочным инструкциям, похоже, что все идет так, как должно.Но я думаю, мне может понадобиться свежий взгляд.Я не понимаю, как мои обходы могут вообще измениться, поскольку на самом деле вопрос только в том, где я обрабатываю узел, который должен влиять на Inorder, Preorder и Postorder.
template <class T>
void BT<T>::insert(const T& item)
{
Node<T>* newNode;
newNode = new Node<T>(item);
insert(root, newNode);
}
template <class T>
void BT<T>::insert(struct Node<T> *&root, struct Node<T> *newNode)
{
if (root == NULL)
{
cout << "Root Found" << newNode->data << endl;
root = newNode;
}
else
{
if (newNode->data < root->data)
{
insert(root->left, newNode);
cout << "Inserting Left" << newNode-> data << endl;
}
else
{
insert(root->right, newNode);
cout << "Inserting Right" << newNode->data << endl;
}
}
}
Моя функция высоты выглядит следующим образом, на случай, если с моей вставкой все в порядке.
template <class T>
int BT<T>::height() const
{
return height(root);
}
template <class T>
int BT<T>::height(Node<T>* root) const
{
if (root == NULL)
return 0;
else
{
if (height(root->right) > height(root->left))
return 1 + height(root-> right);
return 1 + height(root->left);
}
}
Решение
Вам необходимо изменить формулировку операторов отладки.
На самом деле это должно читаться (не корневой узел)
cout << "Leaf Node Found" << newNode->data << endl;
Это только корень, когда он вызывается впервые, после чего любой вызов с node->left или node->right делает его промежуточным узлом.
Чтобы написать height(), я бы сделал это:
template <class T>
int BT<T>::height(Node<T>* root) const
{
if (root == NULL) {return 0;}
return 1 + max(height(root->left),height(root->right));
}
Другие советы
Вам нужно начать с того, что ваш root инициализирован до нуля.Кроме того, вы передаете *&node в;это должно быть *node.В противном случае вы передаете указатель на адрес (или ссылку, я не уверен, что именно в этом контексте, но оба варианта не будут правильными).Вы должны передавать указатель на Node, а не ссылку.
template <class T>
void BT<T>::BT()
{ root = 0;}
template <class T>
void BT<T>::insert(const T& item)
{
Node<T>* newNode;
newNode = new Node<T>(item);
insert(root, newNode);
}
template <class T>
void BT<T>::insert(struct Node<T> *root, struct Node<T> *newNode)
{
/*stuff*/
}
@Влион:
Это должен быть указатель на левый/правый/корневой указатели (т.двойной указатель), поэтому опубликованный код верен, хотя и несколько неясен.
@Дуг:
Рассмотрите возможность изменения функции вставки следующим образом:
template <class T>
void BT<T>::insert(struct Node<T>** root, struct Node<T>* newNode)
{
if (*root == NULL)
{
cout << "Root Found" << newNode->data << endl;
*root = newNode;
}
Это ясно дает понять, что вы собираетесь изменить указатель, переданный в качестве первого параметра (или, скорее, указатель, адрес которого будет передан в качестве первого параметра). Это поможет избежать путаницы, подобной той, которая только что произошла.
Вызовы этой вставки(), такие как:
insert(&root, newNode);
также отразит ваше намерение изменить значение указателя.Однако это вопрос стиля, поэтому я не могу спорить, если вы не хотите меняться.
Что касается проверки «правильного» дерева, почему бы не нарисовать его и не убедиться в этом самому?Что-то вроде:
template class<T>
void printTree(struct Node<T>* node, int level=0)
{
if (!node) {
for (int i=0; i<level; ++i)
cout << " ";
cout << "NULL" << endl;
return;
}
printTree(node->left, level+1);
for (int i=0; i<level; ++i)
cout << " ";
cout << node->data << endl;
printTree(node->right, level+1);
}
(Непроверенный код)