Найти п-й узел в бинарном дереве поиска

С помощью этой начальной загрузки:Найти п-й узел в бинарном дереве поиска

template <class Comparable> 
const Comparable& AugmentedBinarySearchTree<Comparable>::NthElement(int n) 
{ 
    int *i = 0; 
    return NthElement(root, i, n)->element; 
}

Как бы вы найдете п-й узел в BST, используя nodesVisited указатель для отслеживания узлов проверяется?

template <class Comparable> 
BinaryNode<Comparable>* AugmentedBinarySearchTree<Comparable>:: 
NthElement(BinaryNode<Comparable> *t, int *nodesVisited, int n) const 
{ 

}

Каждый узел в BST имеет указатель left и right и значение template <class Comparable> под названием element.

источник

2015-10-26 m_callens

Что означает «N-й узел» в двоичном дереве? Разве это не зависит от того, как проходит двоичное дерево? – PaulMcKenzie

@PaulMcKenzie, найдя «N-й узел», я имею в виду n-е значение, которое было вставлено в дерево, довольно самоочевидное. –

Пройдите по дереву в любом порядке (возможно, в порядке). Увеличивайте '* nodesVisited' для каждого узла. Остановитесь, когда '* nodesVisited == n'. –

Это звучит для меня (из вашего комментария), как будто вы ищете многоиндексный контейнер Boost (http://www.boost.org/doc/libs/1_59_0/libs/multi_index/doc/index.html). У вас будут векторные и картографические представления и вставка с push_back в векторное представление при использовании вида карты для поиска по ключу. Затем вы будете использовать векторный вид, чтобы получить элемент, вставленный n-ым.

источник

2015-10-26 17:48:09

Найти п-й узел в бинарном дереве поиска

ответ

Смежные вопросы