2

我有一个关于 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 提前致谢。

4

9 回答 9

3

你似乎忘记了你在各种方法中使用typedef的类型m_data，我不明白你为什么想要一个单独的tree_node结构（而不​​是使用类本身？）也不明白为什么getData要 returnBSTNode而不是int.

于 2009-05-18T04:27:55.093 回答
3 
   //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）。

还有“使用命名空间标准；” 标题是邪恶的，因为它会强制包含标题的任何内容而无法选择退出。如果您要使用它，我建议将其保存为 .cpp 文件。

于 2009-05-18T04:31:21.227 回答
2

一些琐碎的事情：

tree_node *left;   // left subtree has smaller elements

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

于 2009-05-18T05:19:16.197 回答
1

这是一个关于 BST 的经典问题——任何关于数据结构的好书都会给你完整的代码。以下页面包含 C++ http://cslibrary.stanford.edu/110/BinaryTrees.html的代码示例。

遍历函数不应该是 BST 类本身的一部分，实际上 BSTNode 应该公开左/右节点指针 - 调用应用程序应该以特定方式调用它。或者使用回调函数并在您的类中提供遍历代码，这样会更干净。

于 2009-05-18T04:31:41.040 回答
1

几件事-正如其他人指出的那样，您将不得不使用

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

另一件事是你已经注释掉了你的根节点。尽管您定义错误，但您必须在类中包含一个根节点。正确的定义是

tree_node *root;

此外，如前所述，删除

使用命名空间标准；

从头文件中取而代之，将其放入您的实现文件中。

这就是我现在所能看到的。

于 2009-05-18T04:45:29.173 回答
1

另一个问题是指定的类声明了嵌套类型和方法，但没有成员数据。

您可以使用迭代器声明遍历功能：例如 preorder 方法返回一个 interator，您可以取消对节点的引用，或者递增以指向 preorder 序列中的下一个节点。

或者，您可以使用回调声明遍历功能：即调用者将回调实例传递给预排序方法，预排序方法遍历树并为每个节点调用回调方法：回调方法将采用一个节点（或者，更具体地说，节点数据）作为参数，并可能返回一个布尔值，让回调指定它想要终止遍历。

于 2009-05-18T04:46:41.390 回答
1

我也会添加一个搜索方法。

bool search(int whatIlookfor);

甚至更好

tree_node* search(int whatIlookfor);

另外，请保存tree_node *root在安全的地方。

于 2009-05-18T04:48:37.677 回答
1

  • 在您的示例中使用结构类型的左右指针会限制灵活性 - 假设我采用您的 BST 并遍历根的左子节点，然后想要在这个新子树上调用操作。我不能，因为指针是结构类型的。我宁愿建议使用 BSTNode 类型的两个指针。

    BSTNode *left;

    BSTNode *right;

    这也将解决您的根问题（不需要显式根指针），因为您用于在 main 中引用对象的指针无论如何都会指向根。

  • 遍历函数应该不需要任何参数，因为它们本质上会遍历整个树并打印所有数据项。数据项可以传递给另一个搜索成员函数以搜索其位置，正如 TrueStar 已经指出的那样。

  • 我还建议使用一些私有成员函数来降低公共成员函数的复杂性（DeleteNodeCaseB(int data)会DeleteNodeCaseA(int data)一次又一次地调用）-

    BSTNode * setleft(int data);

    BSTNode * setright(int data);

    void DeleteNodeCaseA(int data) /* 左右孩子中的一个或两个都不存在 */

    void DeleteNodeCaseB(int data) /* 有左右孩子 */

于 2009-05-18T05:22:41.733 回答
1

由于您使用的是 C++，您可能要考虑使用一些标准库而不是尝试自己实现它？STL 库带有一个红黑树，它可能更适合您的应用程序。二叉树可能会变得不平衡或退化为链接列表。

PS：当然，这是假设你没有做家庭作业。

于 2009-05-18T05:26:19.577 回答