c++ - 二分探索木問題

Question

「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;
}

Answer 1

addは非静的メンバー関数です。つまり、のインスタンスでのみ呼び出すことができますCTree。例えば

CTree myTree;
myTree.add(num);

Answer 2

クラスを実際に使用するには、クラスのインスタンスが必要であることを認識していますか? CTreeクラスのインスタンスを操作しているという前提で全体を書きました。設計図ではなく実際の木です。

前に答えたように、それは静的関数でもクラスレベルでもありません。非静的メソッドをインスタンスで呼び出す必要があるため、サイレント ポインターthisを意味のあるものに設定できます。作業している実際のインスタンス - この場合はノードを追加します。

補遺

（以下のすべては、コードを変更せずに機能します。質問に対する明示的な回答で、コンパイルできます。「作業の観点から」、このプログラムは完全にはほど遠いです。いくつかの部分は意味をなさず、多くの変数は未使用のままですまたは初期化されていません（そして使用されます。以下でさらに詳しく説明しましょう。）

あなたがする必要があるのは、古い process() 呼び出しが発生したメインにこれ​​を追加することです:

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

関数プロセスの引数リストを変更して、操作したいツリーへの参照を含めます。これは可能性の 1 つにすぎません。ポインターなどを使用することもできます。ただし、参照の方がクリーンです。

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

また、コンパイラの警告にも注意してください。それらのすべてを処理することをお勧めします。そして覚えておいてください、これは動作ではなくコンパイルになります。端が未完成でラフに見えます。

そして、クラス (アイデア) とインスタンス (そのアイデアの具現化) の違いを思い出してください。技術的な詳細は今のところ重要ではありません。クラスの設計が意図するように、使用するインスタンスがあることを確認してください。あなたは、コンピュータ ソフトウェアがどのように機能するか、ソフトウェア上で動作するデータと命令がどのように接続されるかについて、特にメモリの観点から、把握していないように思えます。コンピューターが何をしたいのかを知るだけでは十分ではありません。操作を実行したい内容 (どの変数またはオブジェクト、または何を持っているか) を知る必要があります。値でコピーして返すことができ、メイン関数でそれを行い、アドレスを含む参照またはポインターを渡して、オブジェクト/インスタンスがメモリ内のどこにあるかを知ることができます。実験だけの場合は、グローバルインスタンス。多くのオプション。

すべてを再宣言しても、以前に発生した変更は引き継がれません (範囲外になるため)。クラス レベルで非静的メンバー メソッドを呼び出すことも意味がありません。

それが役に立ち、幸せなコーディングを願っています。やりがいのあることは何も簡単ではありません。

Answer 3

あなたの経験レベルに対して、彼らは少し技術的になりすぎていると思います。CTree クラスのコードは、CTree クラスとは何か、どのように動作するか (青写真) を作成しますが、実際には、コードにクラスを構築するように指示し、それを参照する方法を用意する必要があります。

次のようにスタック変数インスタンスを宣言できます。

CTree myTree;  

これにより、クラスにメモリが割り当てられ、関数へのエントリでコンストラクターが呼び出されます。次に、ドット表記を使用してインスタンス名から関数を参照することで、それを操作します。

myTree.Add(4);

または、CTree へのポインターを宣言し、new 演算子を使用して動的インスタンスを作成することもできます。

CTree *myTree;

myTree = new CTree();

次に、ポインター表記を使用してツリーを参照します。

myTree->Add(4);

そのようにすると、割り当てたメモリを削除する必要があります

delete myTree;

要約すると、ここに示す種類のクラス定義はクラスを記述しますが、クラスを作成しません (メモリを割り当て、メソッド コードへのポインターをセットアップします)。これにより、コード ロジックで必要な場合に多くのツリーを持つことができます。

CTree directoryTree;
CTree fileTree;
CTree indexTree;

これらはそれぞれ独自のデータを持っています...

幸運を、