时间戳

首页 > 解决方案 > 插入函数的二叉搜索树问题

c++ - 插入函数的二叉搜索树问题

问题描述

您好，我是 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

键码对.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;
}

键码对.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;
}

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

解决方案

让我们看一下您的插入功能：

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
}

推荐阅读