如何在二叉搜索树中查找值大于指定值的节点

Question

我有一棵红黑树，基本操作是插入、删除、遍历中序、后序和前序等。

我希望创建一个方法，可以返回树中大于指定值的节点。与小于也相同。

谁能指出我一些伪代码/算法（它们可能意味着相同的事情）

干杯

Answer 1

下面是我创建的代码，它可以很好地测试以升序显示大于或等于指定值的节点的节点。有人可以检查我的代码并提出改进建议，如果可能的话建议我如何为我的 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
    }
}