Проблема с двоичным деревом поиска

Я действительно застрял, я получаю сообщение об ошибке "CTree.add(num);" говоря, что «CTree» не объявлен, что не имеет смысла, потому что я инициализировал его в tree.h?

Программа должна предлагать пользователю, пользователь вводит команду (например, «добавить 3», только целые числа 0-9), а затем я хочу, чтобы он вставил это число в дерево.

//File: tree.h

class CTree
{
private:
    CTree* m_pLeft;
    CTree* m_pRight;
    CTree* m_pRoot;
    int m_nData;

public:

    CTree();

    bool isEmpty() const { return m_pRoot; }
    bool search(int);
    void print_inorder();
    void inorder(CTree*);
    void Add(int);
    void remove(int);
    void height();
};

//File: CTree.cpp

#include <iostream>
#include <cstdlib>

using namespace std;

CTree::CTree()
{
 m_pRoot=NULL;
}

bool CTree::search(int x)
{
    if(x==m_nData) return true;
    if(x < m_nData){ //go left
       if(m_pLeft != NULL) //if possible
            return m_pLeft->search(x);
    }
    else //go right
       if(m_pRight != NULL) //ifpossible
            return m_pRight->search(x);
    return false;
}

void CTree::Add(int x)
{
CTree* t = new CTree;
CTree* parent;
t->m_nData = x;
t->m_pLeft = NULL;
t->m_pRight = NULL;
parent = NULL;

if(isEmpty()) m_pRoot = t;
else
{
     //insert leaf nodes
    CTree* leaf;
    leaf = m_pRoot;
     // find parent
    while(leaf)
    {
        parent = leaf;
        if(t->m_nData > leaf->m_nData)
            leaf = leaf->m_pRight;
        else
            leaf = leaf->m_pLeft;
    }

    if(t->m_nData < parent->m_nData)
       parent->m_pLeft = t;
    else
       parent->m_pRight = t;
}
}

void CTree::remove(int x)
{
bool found = false;
if(isEmpty())
{
    cout<< "Tree is empty!" <<endl;
    return;
}

CTree* current;
CTree* parent;
current = m_pRoot;

while(current != NULL)
{
     if(current->m_nData == x)
     {
        found = true;
        break;
     }
     else
     {
         parent = current;
         if(x > current->m_nData) current = current->m_pRight;
         else current = current->m_pLeft;
     }
}
if(!found)
{
    cout<< "Not found!" <<endl;
    return;
}

// Node with single child
if((current->m_pLeft == NULL && current->m_pRight != NULL)|| (current->m_pLeft != NULL&& current->m_pRight != NULL))
{
   if(current->m_pLeft == NULL && current->m_pRight != NULL)
   {
       if(parent->m_pLeft == current)
       {
         parent->m_pLeft = current->m_pRight;
         delete current;
       }
       else
       {
         parent->m_pRight = current->m_pRight;
         delete current;
       }
   }
   else // left child present, no right child
   {
      if(parent->m_pLeft == current)
       {
         parent->m_pLeft = current->m_pLeft;
         delete current;
       }
       else
       {
         parent->m_pRight = current->m_pLeft;
         delete current;
       }
   }
 return;
}

             //We're looking at a leaf node
             if( current->m_pLeft == NULL && current->m_pRight == NULL)
{
    if(parent->m_pLeft == current) parent->m_pLeft = NULL;
    else parent->m_pRight = NULL;
                             delete current;

//Node with 2 children
// replace node with smallest value in right subtree
if (current->m_pLeft != NULL && current->m_pRight != NULL)
{
    CTree* check;
    check = current->m_pRight;
    if((check->m_pLeft == NULL) && (check->m_pRight == NULL))
    {
        current = check;
        delete check;
        current->m_pRight = NULL;
    }
    else // right child has children
    {
        //if the node's right child has a left child
        // Move all the way down left to locate smallest element

        if((current->m_pRight)->m_pLeft != NULL)
        {
            CTree* lcurrent;
            CTree* lcurrent_parent;
            lcurrent_parent = current->m_pRight;
            lcurrent = (current->m_pRight)->m_pLeft;
            while(lcurrent->m_pLeft != NULL)
            {
               lcurrent_parent = lcurrent;
               lcurrent = lcurrent->m_pLeft;
            }
            current->m_nData = lcurrent->m_nData;
            delete lcurrent;
            lcurrent_parent->m_pLeft = NULL;
       }
       else
       {
           CTree* tmp;
           tmp = current->m_pRight;
           current->m_nData = tmp->m_nData;
           current->m_pRight = tmp->m_pRight;
           delete tmp;
       }

    }
             return;
}
}
}

void CTree::print_inorder()
{
 inorder(m_pRoot);
}

void CTree::inorder(CTree* x)
{
  if(x != NULL)
{
    if(x->m_pLeft) inorder(x->m_pLeft);
    cout<<" "<<x->m_nData<<" ";
    if(x->m_pRight) inorder(x->m_pRight);
}
else return;
}

//File: main.cpp

#include <iostream>
#include <cstdlib>
#include <sstream>
#include <locale>
#include <string>
#define PROMPT "bst> "

using namespace std;

int getNumber(string s)
{
    int num;

for(int i; i<=s.length();i++)
{
        if(isdigit(s[i]))
        {
              num= s[i]-48;
        }
}

return num;
} // getNumber

bool process(const string& s, CTree* aTree)
{
    bool mustquit=false;
    int num;
    istringstream iss(s);

do
{
    string sub;
    iss >> sub; //               
    if(sub=="add" || sub=="insert")
    {
        num=getNumber(s);
        cout<<num<<endl;
        aTree->Add(num);
    }
    else if(sub=="delete" || sub=="remove")
    {
        num=getNumber(s);
        cout<<num<<endl;
    }
    else if(sub=="search" || sub=="find")
    {
         num=getNumber(s);
         cout<<num<<endl;
    }
    else if(sub=="height")
    {
         //do stuff
    }
    else if (sub=="quit") 
        return mustquit;
    //else cout<<"INPUT ERROR"<<endl;    
 }  while (iss);     




 return mustquit;
 }// process


int main(){ 

string input="";
CTree *myTree;
myTree = new CTree();

bool finished=false;
int i;


    cout<<PROMPT;
    while(!finished)
    {
            if(input!="")cout<<PROMPT;
            getline(cin,input);
            finished=process(input, myTree);
            delete myTree;
    }//while

return 0;
}

person conman    schedule 05.04.2012    source источник
comment
на самом деле вы никогда не создаете экземпляр CTree, вы просто объявляете имя переменной в своем заголовочном файле, а не создаете экземпляр.   -  person Hunter McMillen    schedule 05.04.2012


Ответы (3)


add — это нестатическая функция-член, что означает, что вы можете вызывать ее только в экземпляре CTree. например

CTree myTree;
myTree.add(num);
person Oliver Charlesworth    schedule 05.04.2012
comment
Это не сработало для меня, к сожалению. Хотя я понимаю, что вы имеете в виду. Теперь я получаю сообщение об ошибке при инициализации CTree myTree;. - person conman; 05.04.2012

Вы знаете, что вам нужен экземпляр класса CTree, чтобы его использовать? Вы написали все это, исходя из предположения, что вы работаете с экземпляром класса. Фактическое дерево, а не его чертеж.

Как сказал ответ передо мной, это не статическая функция или уровень класса. Для экземпляра необходимо вызвать нестатический метод, чтобы молчаливый указатель this мог быть установлен на что-то значимое, т.е. фактический экземпляр, с которым вы работаете - в этом случае добавление узла.

ДОПОЛНЕНИЕ

(все ниже работает без изменения вашего кода, просто явный ответ на ваш вопрос, чтобы заставить его компилироваться. С "рабочей точки зрения", эта программа далека от завершения. Некоторые части даже не имеют смысла, много переменных остаются неиспользованными или неинициализированными (а затем используются). Позвольте мне подробнее остановиться ниже.)

Что вам нужно сделать, так это добавить это в ваш main, где произошел старый вызов process():

CTree myTree; // you could also add (), even though it's a default constructor
finished=process(input, myTree);

И измените список аргументов процесса функции, чтобы включить ссылку на ваше дерево, с которым вы хотите работать. Это только одна из возможностей, вы также можете взять указатель и т. д. Но ссылка чище:

bool process(const string& s, CTree& aTree)

Также обратите внимание на предупреждения компилятора. Хорошей практикой является забота обо всех из них. И помните, это заставляет его компилироваться, а не работать. Он кажется незаконченным и грубым по краям.

И помните разницу между классом (идеей) и экземпляром (проявлением этой идеи). Технические детали сейчас не важны, просто убедитесь, что у вас есть экземпляр для работы, как это предусмотрено дизайном вашего класса. Мне кажется, что вы не понимаете, как работают компьютерные программы, как связаны данные и инструкции, которые работают с ними, особенно с точки зрения памяти. Компьютеру недостаточно знать, что вы хотите сделать, ему нужно знать, над чем вы хотите выполнять операции (какие переменные, объекты или что у вас есть). Вы можете скопировать по значению и вернуть, сделать это в основной функции, передать ссылку или указатель с адресом, чтобы он мог знать, где в памяти находится ваш объект/экземпляр и т. д. Если вы просто экспериментируете, вы можете создать глобальный экземпляр. Много вариантов.

Повторное объявление всего не переносит изменения, которые произошли ранее (поскольку вещи выходят за рамки). Также нет смысла вызывать нестатические методы-члены на уровне класса - и даже не правильно.

Надеюсь, это поможет, и приятного программирования. Продолжайте в том же духе, ничего стоящего не бывает простым.

person Community    schedule 05.04.2012
comment
Я не понимаю, экземпляр означает, что мне нужно создать указатель на каждый элемент дерева? Я думал, что сделал это в tree.h в классе CTree под приватным. - person conman; 05.04.2012
comment
Вы определили класс. Класс можно рассматривать как план, поверх которого создаются объекты. Теперь вам нужен экземпляр, как показано в примере мистера Чарльзворта. Но вам также необходимо сохранить активную ссылку на него, чтобы вы могли работать с ним. Указатель this является молчаливым аргументом для каждой нестатической функции класса, который затем помещается при каждом изменении данных члена, таких как m_intVar на this->m_intVar. Таким образом, это имеет смысл и работает с правильным смещением памяти (или с правильным объектом/экземпляром). Проверьте редактирование моего ответа, которое заставляет ваш код компилироваться. - person ; 05.04.2012
comment
вздох, я просто переключаюсь с C на C++, поэтому прошу прощения за краткость моего программирования. Я отредактировал код, и он компилируется. Так что большое спасибо только за это. Но я все еще получаю ошибки времени выполнения - person conman; 07.04.2012

Я думаю, что они становятся слишком техническими для вашего уровня опыта. Код вашего класса CTree определяет, что такое класс CTree и как он себя ведет (чертеж), но на самом деле вы должны сказать своему коду, чтобы создать его, а затем иметь способ сослаться на него.

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

CTree myTree;  

Это выделяет память для вашего класса и вызывает конструктор при входе в функцию. Затем вы будете работать с ним, ссылаясь на функции из имени экземпляра, используя запись через точку.

myTree.Add(4);

Или вы можете объявить указатель на CTree и создать динамический экземпляр, используя новый оператор

CTree *myTree;

myTree = new CTree();

Затем вы ссылаетесь на дерево, используя нотацию указателя:

myTree->Add(4);

если вы сделаете это таким образом, вам нужно будет удалить выделенную вами память

delete myTree;

Таким образом, определение класса, показанное здесь, описывает класс, но не создает его (выделяет память и устанавливает указатели на код метода). Это позволяет вам иметь много деревьев, если этого требует логика вашего кода;

CTree directoryTree;
CTree fileTree;
CTree indexTree;

У каждого будут свои данные...

Удачи,

person Jeff D.    schedule 05.04.2012
comment
вздох Я просто переключаюсь с C на C++, поэтому прошу прощения за краткость моего программирования. Я отредактировал код, и он компилируется. Так что большое спасибо только за это. Но я все еще получаю ошибки времени выполнения. - person conman; 05.04.2012