Как найти значение узла больше указанного значения в бинарном дереве поиска - PullRequest
Новая
       4

Как найти значение узла больше указанного значения в бинарном дереве поиска

0 голосов
/ 18 мая 2010

У меня есть красное черное дерево и основные операции вставки, удаления, обхода заказа, почтового заказа и предварительного заказа и т. Д.

Я хочу создать метод, который может возвращать узлы в дереве, которые больше указанного значения. То же самое с менее чем.

Может кто-нибудь указать мне на какой-нибудь псевдокод / ​​алгоритм (они, вероятно, означают одно и то же)

Приветствия

1 Ответ

0 голосов
/ 19 мая 2010

Ниже приведен код, созданный мной, который отлично тестирует отображение моих узлов в порядке возрастания для узлов, которые больше или равны указанному значению. Может ли кто-нибудь просмотреть мой код и порекомендовать улучшения и, если возможно, порекомендовать, как я могу сделать это для моего метода LessThan. В настоящее время мой метод LessThan возвращается в порядке убывания, и я просто не вижу, как получить его по возрастанию. Приветствия. 

 // --------------------------------------------------------------------------------
// GetNodesGreaterThan
// --------------------------------------------------------------------------------
/** \fn void  RedBlackTree<T>::GetNodesGreaterThan(T &data)
 *  \brief This method checks to see if tree is empty otherwise calls the 
 *          recursive the GreaterThan method.
 *  \param templated
 *  \return void
 */
template <class T>
void  RedBlackTree<T>::GetNodesGreaterThan(T &data)
{
    GreaterThan(m_root, data);
}

// --------------------------------------------------------------------------------
// GreaterThan
// --------------------------------------------------------------------------------
/** \fn void RedBlackTree<T>::GreaterThan(NodeType<T> *p, const T &data) const
 *  \brief This method finds the nodes in the tree that are greater than  or equal to 
 *          a specified value and puts nodes into a list.
 *  \param templated pointer
 *  \param constant template
 *  \return void
 */
template <class T>
void RedBlackTree<T>::GreaterThan(NodeType<T> *p, const T &data) const
{
    if ( p != NULL)                                         // we have hit a leaf node
    {
        if ((p->m_data == data) || (data < p->m_data)){     // record the node whos value is
            GreaterThan(p->m_lLink, data);                  // move down left link
            //cout << p->m_data << " ";                     // Display data (debug purpose)
        }
        GreaterThan(p->m_rLink, data);                      // move down right link 
    }
}

// --------------------------------------------------------------------------------
// GetNodesLessThan
// --------------------------------------------------------------------------------
/** \fn void  RedBlackTree<T>::GetNodesLessThan(T &data)
 *  \brief This method checks to see if tree is empty otherwise calls the 
 *          recursive the LessThan method.
 *  \param template
 *  \return void
 */
template <class T>
void  RedBlackTree<T>::GetNodesLessThan(T &data)
{
    ClearList();                                            // clears the node list
    LessThan(m_root, data);
}

// --------------------------------------------------------------------------------
// LessThan
// --------------------------------------------------------------------------------
/** \fn void RedBlackTree<T>::LessThan(NodeType<T> *p, const T &data) const
 *  \brief This method finds the nodes in the tree that are less than  or equal to 
 *          a specified value and puts nodes into a list.
*  \param templated pointer
 *  \param constant template
 */
template <class T>
void RedBlackTree<T>::LessThan(NodeType<T> *p, const T &data) const
{
    if ( p != NULL)
    {
        if ((p->m_data == data) || (data > p->m_data)){     // record the node whos value is
            LessThan(p->m_rLink, data);                     // move down left link
            //cout << p->m_data << " ";                     // Display data (debug purpose)
            //m_list[m_countOfElements] = p->m_data;            // add to list
            //m_countOfElements++;                              // increment # of elements
        }
        LessThan(p->m_lLink, data);                         // move down left link
    }
}
...