Я пытаюсь сделать функцию "InOrder", которая делает обход по бинарному поиску - PullRequest
Новая
       19

Я пытаюсь сделать функцию "InOrder", которая делает обход по бинарному поиску

0 голосов
/ 27 мая 2019

Я пытаюсь сделать InOrder в void-типе, который выполняет обход по порядку в двоичном дереве поиска. 

//Code Provided by Professor
//Program 5.1:Inorder traversal of a binary tree
//===============================================
  template <class T>
  void Tree<T>::Inorder()
  {// Driver.
     Inorder(root);
  }

 template <class T>
 void Tree<T>::Inorder(TreeNode<T> *currentNode)
  {// Workhorse.
 if (currentNode) {
     Inorder(currentNode->leftChild); 
     Visit(currentNode);
     Inorder(currentNode->rightChild);
     }
   }

Приведенный выше код предоставлен Профессором в качестве ссылки для создания моей собственной функции InOrder.

Этот код - то, как я объявил элементы (реквизиты) для моего двоичного дерева поиска. 

#include <iostream>
using namespace std;
template<class K, class E>
class BinarySearchTree 
{
public:
    virtual void Insert(const pair<K, E>&) = 0;
    virtual void Delete(const K&) = 0;
    virtual pair<K, E>*Get(const K&) const = 0;
    virtual void InOrder()const;
};
template<class T>
struct TreeNode {
    T data;
    TreeNode<T> *leftChild;
    TreeNode<T> *rightChild;
    TreeNode(T node) : data(node), leftChild(0), rightChild(0) {}
};

template<class K, class E>
class BST : BinarySearchTree<K, E> {
public:
    BST() : root(0) {}
    void Insert(const pair<K, E>&);
    void Delete(const K&);
    pair<K, E>*Get(const K&)const;
    void InOrder()const;

private:
    TreeNode<pair<K, E>> *root;
};

Другие функции работают хорошо, и я был бы признателен за любую помощь в создании функции InOrder с использованием C ++.

1 Ответ

0 голосов
/ 27 мая 2019

Понятие в порядке - это просто понятие порядка.Вы также должны сказать, что должно быть сделано в этом порядке.Код, предоставленный вашим профессором, вызывает функцию visit.

Это означает, что в вашей реализации вам также необходима такая функция посещения.Он может быть жестко закодирован (отображать узел на cout) или лучше передаваться в качестве параметра.В этом случае вы должны объявить InOrder как: 

void InOrder(void (*visit)(const pair<K, E>&))const;

, а затем вызвать его (например, с помощью лямбда-функции) как: 

BST<int, string> bst;
...
bst.InOrder([](const pair<int, string>&ke) {
    cout << "K: " << ke.first << " -E: " << ke.second << "\n";
});

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

template<class K, class E>
void BST<K,E>::doInOrder(const TN* root, void (*visit)(const pair<K, E>&)) {
    if (root) {
        doInOrder(root->leftChild, visit);
        visit(root->data);
        doInOrder(root->rightChild, visit);
    }
}

template<class K, class E>
void BST<K,E>::InOrder(void (*visit)(const pair<K, E>&))const {
    doInOrder(root, visit);
}
...