2

C++ での二分探索ツリーの実装に関して質問があります。以下、質問です

整数を格納する単純な (テンプレート化されていない) BST を実装します。次の操作を提供します: Insert、Remove、inOrder トラバーサル、preOrder トラバーサル、postOrder トラバーサル。

ツリーの処理には再帰ルーチンを使用します。

ノードを処理するには、ノードの内容を出力するだけです。この場合は、ノードに格納されている整数です。

データはテスト ファイルから取得する必要があります。メイン プログラムは、データ ファイルを開いてツリーに挿入し、他のツリー操作を実演する必要があります。

この演習のポイントは、BST を理解していることを示すことです。やり過ぎて、求められていない操作を行う必要はありません。

これまでのところ、ヘッダー ファイルのみを作成しました。誰かが見て、私が正しい方向に向かっているかどうかアドバイスしてもらえますか?

using namespace std;
#ifndef BSTNODE_H
#define BSTNODE_H
class BSTNode
{
    private:
    //Defines the 'node' structure
    struct tree_node 
    {
     tree_node *left;   // left subtree has smaller elements
     tree_node *right;  // right subtree has larger elements
     int m_data;
    };
    //root * r;
    public:
        //The Constructor
        BSTNode();
        //The Destructor
       ~BSTNode();
       //Inserts a value into a BST, public function
        void insert(const m_data & d);
        //Removes a value from a BST, public function
        void remove(const m_data & d);
        //isEmpty function, public function
        bool isEmpty();
        BSTNode getData();
        void inOrder(const m_data & d);
        void preOrder(const m_data & d);
        void postOrder(const m_data & d);
};
#endif

次に、BSTNode.cpp ファイルを作成する必要があります。メールで jediknight80n@hotmail.com までご返信いただければ幸いです。よろしくお願いいたします。

4

9 に答える 9

3

さまざまなメソッドで使用してtypedefいる型を忘れてしまったようです。また、(クラス自体を使用するのではなく) 別の構造体が必要な理由も、.m_datatree_nodegetDataBSTNodeint

于 2009-05-18T04:27:55.093 に答える
3 
   //Inserts a value into a BST, public function
    void insert(const m_data & d);
    //Removes a value from a BST, public function
    void remove(const m_data & d);
    //isEmpty function, public function
    bool isEmpty();
    BSTNode getData();
    void inOrder(const m_data & d);
    void preOrder(const m_data & d);
    void postOrder(const m_data & d);

m_data は型ではなくメンバーです。ここでは int を使用する必要があります。また、ノードは tree_node であるため、外部クラスはおそらくツリー全体を表す必要があります (つまり、BSTNode ではなく BSTree)。

また、「名前空間 std; を使用する」オプトアウトする方法がないヘッダーを含むものにそれを強制するため、ヘッダーでは悪です。使用する場合は、.cpp ファイルに保存することをお勧めします。

于 2009-05-18T04:31:21.227 に答える
2

些細なこと：

tree_node *left;   // left subtree has smaller elements

一般に、左側のサブツリーにも同じ要素が含まれています。

于 2009-05-18T05:19:16.197 に答える
1

カップルのもの-他の人が指摘しているように、あなたは使用する必要があります

void insert(const int & d);
//Removes a value from a BST, public function
void remove(const int & d);
//isEmpty function, public function
bool isEmpty();
BSTNode getData();
void inOrder(const int & d);
void preOrder(const int & d);
void postOrder(const int & d);

もう1つは、ルートノードをコメントアウトしたことです。間違って定義しましたが、クラスにルートノードを含める必要があります。正しい定義は次のようになります

tree_node *root;

また、前に指摘したように、

名前空間stdを使用します。

ヘッダーファイルから、代わりに実装ファイルに入れます。

私が今見ることができるのはそれだけです。

于 2009-05-18T04:45:29.173 に答える
1

もう1つの問題は、指定されたクラスがネストされた型とメソッドを宣言しているが、メンバーデータを宣言していないことです。

イテレータを使用してトラバーサル機能を宣言できます。たとえば、preorderメソッドは、ノードを逆参照したり、preorderシーケンスの次のノードを指すようにインクリメントしたりできるインタレータを返します。

または、コールバックを使用してトラバーサル機能を宣言することもできます。つまり、呼び出し元がコールバックインスタンスをpreorderメソッドに渡し、preorderメソッドがツリーをトラバースして、各ノードのコールバックメソッドを呼び出します。コールバックメソッドはノードを取得します（より具体的には、ノードデータ）をパラメータとして返し、コールバックがトラバーサルを異常終了することを指定できるようにするブール値を返す場合があります。

于 2009-05-18T04:46:41.390 に答える
1

検索メソッドも追加します。

bool search(int whatIlookfor);

またはさらに良い

tree_node* search(int whatIlookfor);

また、tree_node *root安全な場所に保管してください。

于 2009-05-18T04:48:37.677 に答える
1

  • あなたの例で構造体型の左右のポインターを使用すると、柔軟性が制限されます-BSTを取得してルートの左の子にトラバースし、この新しいサブツリーで操作を呼び出したいとします。ポインターが構造体型であるため、できません。タイプ BSTNode として両方のポインターを使用することをお勧めします。

    BSTNode *left;

    BSTNode *right;

    メインでオブジェクトを参照するために使用するポインターはとにかくルートを指すため、これによりルートの問題も解決されます (明示的なルートポインターは必要ありません)。

  • トラバーサル関数は、本質的にツリー全体をトラバースし、すべてのデータ項目を出力する場合、引数を必要としません。データ項目は、TrueStar によって既に指摘されているように、その位置を検索するために別の検索メンバー関数に渡すことができます。

  • また、パブリックメンバー関数の複雑さを軽減するために、いくつかのプライベートメンバー関数を提案します（何度も何度もDeleteNodeCaseB(int data)呼び出さDeleteNodeCaseA(int data)れます）-

    BSTNode * setleft(int data);

    BSTNode * setright(int data);

    void DeleteNodeCaseA(int data) /* 左右どちらかまたは両方の子が存在しない */

    void DeleteNodeCaseB(int data) /* 左右両方の子を持つ */

于 2009-05-18T05:22:41.733 に答える
1

C++ を使用しているため、すべてを自分で実装しようとするのではなく、いくつかの標準ライブラリを使用することを検討することをお勧めします。STL ライブラリには赤黒ツリーが付属しており、アプリケーションにより適している場合があります。バイナリ ツリーは、片側が偏ったり、リンク リストに縮退したりする可能性があります。

PS: もちろん、これは宿題をしていないことを前提としています。

于 2009-05-18T05:26:19.577 に答える
1

これは BST に関する古典的な質問です。データ構造に関する優れた本であれば、コード全体が得られます。次のページには、C++ http://cslibrary.stanford.edu/110/BinaryTrees.htmlのコード例が含まれています。

トラバーサル関数は BST クラス自体の一部であってはなりません。事実、BSTNode は左右のノード ポインタを公開する必要があり、呼び出し元のアプリケーションは特定の方法でそれを呼び出す必要があります。または、コールバック関数を使用して、クラス内にトラバーサル コードを提供します。この方法では、はるかにクリーンになります。

于 2009-05-18T04:31:41.040 に答える