Ошибка в алгоритме поиска

[_Ч_]

очень странно. это точно весь код? если у вас там в после вставки node2 в рут вставляется еще что-то и вы это не показали, то возможно проблема как раз с перераспределением памяти в векторе.
deque<tree_node> уже есть. #include <deque>. если перед deque написать std:: то форум это заменяет на смайлик

[murzilka6002]

Сделал замены, как бы всё уже хорошо...но выдает вновь ошибку памяти. Начиная с третьего уровня что-то не так, до - всё работает ок, а дальше какая-то ошибка памяти.

PHP код:

#include <cstdlib>
#include <iostream>
#include <vector>
#include <string>
#include <deque>

using namespace std;

//Class drzewa
class tree_node
       {
       public:
        int id;                                        //Numer
        string data;                                   //zawartosc
        deque <tree_node> children;                   //dzieci
        };

//Funkcja wyszukiwania
void szukaj(tree_node& t, string& s)
{
         if (t.data==s)                                //Wyszuk
            {
             cout<<"id= "<< t.id<<"\t";                //Wywod wyszukiwania
            }           
         for(int i=0; i<t.children.size();i++)         //Sprawdzanie wezla
                {
                 szukaj(t.children[i],s);
                }
}

        
int main(int argc, char *argv[])
{
    
tree_node root;
root.id=1;
root.data="Ivan";

tree_node node2;
node2.id=2;
node2.data="Dawid";
root.children.push_back(node2);
tree_node& node2Ref = root.children.back();

tree_node node3;
node3.id=3;
node3.data="Andrzej";
root.children.push_back(node3);
tree_node& node3Ref = root.children.back();

tree_node node4;
node4.id=4;
node4.data="Swieta";
root.children.push_back(node4);
tree_node& node4Ref = root.children.back();

tree_node node5;
node5.id=5;
node5.data="Kolia";
root.children.push_back(node5);
tree_node& node5Ref = root.children.back();

tree_node node6;
node6.id=6;
node6.data="Mihal";
node2Ref.children.push_back(node6);
tree_node& node6Ref = node2.children.back();

tree_node node7;
node7.id=7;
node7.data="Ivan";
node2Ref.children.push_back(node7);
tree_node& node7Ref = node2.children.back();

tree_node node8;
node8.id=8;
node8.data="Tania";
node4Ref.children.push_back(node8);
tree_node& node8Ref = node4.children.back();

tree_node node9;
node9.id=9;
node9.data="Andrzej";
node4Ref.children.push_back(node9);
tree_node& node9Ref = node4.children.back();

tree_node node10;
node10.id=10;
node10.data="Olia";
node5Ref.children.push_back(node10);
tree_node& node10Ref = node5.children.back();

tree_node node11;
node11.id=11;
node11.data="Sasza";
node5Ref.children.push_back(node11);
tree_node& node11Ref = node5.children.back();

tree_node node12;
node12.id=12;
node12.data="Tania";
node5Ref.children.push_back(node12);
tree_node& node12Ref = node5.children.back();

tree_node node13;
node13.id=13;
node13.data="Kolia";
node7Ref.children.push_back(node13);
tree_node& node13Ref = node7.children.back();

tree_node node14;
node14.id=14;
node14.data="Tania";
node10Ref.children.push_back(node14);
tree_node& node14Ref = node10.children.back();

tree_node node15;
node15.id=15;
node15.data="Swieta";
node10Ref.children.push_back(node15);
tree_node& node15Ref = node10.children.back();

tree_node node16;
node16.id=16;
node16.data="Dawid";
node12Ref.children.push_back(node16);
tree_node& node16Ref = node12.children.back();

tree_node node17;
node17.id=17;
node17.data="Wiktor";
node12Ref.children.push_back(node17);
tree_node& node17Ref = node12.children.back();

tree_node node18;
node18.id=18;
node18.data="Ania";
node12Ref.children.push_back(node18);
tree_node& node18Ref = node12.children.back();


////////////////Wyszukiwanie//////////////////////////

string szuk;

cin>>szuk;
szukaj(root,szuk);
cout<<endl;

    system("PAUSE");
    return EXIT_SUCCESS;
} 


[_Ч_]

node2Ref.children.push_back(node6);
tree_node& node6Ref = node2.children.back();

рефы надо использовать везде
т.е. это поменять на

node2Ref.children.push_back(node6); 
tree_node& node6Ref = node2Ref.children.back();

и в других похожих местах

учитесь пользоваться дебагером. он сразу показывает место, коде криво.

+ я сразу не заметил такую штуку:
странно, что это компилится. структура tree_node содержит контейнер tree_node а не указателей на них. вот это мне не понятно почему компилится. ну раз компилится, то компилится

[_Ч_]

вектор оказался хитрым. студия с ним компилит. а вот с деком уже нет.
вот простой пример с возможностью поиметь проблемы при перераспределении памяти и не везде собирающийся

#include <cstdlib>
#include <iostream>
#include <vector>
#include <string>
#include <deque>
#include <memory>

using namespace std;

struct tree_node
{
  int id;
  string data;
  vector<tree_node> children;

  tree_node(int theId, string theData)
    : id(theId)
    , data(theData)
  {
  }

  tree_node& add_node(const tree_node& node)
  {
    children.push_back(node);
    return children.back();
  }
};

//Funkcja wyszukiwania
void szukaj(tree_node& t, string& s)
{
  if (t.data==s)
  {
    cout<<"id= "<< t.id<<"\t";
  }

  for (unsigned i=0; i<t.children.size();i++)
  {
    szukaj(t.children[i],s);
  }
}

void printTree(tree_node& tree, int indent = 0)
{
  cout << std::string(indent, ' ');
  cout << '(' << tree.id << " , " << tree.data << ')';
  cout << endl;
  for (unsigned i = 0; i < tree.children.size(); ++i)
    printTree(tree.children[i], indent + 4);
}

int main(int argc, char *argv[])
{
  cout << "size of tree_node = " << sizeof(tree_node) << endl;

  tree_node root(1, "Root");
  tree_node& node2Ref = root.add_node(tree_node(2, "node2"));
    tree_node& node6Ref = node2Ref.add_node(tree_node(6, "node6"));
    tree_node& node7Ref = node2Ref.add_node(tree_node(7, "node7"));
      tree_node& node13Ref = node7Ref.add_node(tree_node(13, "node13"));
  tree_node& node3Ref = root.add_node(tree_node(3, "node3"));
  tree_node& node4Ref = root.add_node(tree_node(4, "node4"));
    tree_node& node8Ref = node4Ref.add_node(tree_node(8, "node8"));
    tree_node& node9Ref = node4Ref.add_node(tree_node(9, "node9"));
  tree_node& node5Ref = root.add_node(tree_node(5, "node5"));
    tree_node& node10Ref = node5Ref.add_node(tree_node(10, "node10"));
      tree_node& node14Ref = node10Ref.add_node(tree_node(14, "node14"));
    tree_node& node11Ref = node5Ref.add_node(tree_node(11, "node11"));
    tree_node& node12Ref = node5Ref.add_node(tree_node(12, "node12"));
      tree_node& node15Ref = node12Ref.add_node(tree_node(15, "node15"));
      tree_node& node16Ref = node12Ref.add_node(tree_node(16, "node16"));
      tree_node& node17Ref = node12Ref.add_node(tree_node(17, "node17"));
      tree_node& node18Ref = node12Ref.add_node(tree_node(18, "node18"));

  cout << "-----------------------------------------------" << endl;
  printTree(root);
  cout << "-----------------------------------------------" << endl;

  string szuk = "node18";
  szukaj(root, szuk);
  cout<<endl;

  system("PAUSE");
  return EXIT_SUCCESS;
}

[murzilka6002]

Большое спасибо! Всё работает

[_Ч_]

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

разбирайтесь.

#include <cstdlib>
#include <iostream>
#include <vector>
#include <string>
#include <deque>
#include <memory>

using namespace std;

struct tree_node
{
  int id;
  string data;
  vector<tree_node*> children;

  tree_node(int theId, string theData)
    : id(theId)
    , data(theData)
  {
  }

  tree_node(const tree_node& other)
  {
    id = other.id;
    data = other.data;
    for (unsigned i = 0; i < other.children.size(); ++i)
      add_node(*other.children[i]);
  }

  tree_node& operator = (const tree_node& other)
  {
    tree_node node(other);
    swap(node);
    return *this;
  }

  ~tree_node()
  {
    for (unsigned i = 0; i < children.size(); ++i)
      delete children[i];
  }

  tree_node& add_node(const tree_node& child)
  {
    std::auto_ptr<tree_node> node(new tree_node(child));
    children.push_back(node.get());
    node.release();
    return *children.back();
  }

  void swap(tree_node& other)
  {
    std::swap(id, other.id);
    std::swap(data, other.data);
    std::swap(children, other.children);
  }
};

//Funkcja wyszukiwania
void szukaj(tree_node& t, string& s)
{
  if (t.data==s)
  {
    cout<<"id= "<< t.id<<"\t";
  }

  for (unsigned i=0; i<t.children.size();i++)
  {
    szukaj(*t.children[i],s);
  }
}

void printTree(tree_node& tree, int indent = 0)
{
  cout << std::string(indent, ' ');
  cout << '(' << tree.id << " , " << tree.data << ')';
  cout << endl;
  for (unsigned i = 0; i < tree.children.size(); ++i)
    printTree(*tree.children[i], indent + 4);
}

int main(int argc, char *argv[])
{
  cout << "size of tree_node = " << sizeof(tree_node) << endl;

  tree_node root(1, "Root");
  tree_node& node2Ref = root.add_node(tree_node(2, "node2"));
    tree_node& node6Ref = node2Ref.add_node(tree_node(6, "node6"));
    tree_node& node7Ref = node2Ref.add_node(tree_node(7, "node7"));
      tree_node& node13Ref = node7Ref.add_node(tree_node(13, "node13"));
  tree_node& node3Ref = root.add_node(tree_node(3, "node3"));
  tree_node& node4Ref = root.add_node(tree_node(4, "node4"));
    tree_node& node8Ref = node4Ref.add_node(tree_node(8, "node8"));
    tree_node& node9Ref = node4Ref.add_node(tree_node(9, "node9"));
  tree_node& node5Ref = root.add_node(tree_node(5, "node5"));
    tree_node& node10Ref = node5Ref.add_node(tree_node(10, "node10"));
      tree_node& node14Ref = node10Ref.add_node(tree_node(14, "node14"));
      tree_node& node15Ref = node10Ref.add_node(tree_node(15, "node15"));
    tree_node& node11Ref = node5Ref.add_node(tree_node(11, "node11"));
    tree_node& node12Ref = node5Ref.add_node(tree_node(12, "node12"));
      tree_node& node16Ref = node12Ref.add_node(tree_node(16, "node16"));
      tree_node& node17Ref = node12Ref.add_node(tree_node(17, "node17"));
      tree_node& node18Ref = node12Ref.add_node(tree_node(18, "node18"));

  cout << "-----------------------------------------------" << endl;
  printTree(root);
  cout << "-----------------------------------------------" << endl;

  string szuk = "node18";
  szukaj(root, szuk);
  cout<<endl;

  system("PAUSE");
  return EXIT_SUCCESS;
}