Проблема дерева двоичного поиска с функцией вставки

Question

Здравствуйте, я новичок в c ++ и изучаю бинарные деревья поиска. Я пытаюсь реализовать простое двоичное дерево поиска, где я могу хранить объект «KeyCodePair» (который содержит строку и целое число) и выполнять некоторые операции с деревом, такие как поиск и вставка. Похоже, с моей логикой есть некоторые проблемы, поэтому первая функция Вставка работает, но вторая не работает (вызывая их из 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);
    }
}

tree.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

Проблема в том, что ваша вставка учитывает только корневой узел. Вам нужно пройти вниз по дереву до точки, где вы делаете вставку:

class Tree {
   ...
public:
    treeNode* Insert(KeyCodePair data);
    ...
};

Шаг 1: Измените ваш интерфейс

class Tree {
   ...
    // The insert that does the work
    // We pass in the current position in the tree.
    treeNode* Insert(treeNode* node, KeyCodePair data);
public:

    // The public interface that accepts the data and calls the internal Insert
    void Insert(KeyCodePair data);
    ...
};

Шаг 2. Используйте общедоступную вставку для вызова внутренней вставки.

void Tree::Insert(KeyCodePair data) {
    // Use the internal Insert() passing the root as the starting point.
    // If a new value is needed it will be returned otherwise the original
    // value is returned.
    root = Insert(root, data);
}

Шаг 3. Измените вставку OP во внутреннюю вставку.

Tree::treeNode* Tree::Insert(treeNode* node, KeyCodePair data) {
    if (node == NULL) { 
        // If we have reached the tip of the tree then
        // return the new node so it can be inserted.
        return getNewNode(data);
    }

    // Otherwise we have a node so we need to find the node
    // were the data will be inserted.
    // so move to the next level. Assign the result as the next
    // level could be null.
    if (data.getCode() <= root->data.getCode()) {
        node->left  = Insert(node->left,  data);
    }
    else {
        node->right = Insert(node->right, data);
    }

    // Return this node
    // So it stays in the chain.
    return node;
}

Answer 2

Давайте посмотрим на вашу функцию вставки:

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
}