在二叉搜索树中排序对象值

Question

我正在将以下项目插入到二叉搜索树中：

Mayweather,Floyd,1,105,105,0,Boxing
Ronaldo,Cristiano,2,80,52,28,Soccer
James,LeBron,3,72.3,19.3,53,Basketball
Messi,Lionel,4,64.7,41.7,23,Soccer
Bryant,Kobe,5,61.5,30.5,31,Basketball
Woods,Tiger,6,61.2,6.2,55,Golf
Federer,Roger,7,56.2,4.2,52,Tennis
Mickelson,Phil,8,53.2,5.2,48,Golf
Nadal,Rafael,9,44.5,14.5,30,Tennis
Ryan,Matt,10,43.8,42,1.8,Football
Pacquiao,Manny,11,41.8,41,0.8,Boxing
Ibrahimovic,Zlatan,12,40.4,36.4,4,Soccer
Rose,Derrick,13,36.6,17.6,19,Basketball
Bale,Gareth,14,36.4,25.4,11,Soccer
Falcao,Radamel,15,36.4,32.4,3,Soccer

其中排名是 csv 中的第一个整数。正如您所看到的，大多数已经有序，但一旦它们进入二叉搜索树，并且如果我进行预遍历，post 或有序遍历，它们也会乱序。

我尝试了很多方法，但假设不能使用数组、向量或任何其他对象 - 只能使用树，这怎么能做到？

void displayRank(Athlete& anItem)
{
        cout << "Player: " << anItem.getRank() << endl;
}

void AthleteDatabase::displayByRank(void)
{
    athleteDatabaseBST.preorderTraverse(displayRank);
}

内置遍历以随机顺序打印排名，因为姓氏是关键。非常感谢任何帮助！

下面是 BinarySearchTree.h 文件：

class BinarySearchTree : public BinaryNodeTree<ItemType>
{
private:
   BinaryNode<ItemType>* rootPtr;

protected:
   //------------------------------------------------------------
   // Protected Utility Methods Section:
   // Recursive helper methods for the public methods.
   //------------------------------------------------------------
   // Recursively finds where the given node should be placed and
   // inserts it in a leaf at that point.
   BinaryNode<ItemType>* insertInorder(BinaryNode<ItemType>* subTreePtr,
                                       BinaryNode<ItemType>* newNode);

   // Removes the given target value from the tree while maintaining a
   // binary search tree.
   BinaryNode<ItemType>* removeValue(BinaryNode<ItemType>* subTreePtr,
                                     const ItemType target,
                                     bool& success);

   // Removes a given node from a tree while maintaining a
   // binary search tree.
   BinaryNode<ItemType>* removeNode(BinaryNode<ItemType>* nodePtr);

   // Removes the leftmost node in the left subtree of the node
   // pointed to by nodePtr.
   // Sets inorderSuccessor to the value in this node.
   // Returns a pointer to the revised subtree.
   BinaryNode<ItemType>* removeLeftmostNode(BinaryNode<ItemType>* subTreePtr,
                                            ItemType& inorderSuccessor);

   // Returns a pointer to the node containing the given value,
   // or nullptr if not found.
   BinaryNode<ItemType>* findNode(BinaryNode<ItemType>* treePtr,
                                  const ItemType& target) const;

public:
   //------------------------------------------------------------
   // Constructor and Destructor Section.
   //------------------------------------------------------------
   BinarySearchTree();
   BinarySearchTree(const ItemType& rootItem);
   BinarySearchTree(const BinarySearchTree<ItemType>& tree);
   virtual ~BinarySearchTree();

   //------------------------------------------------------------
   // Public Methods Section.
   //------------------------------------------------------------
   bool isEmpty() const;
   int getHeight() const;
   int getNumberOfNodes() const;
   ItemType getRootData() const throw(PrecondViolatedExcep);
   void setRootData(const ItemType& newData) const throw(PrecondViolatedExcep);
   bool add(const ItemType& newEntry);
   bool remove(const ItemType& anEntry);
   void clear();
   ItemType getEntry(const ItemType& anEntry) const throw(NotFoundException);
   bool contains(const ItemType& anEntry) const;

   //------------------------------------------------------------
   // Public Traversals Section.
   //------------------------------------------------------------
   void preorderTraverse(void visit(ItemType&)) const;
   void inorderTraverse(void visit(ItemType&)) const;
   void postorderTraverse(void visit(ItemType&)) const;

   //------------------------------------------------------------
   // Overloaded Operator Section.
   //------------------------------------------------------------
   BinarySearchTree<ItemType>& operator=(const BinarySearchTree<ItemType>& rightHandSide);   
}; // end BinarySearchTree

Answer 1

当您无法将树的内容转储到向量中并在不同字段上对向量进行排序时，我想您可以尝试以下操作：

第1步：根据新的排序字段查找、报告并保留最小元素的副本。（搜索整棵树）

第 2 步（及后续步骤）：查找、报告并保留也大于前一个最小元素的最小元素的副本。（搜索整棵树）

效率不是很高，但我认为你应该能够完成这项工作。

祝你好运。

在二叉搜索树中排序对象值

Ordering object values in a binary search tree

c++

sorting

binary-search-tree