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

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

0

binary-search-tree c++inorder

Решение

Другие решения

Других решений пока нет …

Источник

Accepted Answer

Я предполагаю BinaryNode имеет методы

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

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

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

Из-за этого его можно разместить где угодно.

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

Другое решение: реализовать его внутри 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);
}

Еще одно решение: если вам не разрешено использовать лямбды, вы все равно можете объявить класс / структуру внутри вашего метода. Итак, давайте объявим / используем один в самом 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);
}

2