帮助使用 BST 插入函数

Question

嘿，我正在尝试编写 BST，但我遇到了很多错误，而且我非常不知所措，不知道该怎么做。你们能看一下并指出任何不对的地方吗？老师在解释任何事情上根本没有多大用处。

.h 文件中的标头

class Tree
{
public:
    bool insert(int k, string s);

private:
    struct Node
    {
        int key;
        string data;
        Node *left;
        Node *right;
    };
    Node* root;
    bool insert(Node *& root, int k, string s);
};

.cpp 文件

bool Tree::insert(int k, string s)
{
    return insert(root, k, s);
}
bool Tree::insert (Node *& root, int k, string s)
{
    if (root == NULL){
        root = new Node;
        root->key = k;
        root->data = s;
        root->left = NULL;
        root->right = NULL;
    }
    else if (root == k)
        return false;
    else if (root->key < k)
        insert (root ->left, k);
    else
        insert (root -> right, k);
}

Answer 1

看来您有很多未经测试的代码。您必须一次让一项功能发挥作用。

此外，我已经看到至少一个重复工作的例子。 preOrder 和 postOrder 方法应该是同一算法的轻微变体，但一个是基于循环的，另一个是通过函数递归工作的。

将这些源文件放在一边，创建一个新项目，然后一次复制粘贴一个功能。在继续下一个功能之前进行彻底测试。如果您遇到现有代码中可能已经隐藏的功能，请不要从旧代码中复制粘贴，而是利用现有的经过测试的代码。

编辑

这看起来应该可行。如果您需要的话，这里有一些风格上的批评：v)。

1. Node 结构应该有自己的构造函数。始终提供构造函数来帮助保证任何内容都不会处于无效状态。
2. 同样，当您创建新的Tree 时，需要将root 设置为NULL。
3. 更改 root 参数的值并不是一个好的风格。乍一看，left 和 right 似乎永远不会接收非 NULL 值。就我个人而言，我更喜欢这里使用指针到指针，但有些人可能会同意您的实现。

Answer 2

一方面，代码末尾缺少括号。

Answer 3

如果不考虑实际的实现，就会发现有很多与接口相关的陷阱。以下是其中一些：

• 您在头文件中缺少包含防护。
• 在包含的头文件的全局范围内说“使用命名空间 std”是允许的，但它的风格非常糟糕。
• Tree::findKey 方法接受字符串作为非常量引用，为什么？
• Tree::insert 按值接受字符串，这涉及到不必要的复制，有什么用呢？
• preOrder 和 levelOrder 需要指向函数的指针。如果我想调用类方法或传递附加参数怎么办？我想说你最好在那里使用谓词，或者 boost::function。
• 不修改状态（类内的数据）的方法不是常量（const 修饰符）。例如，isEmpty()方法。
• makeCopy 方法不是异常安全。
• 使用有符号整数代替 size_t。

希望有帮助。

Answer 4

编写你的第一个 BST 可能很困难......根据 Potatoswatter 的建议，我首先要确保你有一个非常可靠的插入函数，然后再去其他地方。因此，您可以为 BST 创建类，包括函数的声明，但在它们的定义中，只需将它们设为空函数，例如：

在头文件中：

class BST
{
    public:
        BST();
        bool insert(int k, const string& s);
        bool findKey(int k, string& s);
        int maxKey();

        /* ... the rest of your class ...*/
};

在 .cpp 文件中：

#include "BST.h"

BST::BST()
{
    /*initialize anything required for your insert function to work*/
}

//pass in a const reference for your string argument, 
//or else you could end up doing a lot
//of extra processing creating a new copy of your string on the stack for
//each insertion call
bool BST::insert(int k, const string& s)
{
    /* write your insertion algorithm implementation */
}

//make the rest of your function definitions that don't
//apply to insertion empty so you can compile and test your insertion algorithm
//without adding more cruft
bool BST::findKey(int k, string& s) {}

int BST::maxKey() {}

/* continue process for the rest of the class */

现在使用这种方法，您可以测试确保您正确地将节点插入到树中而不会崩溃等，完成后，您可以测试是否可以找到已插入的节点。之后，您可以完成其余函数的定义，这些函数负责删除、迭代等。但是，通过将每个阶段不需要的函数的定义留空，您可以正确构建解决方案，而无需一堆编译器错误和其他不相关的项目使您无法为手头的任务构建实际的界面。换句话说，您无法从一开始就没有正确插入节点的树中找到或删除节点而不会出现问题，因此当您第一步还没走对。此外，您可能会发现，当您实现后续步骤（例如查找节点）时，仍然存在插入问题...如果您只实现了插入和查找节点的完整定义，那么这些是您唯一的两个函数我们将不得不担心修复问题。

因此，将其分解为基本部分（插入、查找、删除，然后是其他所有部分），然后您就可以完成工作了:-)