Как заменить узел в бинарном дереве поиска - PullRequest
Новая
       12

Как заменить узел в бинарном дереве поиска

0 голосов
/ 04 июня 2019

У меня есть двоичное дерево поиска со строками. Каждый узел содержит строку и частоту строки.

Моя функция имеет две строки: s1, s2. Я должен заменить s1 на s2. Если s2 уже существует в bstree, мне просто нужно добавить частоту s1.Если его нет, я создаю новый узел с частотой s1.

То, что я сделал, это: (1) я удаляю s1 из bstree и сохраняю частоту s1 (2) Я вставляю s2 в bstree (используя частоту s1)

Проблема в том, что пока (1) работает и узел s1 удален вторая часть ничего мне не дает (когда я запускаю ее без функции удаления, она дает мне некоторые странные символы) 

struct node{
    string data;
    int freq;
    node *left, *right;
    node(string d, int f){
        data = d;
        freq = f;
        left = right = nullptr;
    }

node *replacehelp(node *r, string v, int f){
        if(r == nullptr)
            return new node(v,f);

        int state = v.compare(r->data);//to check the alphabetical order

        if(state == 0){
            r->freq += f;
            return r;
        }
        if(state > 0)
            r->right = replacehelp(r->right, v, f);
        else if(state < 0)
            r->left = replacehelp(r->left, v, f);
    }

void replace(const string &s1, const string &s2){
    //the delete function works(I get the freq of s1)
    root = DeleteNode(root, s1, &freq);
    //I have to insert s2 to the tree
    root = replacehelp(root,s2,freq);
}

1 Ответ

1 голос
/ 04 июня 2019

Ваша проблема возникает из-за того, что return отсутствует в replacehelp .

Обратите внимание, что проверка (state < 0) бесполезна в replacehelp , посколькуоно не равно 0 и не является положительным, поэтому 

node *replacehelp(node *r, string v, int f){
  if(r == nullptr)
    return new node(v,f);

  int state = v.compare(r->data);//to check the alphabetical order

  if(state == 0)
    r->freq += f; 
  else if(state > 0) // 'else' ADDED
    r->right = replacehelp(r->right, v, f);
  else // MODIFIED
    r->left = replacehelp(r->left, v, f);

  return r;
}

Вы не дадите определение DeleteNode , поэтому невозможно узнать, правильно ли это, как вы предполагаете.

Если я добавлю некоторые определения для запуска: 

#include <iostream>
#include <string>

using namespace std;

struct node{
  string data;
  int freq;
  node *left, *right;
  node(string d, int f){
    data = d;
    freq = f;
    left = right = nullptr;
  }
};

node *replacehelp(node *r, string v, int f){
  if(r == nullptr)
    return new node(v,f);

  int state = v.compare(r->data);//to check the alphabetical order

  if(state == 0)
    r->freq += f;
  else if(state > 0) // 'else' ADDED
    r->right = replacehelp(r->right, v, f);
  else  // MODIFIED
    r->left = replacehelp(r->left, v, f);

  return r; // ADDED
}

// ADDED
node * DeleteNode(node *r, string s, int * freq) // can be "int & freq" to not have to give the addr in the call
{
  if (r != nullptr) {
    int state = s.compare(r->data);

    if (state > 0)
      r->right = DeleteNode(r->right, s, freq);
    else if (state < 0)
      r->left = DeleteNode(r->left, s, freq);
    else {
      *freq = r->freq;

      if (r->right == nullptr) {
        node * t = r->left;

        delete (r);
        return t;
      }

      if (r->left == nullptr) {
        node * t = r->right;

        delete (r);
        return t;
      }

      node * t = r->right;

      while ((t != nullptr) && (t->left != nullptr))
        t = t->left;

      r->data = t->data;
      r->freq = t->freq;

      int dummy;

      r->right = DeleteNode(r->right, t->data, &dummy);
    }
  }

  return r;
}

node * root; // ADDED

void replace(const string &s1, const string &s2){
  int freq = 0; // initialized to 0 to not have undefined value if DeleteNode do not find the node
  //the delete function works(I get the freq of s1)
  root = DeleteNode(root, s1, &freq);
  //I have to insert s2 to the tree
  root = replacehelp(root,s2,freq);
}

// ADDED
void insert(string s, int freq)
{
  root = replacehelp(root, s, freq);
}

// ADDED
void pr(node *r)
{
  cout << '(';
  if (r != nullptr) {
    pr(r->left);
    cout << '"' << r->data << "\" " << r->freq;
    pr(r->right);
  }
  cout << ')';
}

// ADDED
int main(void)
{
  insert("5", 5);
  insert("4", 4);
  insert("3", 3);
  insert("6", 6);

  pr(root);
  cout << endl;

  replace("5", "55");

  pr(root);
  cout << endl;

  replace("3", "33");

  pr(root);
  cout << endl;

  replace("4", "33");

  pr(root);
  cout << endl;
}

Компиляция и выполнение: 

pi@raspberrypi:/tmp $ g++ -g -pedantic -Wextra -Werror t.cc
pi@raspberrypi:/tmp $ ./a.out
(((()"3" 3())"4" 4())"5" 5(()"6" 6()))
(((()"3" 3())"4" 4(()"55" 5()))"6" 6())
(((()"33" 3())"4" 4(()"55" 5()))"6" 6())
(((()"33" 7())"55" 5())"6" 6())
pi@raspberrypi:/tmp $
...