ノードポインタを持たないバイナリ検索ツリーのトラバーサルをパラメータとして

Question

私は、トラバーサルのためにバイナリ検索ツリー内のラボ用の関数をコーディングする必要があります。私の問題は、私は私が従わなければならないインターフェースを与えてきたし、その中で私がトラバーサル関数に渡すことができる唯一のパラメータがvoid戻り値の型の別の関数である：

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"ファイル内のクラス外の静的関数として記述します。

別の解決策：のようlambda functionとして、inorderTraverseメソッドの中にそれを実装します。さらに別の解決策

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