Для обхода двоичного дерева поиска без указателя узла как параметра

Question

Мне нужно запрограммировать функцию для лаборатории в двоичном дереве поиска для обхода. Моя проблема, я был дан интерфейс, который я должен следовать и в нем единственный параметр, я могу перейти к функции обхода является еще одной функцией ничтожной возвращаемого типа:

void BinarySearchTree<ItemType, KeyType>::inorderTraverse(void visit(ItemType&)) const 

Функция визит в основном функция что я буду определять для конкретного примера использования для дерева, например, я хочу распечатать дерево в порядке возрастания, и в этом случае функция, которую я передал бы функции inorderTraverse, будет функцией печати. Я не могу понять, как пройти все дерево без указателя узла в качестве параметра. Я не прошу весь код, просто совет, который может указать мне в правильном направлении! Вот BinarySearchTree.h:

template<typename ItemType, typename KeyType> 
class BinarySearchTree 
{ 
private: 
    BinaryNode<ItemType>* rootPtr; 

    // Recursively deletes all nodes from the tree. 
    void destroyTree(BinaryNode<ItemType>* subTreePtr); 

    // 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); 

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

public: 
    //------------------------------------------------------------ 
    // Constructor and Destructor Section. 
    //------------------------------------------------------------ 
    BinarySearchTree(); 
    virtual ~BinarySearchTree(); 

    //------------------------------------------------------------ 
    // Public Methods Section. 
    //------------------------------------------------------------ 
    bool add(const ItemType& newEntry); 
    ItemType getEntry(const KeyType& aKey) const throw(NotFoundException); 
    bool contains(const KeyType& aKey) const; 

    //------------------------------------------------------------ 
    // Public Traversals Section. 
    //------------------------------------------------------------ 
    void inorderTraverse(void visit(ItemType&)) const; 
}; // end BinarySearchTree 

#include "BinarySearchTree.cpp" 

#endif 

Answer 1

я предполагаю BinaryNode есть методы

const BinaryNode* getLeft() const; 
const BinaryNode* getRight() const; 
const ItemType& getValue() const; 

[Отредактировано по причине: «получил сказали, что мы не могли бы добавить что-нибудь дополнительное к классу»]

Вы видите, что метод static - это означает, что он не полагается ни на какие знания о конкретном моменте вашего дерева.

Из-за этого его можно разместить в любом месте.

Например, просто напишите его как статическую функцию вне класса, внутри вашего файла "BinarySearchTree.cpp".

Другое решение: реализовать внутри метода inorderTraverse, как lambda function как в:

// as a method of this class, you **do** have access to the root node 
    void inorderTraverse(void visit(const ItemType&)) const { 
    // this is a lambda function 
    auto inOrderRecurse=(
     const BinaryNode<ItemType>* node, 
     void visit(const ItemType&) 
    ) { 
     if(node) { 
      auto n=node->getLeft(); 
      if(n) { 
       this->inOrderRecurse(n, visit); 
      } 
      visit(node->getValue()); 
      n=node->getRight(); 
      if(n) { 
      this->inOrderRecurse(n, visit); 
      } 
     } 
     } 
    ; 
    inOrderRecurse(this->rootPtr); 
    } 

Еще одно решение: если вы не можете использовать лямбды, вы все еще можете declare a class/structure inside you method. Итак, давайте объявим/используем его в самом методе inorderTraverse.

// as a method of this class, you **do** have access to the root node 
    void inorderTraverse(void visit(const ItemType&)) const { 
    struct recurser { 
     static void inOrderRecurse(
     const BinaryNode<ItemType>* node, 
     void visit(const ItemType&) 
    ) { 
     // etc... 
     } 
    }; 
    recurser::inOrderRecurse(this->rootPtr); 
    } 

---

[оригинальный ответ]

Таким образом, inorderTraverse может быть реализован как:

private: 
    // "All problems in computer science can be solved by another level of indirection, 
    // except of course for the problem of too many indirections." 
    // In the context, **this method** is another level of indirection 
    static void inOrderRecurse(
     const BinaryNode<ItemType>* node, 
     void visit(const ItemType&) 
) const { 
    if(node) { 
    auto n=node->getLeft(); 
    if(n) { 
     this->inOrderRecurse(n, visit); 
    } 
    visit(node->getValue()); 
    n=node->getRight(); 
    if(n) { 
     this->inOrderRecurse(n, visit); 
    } 
    } 
public: 

    // as a method of this class, you **do** have access to the root node 
    void inorderTraverse(void visit(const ItemType&)) const { 
    // note this `const` here ---^ needed because of ^^^^ this one 
    inOrderRecurse(this->rootPtr); 
    }