二分搜索树

Question

关于C++中的二进制搜索树实现，我有一个问题。下面是问题

实现一个存储整数的简单(非模板化) BST。提供以下操作: Insert、Remove、inOrder遍历、preOrder遍历、postOrder遍历。

使用递归例程来处理树。

处理节点只需要打印出节点的内容，在本例中是存储在节点中的整数。

数据应该来自测试文件。主程序应该打开数据文件并插入到树中，并演示其他树操作。

本练习的目的是证明您理解BST。没有必要过多地使用它，并在不需要的情况下进行操作。

到目前为止，我只创建了头文件。有没有人可以看看我是否走对了方向？

using namespace std;
#ifndef BSTNODE_H
#define BSTNODE_H
class BSTNode
{
    private:
    //Defines the 'node' structure
    struct tree_node 
    {
     tree_node *left;   // left subtree has smaller elements
     tree_node *right;  // right subtree has larger elements
     int m_data;
    };
    //root * r;
    public:
        //The Constructor
        BSTNode();
        //The Destructor
       ~BSTNode();
       //Inserts a value into a BST, public function
        void insert(const m_data & d);
        //Removes a value from a BST, public function
        void remove(const m_data & d);
        //isEmpty function, public function
        bool isEmpty();
        BSTNode getData();
        void inOrder(const m_data & d);
        void preOrder(const m_data & d);
        void postOrder(const m_data & d);
};
#endif

接下来，我必须创建BSTNode.cpp文件。感谢您通过邮件回复到jediknight80n@hotmail.com，提前感谢。

Answer 1

您似乎忘记了对在各种方法中使用的类型m_data执行typedef操作，我不明白为什么需要一个单独的tree_node结构(而不是使用类本身？)也不知道为什么getData应该返回BSTNode而不是int。

Answer 2

   //Inserts a value into a BST, public function
    void insert(const m_data & d);
    //Removes a value from a BST, public function
    void remove(const m_data & d);
    //isEmpty function, public function
    bool isEmpty();
    BSTNode getData();
    void inOrder(const m_data & d);
    void preOrder(const m_data & d);
    void postOrder(const m_data & d);

m_data是成员，而不是类型。你应该在这里使用int。此外，由于您的节点是tree_node，外部类可能应该将树表示为一个整体(即，BSTree而不是BSTNode)。

同样，“使用名称空间std；”在头文件中也是邪恶的，因为它将它强加于包括头文件在内的任何东西上，并且没有办法退出。如果你打算使用它，我建议你把它保存在.cpp文件中。

Answer 3

一些琐碎的事情：

tree_node *left;   // left subtree has smaller elements

一般来说，左子树也包含相等的元素。