0

私のプログラムで何が間違っているのか教えてください。これは基本的に、二分探索木に新しいノードを挿入するプログラムです。

問題は、私の挿入機能が正しく機能していて、ノードが挿入されていることです。これは、メインプログラムで次の行で確認しています

     cout<<a.left->right->right->data;

その出力は正しく来ています、つまり5

しかし、バイナリ ツリーのレベル順トラバーサルを出力しようとすると、新しいノードの代わりにジャンク値が渡され、プログラムがクラッシュします。

誰かが見て、私が間違っていることと、メインプログラムで正しい値が表示される方法を説明してください。

#include<iostream>
#include<string>
#include<conio.h>
#include<array>
#include<stack>
#include<sstream>
#include<algorithm>
#include<vector>
#include<ctype.h>//isdigit
#include<deque>
#include<queue>
#include<map>
using namespace::std;
struct BST
{
    int data;
    BST *left;
    BST *right;
    BST(int d,struct BST* l,BST *r):data(d) , left(l) ,right(r)
    {
    }
};

void levelOrder(struct BST *root)
{
    struct BST *temp=NULL;
    int count =0;
    deque<struct BST*> dq;
    if(!root)
    {
        return;
    }
    dq.push_back(root);
    count=dq.size();
    while(!dq.empty())
    {
        temp=dq.front();
        cout<<temp->data<<" ";
        if(temp->left)
        {
            dq.push_back(temp->left);
        }
        if(temp->right)
        {
            dq.push_back(temp->right);
        }
        dq.pop_front();
        if(--count==0)
        {
            cout<<endl;
            count=dq.size();
        }
    }
}
void Insert(struct BST*root,int data)
{
    struct BST temp(data,NULL,NULL);
    if(!root)
    {
        return;
    }
    while(root)
    {
        if((root)->data >data)
        {
            (root)=(root)->left;
            if(!(root)->left)
            {
                (root)->left=&temp;
                break;
            }
        }
        else
        {
            (root)=(root)->right;
            if(!(root)->right)
            {
                (root)->right=&temp;
                break;
            }
        }
    }
}
int main()
{
    deque<struct BST> dq1,dq2;
    BST e(4,NULL,NULL);
    BST f(3,NULL,NULL);
    BST d(1,&f,NULL);
    //BST g(4,NULL,NULL);
    BST b(2,&d,&e);
    BST c(8,NULL,NULL);
    BST a(6,&b,&c);
    levelOrder(&a);
    Insert(&a,5);
    cout<<a.left->right->right->data;
    cout<<endl;
    levelOrder(&a);
    _getch();
    return 0;
}
4

1 に答える 1

3

その理由は、Insert関数内のツリーにローカル変数へのポインターを入れているためです。

関数が戻ると、そのすべてのローカル変数はもはや「生きていない」ため、それらのローカル変数の 1 つへのポインタへのアクセスは未定義の動作です。実際、これらの変数が一度占有したメモリは、どの関数を呼び出しても、次の関数呼び出しによって上書きされる可能性があります。

新しいノードを追加したい場合は、eg を使用してヒープに割り当てる必要がありますnew。ただし、ツリーの設計により、サブノードを解放しないため、メモリ リークが発生します。実際、main関数内でローカル変数へのポインターを使用する場合 (これらの変数の有効期間はmainプログラム全体であるため、問題ありません)、単純deleteにポインターをウィリーナイリーにすることはできません。

于 2013-03-02T21:27:37.113 に答える