c++ - 具有插入功能的二叉搜索树问题

Question

你好，我是 C++ 的新手，正在学习二叉搜索树。 我正在尝试实现一个简单的二叉搜索树，我可以在其中存储“KeyCodePair”对象(具有字符串和整数)并对树执行一些操作，例如搜索和插入。似乎我的逻辑有一些问题，这就是为什么第一个 Insert 函数工作但第二个不工作(从 Main 调用它们)我想我实现“root”的方式有问题我应该在哪里写

这是 Tree.cpp:

#include "Tree.h";
#include "KeyCodePair.h";
Tree::Tree() {
    treeNode* root = NULL;
}
Tree::treeNode* Tree::getNewNode(KeyCodePair data) {

    treeNode* newNode = new treeNode();
    newNode->data = data;
    newNode->left = newNode->right = NULL;
    return newNode;
}
   Tree::treeNode* Tree::Insert(KeyCodePair data) {
    if (root == NULL) { 
        root = getNewNode(data);
    }
    else if (data.getCode() <= root->data.getCode()) {
        root->left = Insert(data);
    }
    else {
        root->right = Insert(data);
    }
    return root;
}
bool Tree::Search(KeyCodePair data) {
    if (root == NULL) {
        return false;
    }
    else if (root->data.getCode() == data.getCode()) {
        return true;
    }
    else if (data.getCode() <= root->data.getCode()) {
        return Search(data);
    }
    else {
        return Search(data);
    }
}

树.h:

#ifndef TREE_H
#define TREE_H
#include "KeyCodePair.h"
class Tree {
private:
     struct treeNode {
        KeyCodePair data;
        treeNode* left;
        treeNode* right;
    } ;
     treeNode* root;
public:
    treeNode* Insert( KeyCodePair data);
    bool Search(KeyCodePair data);
    treeNode* getNewNode(KeyCodePair data);
    Tree();
};
#endif

KeyCodePair.cpp

#include "KeyCodePair.h"
KeyCodePair::KeyCodePair(string keyparam, int codeparam) {
    key = keyparam;
    code = codeparam;
}
KeyCodePair::KeyCodePair() {

}
string KeyCodePair::getKey() {
    return key;

}
int KeyCodePair::getCode() {
    return code;
}

KeyCodePair.h

#ifndef KEYCODEPAIR_H
#define KEYCODEPAIR_H
#include <iostream>

using namespace std;

class KeyCodePair {
private:
    string key;
    int code;
public:
    KeyCodePair();
    KeyCodePair(string key, int code);
    string getKey();
    int getCode();

};

#endif

最后这是主要的:

#include <iostream>
#include <string>
#include "Tree.h"
#include "KeyCodePair.h"
using namespace std;
int main()
{
    Tree tree =  Tree();
    KeyCodePair testPair =  KeyCodePair("teststring1",10);
    KeyCodePair qwePair = KeyCodePair("teststring2", 20);
    cout << tree.Insert(testPair) << endl;
    cout << tree.Insert(qwePair) << endl; // problem on second insert

    if (tree.Search(testPair) == true) cout << "Found\n";
    else cout << "Not Found\n";
    cin.get();

    return 0;
}

Answer 1

让我们看一下您的插入函数:

Tree::treeNode* Tree::Insert(KeyCodePair data) {
    if (root == NULL) { 
        root = getNewNode(data);
    }
    else if (data.getCode() <= root->data.getCode()) {
        root->left = Insert(data);
    }
    else {
        root->right = Insert(data);
    }
    return root;
}

您在这里所做的是接收要插入的数据，然后查看根。如果没有根，则添加一个包含数据的新节点并将其分配给根(这就是您的第一个插入有效的原因)。但是，一旦有了根，您就可以确定新节点应该放在根的左侧还是右侧，然后使用相同的数据递归调用 Insert()。对 Insert 的下一次调用不会做任何不同的事情，并一遍又一遍地查看树的同一个根，很可能会产生无限循环。

你要做的就是使用你的数据，首先沿着树一直向下遍历到你想要插入你的节点的位置，然后插入它并分配指针。一些代码可能如下所示:

Tree::Insert(KeyCodePair data) {
    // currPos will end up being the position where we want to insert
    Tree::treeNode* currPos = root;
    while (currPos != NULL) {
        if (data.getCode() <= currPos->data.getCode())
            currPos = currPos->left;
        else if (data.getCode() > currPos->data.getCode())
            currPos = currPos->right;
    }

    // Insert at currPos and reassign the left or right pointer of 
    // the parent
}