0

私は木について学び始め、BSTのコードを書いてみました。残念ながら、ツリーデータの表示に問題があります。深さ優先走査を実装しようとしています。しかし、それを実装する方法がわかりません。以下は私のコードです

#include<iostream>
using namespace std;

class node
{
  public:
  int data;
  node *left,*right;
};

class btree
{
private:
node *root;
public:
btree(){root=NULL;}
void insert(int value)
{node *temp=new node;
    if(root == NULL)
        {
        temp->right=NULL;
        temp->data=value;
        temp->left=NULL;
        root=temp;
        }
    else
        insertHelper(root, value);
}

void insertHelper(node* Node, int value)
{
    if(value < Node->data)
    {
        if(Node->left == NULL)
            {
                Node->left=new node;
                Node->left->data=value;
                Node->left->left=NULL;
                Node->left->right=NULL;
                }
        else
            insertHelper(Node->left, value);
    }
    else
    {
        if(Node->right== NULL)
           {
               Node->right = new node;
               Node->right->data=value;
               Node->right->left=NULL;
               Node->right->right=NULL;
               }
        else
            insertHelper(Node->right, value);
    }

}


void disp()
{node*tmp=root;
if(tmp==NULL)
    cout<<"empty"<<endl;
else
    {
        cout<<tmp->data<<endl;
        disphelper(tmp);
    }
}

void disphelper(node *tmp)
{


    if(tmp->left!=NULL)
    {
        cout<<tmp->left->data<<endl;
        tmp=tmp->left;
        disphelper(tmp);}
    if(tmp->right!=NULL)
    {
       cout<<tmp->right->data<<endl;
        tmp=tmp->right;
        disphelper(tmp);
    }
}
};

int main()
{
    btree binarytree;
    binarytree.disp();
    binarytree.insert(10);
    binarytree.insert(5);
    binarytree.insert(30);
    binarytree.disp();
}

出力は

empty
10
5

30が表示されない理由を教えてください。

4

2 に答える 2

2

コードを次のように変更します

void disphelper(node *tmp)
{
    if(tmp == NULL)
       return;
    cout<<tmp->data<<endl; // print data for current node

    if(tmp->left!=NULL) // traverse left branch
    {
        //cout<<tmp->left->data<<endl;
        //tmp=tmp->left;
        disphelper(tmp->left);}
    if(tmp->right!=NULL) // traverse right branch
    {
       //cout<<tmp->right->data<<endl;
        //tmp=tmp->right;
        disphelper(tmp->right);
    }
}

そして、それはうまくいくはずです。

void disp()
{node*tmp=root;
if(tmp==NULL)
    cout<<"empty"<<endl;
else
    {   
        disphelper(tmp);
    }
}
于 2013-01-11T14:47:53.117 に答える
2

ここで出力が得られない理由は、disphelper()最初に左のノードが存在するかどうかを確認してから、再帰するときにNULLそれを変更しているためです。正しいノードに再帰する場合も同じです。

    void disphelper(node *tmp)
    {
        if(tmp->left!=NULL)
        {
            cout<<tmp->left->data<<endl;
            //tmp=tmp->left; // Get rid of this.
            disphelper(tmp->left); // Use this.
        }
        if(tmp->right!=NULL)
        {
            cout<<tmp->right->data<<endl;
            //tmp=tmp->right; // Get rid of this
            disphelper(tmp->right); // Use this.
        }
    }

両方の比較で同じであるはずの temp の値を変更する代わりに、左または右のノードを渡すだけです。

他の2つのこと。まず、ここで狂ったようにメモリをリークしています: では、insert()毎回新しいオブジェクトを作成しますが、最初にのみ使用し、リークするたびに使用します。クラスnodeは、両方のノードを削除するデストラクタを持つことでメモリを処理する必要があります。

次に、コードを投稿する前に、インデントが一貫するように形式を整えていただけませんか? これを行うのに以前ほど苦労することはありません。多くのエディターが代わりにやってくれるか、優れたAstyleを使用できます。些細なことだとは思いますが、あなたのコードを読んでいる人にとってはイライラすることです。ありがとう ：-）

于 2013-01-11T14:39:01.823 に答える