Вот мой код:
template <typename DataType> bool SearchValue(TreeNode<DataType> *root, DataType search_value)
{
if(search_value != root->data)
{
if(root->right != NULL)
{
return SearchValue(root->right, search_value);
}
if (root->left != NULL)
{
return SearchValue(root->left, search_value);
}
return false;
}
else
{
return true;
}
}
Я не могу заставить функцию SearchValue
работать должным образом. условием является не менять сигнатуру функции SearchValue
.
Проблема следующая: например, мы пытаемся найти элемент с полем данных равным "90" и он существует в дереве. Иногда этот код находит этот элемент, а иногда нет - в зависимости от его положения в дереве.
Вопрос в том, как заставить его работать правильно каждый раз.
Строю дерево так:
template <typename DataType> TreeNode<DataType> *BuildTree()
{
TreeNode<DataType> *root = new TreeNode<DataType>(10, new TreeNode<DataType>(20), new TreeNode<DataType>(30));
TreeNode<DataType> *curRoot = root;
curRoot = curRoot->left;
curRoot->left = new TreeNode<DataType>(40);
curRoot->left->left = new TreeNode<DataType>(70);
curRoot->right = new TreeNode<DataType>(50);
curRoot = curRoot->right;
curRoot->left = new TreeNode<DataType>(80, new TreeNode<DataType>(100), new TreeNode<DataType>(110));
curRoot = root->right;
curRoot->left = new TreeNode<DataType>(60);
curRoot = curRoot->left;
curRoot->right = new TreeNode<DataType>(90, new TreeNode<DataType>(120), new TreeNode<DataType>(130));
return root;
}
Тестирую поиск так:
TreeNode<int> *treeRoot = BuildTree<int>();
int valueToFind = treeRoot->data;
cout << "Enter the value you'd like to find in the tree: ";
cin >> valueToFind;
cin.get();
if(SearchValue(treeRoot, valueToFind) == true)
{
cout << "Value " << valueToFind << " was found!";
}
Как реализую дерево:
template <typename DataType> struct TreeNode
{
TreeNode(DataType val, TreeNode<DataType> *leftPtr = NULL, TreeNode<DataType> *rightPtr = NULL)
{
left = leftPtr;
right = rightPtr;
data = val;
}
TreeNode<DataType> *left, *right;
DataType data;
};