c++ - 我正在尝试创建一个函数“InOrder”，它在二分搜索中进行中序遍历

Question

我正在尝试将 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;
};

其他函数运行良好，如果使用 C++ 制作 InOrder 函数，我将不胜感激。

标签： c++data-structuresbinary-search-treeinorder

Answer 1

有序的概念只是秩序的概念。您还必须说明按该顺序应该做什么。您的教授提供的代码调用了一个visit函数。

这意味着在你的实现中，你还需要这样一个访问函数。它可以是硬编码的（在 上显示一个节点cout），也可以更好地作为参数传递。在这种情况下，您应该声明InOrder为：

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

然后将其（例如使用 lambda 函数）称为：

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