Отображение пути к узлу в дереве двоичного поиска
Я работаю над попыткой отобразить путь от корневого узла BST до целевого узла. Функция, которая у меня есть, отлично работает для первых двух слоев, но потом портится. Например, номера тестов 6, 9, 4, 11, 10 (вставляются в этом порядке). Если я ищу 6, 9 или 4, это работает (например: «6 9»). Но если я попытаюсь 11 или 10, он отображает их обоих, и не в порядке. Я немного озадачен, почему. Любые идеи будут потрясающими!
template <class T>
void BST<T>::displayPath(T searchKey, BST<T> *node)
{
if (searchKey == node->mData)
{
cout << node->mData << " ";
}
else if (searchKey < node->mData )
{
cout << node->mData << " ";
displayPath(searchKey, node->mLeft);
}
else// (searchKey > node->mData)
{
cout << node->mData << " ";
displayPath(searchKey, node->mRight);
}
}
Это функция вставки. Номера вставляются в порядке выше.
template <class T>
void BST<T>::insert(BST<T> *&node, T data)
{
// If the tree is empty, make a new node and make it
// the root of the tree.
if (node == NULL)
{
node = new BST<T>(data, NULL, NULL);
return;
}
// If num is already in tree: return.
if (node->mData == data)
return;
// The tree is not empty: insert the new node into the
// left or right subtree.
if (data < node->mData)
insert(node->mLeft, data);
else
insert(node->mRight, data);
}
Решение
Ваш код подтверждает мое подозрение. Ваш метод в порядке — это дерево, которое вы построили из вставки 6, 9, 4, 11, 10 в этом порядке:
первая (6):
6
второй (9)
6
\
9
3-й (4)
6
/ \
4 9
4 (11):
6
/ \
/ \
4 9
\
\
11
5 (10):
6
/ \
/ \
4 9
\
\
11
/
/
10
Так что поиск 10 даст вам путь (6,9,11,10).
Обратите внимание, что путь от корня к элементу в BST НЕ гарантируется для сортировки — если это было то, что вы ожидали. Фактически, он будет отсортирован, только если узел находится на пути к самому правому листу дерева.
Другая проблема в коде: поиск 7 (или любого элемента, который не существует в дереве) даст вам некоторый фиктивный путь.
Другие решения
Код будет работать, только если входное значение находится в дереве. Когда вы ищете значение, которого нет, вы ищете узел, которого нет в дереве
template <class T>
void BST<T>::displayPath(T searchKey, BST<T> *node)
{
if (searchKey == node->mData)
{
cout << node->mData << " ";
}
else if (searchKey < node->mData )
{
cout << node->mData << " ";
if (node->mLeft == NULL) // When trying to access a node that isn't there
cout << "Not Found\n";
else
displayPath(searchKey, node->mLeft);
}
else // (searchKey > node->mData)
{
cout << node->mData << " ";
if (node->mRight == NULL)
cout << "Not Found\n";
else
displayPath(searchKey, node->mRight);
}
}