Красно-черное дерево неверное преобразование
У меня проблемы с прохождением инициализации красного черного дерева. Всякий раз, когда я компилирую, я получаю следующую ошибку.
redBlackTree.h:81:28: error: invalid conversion from ‘long int’ to ‘nodeColor’ [-fpermissive]
nodeType<myType> *x = new nodeType<myType>;
^
redBlackTree.h:10:8: error: invalid conversion from ‘long int’ to ‘nodeColor’ [-fpermissive]
struct nodeType
^
redBlackTree.h:81:28: note: synthesized method ‘nodeType<int>::nodeType()’ first required here
nodeType<myType> *x = new nodeType<myType>;
У меня также возникают проблемы при поиске дерева, чтобы убедиться, что значение уже не внутри дерева. Текущий метод я могу думать об этом, но я все еще получаю дубликаты результатов внутри моего дерева.
if(nd != NULL)
{
if(nd->keyValue == x)
return true;
return ((search(x, nd->right)) || (search(x, nd->left)));
}
return false;
Он находится под функцией вставки. Может ли быть так, как я объявляю свои переменные? Предполагается, что мы следуем определенному шаблону, и он говорит, что должен создать новый nodeType, но не может. Удаление приводит к ошибке программы.
#ifndef REDBLACKTREE_H
#define REDBLACKTREE_H
#include <iostream>
#include <sstream>
using namespace std;
enum nodeColor { RED, BLACK };
template<class myType>
struct nodeType
{
myType keyValue = keyValue;
nodeColor color = NULL;
nodeType *left = NULL;
nodeType *right = NULL;
nodeType *parent = NULL;
};
template <class myType>
class redBlackTree
{
public:
redBlackTree(){};
~redBlackTree();
void destroyTree();
unsigned int countNodes() const;
unsigned int height() const;
void printTree() const;
void insert(myType);
bool search(myType);
private:
nodeType<myType> *root = NULL;
bool search(myType, nodeType<myType> *);
void destroyTree(nodeType<myType> *);
unsigned int countNodes(nodeType<myType> *) const;
unsigned int height(nodeType<myType> *) const;
void printTree(nodeType<myType> *) const;
void rightRotate(nodeType<myType> *);
void leftRotate(nodeType<myType> *);
};
//template <class myType>
//redBlackTree<myType>::redBlackTree():root(NULL)
//{
//};
template <class myType>
redBlackTree<myType>::~redBlackTree()
{
destroyTree();
}
template <class myType>
void redBlackTree<myType>::destroyTree()
{
destroyTree(root);
};
template <class myType>
unsigned int redBlackTree<myType>::countNodes() const
{
return countNodes(root);
};
template <class myType>
unsigned int redBlackTree<myType>::height() const
{
return height(root);
};
template <class myType>
void redBlackTree<myType>::printTree() const
{
printTree(root);
};
template <class myType>
void redBlackTree<myType>::insert(myType value)
{
if(search(value))
return;
nodeType<myType> *x = new nodeType<myType>;
x->right = NULL;
x->left = NULL;
x->parent = NULL;
x->keyValue = value;
x->color = RED;
if(root == NULL)
{
root = x;
x->color = BLACK;
return;
}
nodeType<myType> *curr = root;
if(curr->keyValue > x->keyValue)
{
curr->left = x;
x->parent = curr;
x->color = RED;
}
else
{
curr->right = x;
x->parent = curr;
x->color = RED;
}
while(x != root && x->parent->color == RED)
{
if(x->parent == x->parent->parent->left)
{
if(x->parent->parent->right != NULL && x->parent->parent->color == RED)
{
x->parent->color = BLACK;
x->parent->parent->right->color = BLACK;
x->parent->parent->color = RED;
x = x->parent->parent;
}
else
{
if(x == x->parent->right)
{
x = x->parent;
leftRotate(x);
}
x->parent->color = BLACK;
x->parent->parent->color = RED;
rightRotate(x->parent->parent);
}
}
else
{
if(x->parent->parent->left != NULL && x->parent->parent->color == RED)
{
x->parent->color = BLACK;
x->parent->parent->left->color = BLACK;
x->parent->parent->color = RED;
x = x->parent->parent;
}
else
{
if(x == x->parent->right)
{
x = x->parent;
rightRotate(x);
}
x->parent->color = BLACK;
x->parent->parent->color = RED;
leftRotate(x->parent->parent);
}
}
if(x == root)
x->color = BLACK;
}
};
template <class myType>
bool redBlackTree<myType>::search(myType x)
{
search(x, root);
};
template <class myType>
bool redBlackTree<myType>::search(myType x, nodeType<myType> *nd)
{
if(nd == NULL)
return 0;
search(x, nd->left);
search(x, nd->right);
if(nd->keyValue == x)
return true;
else
return false;
};
template <class myType>
void redBlackTree<myType>::destroyTree(nodeType<myType> *node)
{
if(node==NULL)
return;
destroyTree(node->left);
destroyTree(node->right);
delete node;
};
template <class myType>
unsigned int redBlackTree<myType>::countNodes(nodeType<myType> *nd) const
{
if(nd==NULL)
return 0;
return (countNodes(nd->left) + countNodes(nd->right) + 1);
};
template <class myType>
unsigned int redBlackTree<myType>::height(nodeType<myType> *nd) const
{
int leftHeight = 0;
int rightHeight = 0;
if(nd==NULL)
return 1;
leftHeight = leftHeight + height(nd->left);
rightHeight = rightHeight + height(nd->right);
if(leftHeight == rightHeight)
return leftHeight;
else if(leftHeight > rightHeight)
return leftHeight;
else
return rightHeight;
};
template <class myType>
void redBlackTree<myType>::printTree(nodeType<myType> *nd) const
{
if(nd == NULL)
return;
printTree(nd->left);
cout << nd->keyValue;
printTree(nd->right);
cout << nd->keyValue;
};
template <class myType>
void redBlackTree<myType>::rightRotate(nodeType<myType> *y)
{
nodeType<myType> *x = y->left;
x->left = x->right;
if(x->right != NULL)
x->right->parent = y;
x->parent = y->parent;
if(x->parent == NULL)
root = x;
else if(y == y->parent->left)
y->parent->left = x;
else
y->parent->right = x;
x->right = y;
y->parent = x;
};
template <class myType>
void redBlackTree<myType>::leftRotate(nodeType<myType> *x)
{
nodeType<myType> *y = y->right;
x->right = y->left;
if(x->right != NULL)
root = y;
else if(x == x->parent->left)
x->parent->left = y;
else
x->parent->right = y;
x->left = x;
x->parent = y;
};
#endif
1 ответ
Решение
Проблема вызвана строкой:
nodeColor color = NULL;
NULL не является допустимым значением для color, Используйте допустимое значение, например:
nodeColor color = RED;
Также линия
myType keyValue = keyValue;
будет проблемой. Инициализирует keyValue с неинициализированным значением keyValueСделайте RHS этой строки чем-то более подходящим, например:
myType keyValue = {};
Вам не хватает return во-первых search функция.
template <class myType>
bool redBlackTree<myType>::search(myType x)
{
return search(x, root);
// ^^
}
Вам не нужно ; в конце определения функции-члена. У вас есть их в некоторых определениях функций. Вы должны удалить их.