-1

以下は、BSTをソート済み二重リンクリストに変換するために実装したコードです。しかし、次の入力では、左端の右端のサブブランチがありません

たとえば。入力用 4 1 2 3 6 5 7 (BST への入力)

データ 2 と 3 のノードがありません。コードの何が問題なのか教えてください。

#include<iostream>
 using namespace std;
struct node
{
int data;
node* left;
node* right;
};
node* tree=NULL;
int count=1;
void inorder(node *tree)
{
if(tree!=NULL)
{
     inorder(tree->left);
    cout<<tree->data<<" ";
    inorder(tree->right);
}
}
node * insert(node *tree,int n)
{
if(tree==NULL)
{
    tree=new node;
    tree->left=tree->right=NULL;
    tree->data=n;
}
else if(tree->data>n)
tree->left=insert(tree->left,n);
else
tree->right=insert(tree->right,n);
return(tree);

}
node *start=NULL;
node *prev=NULL;
node * head=NULL;
void func(node *root)
{
if(root!=NULL)
{
    func(root->left);
    if(start==NULL)
    {
        start=root;
        start->left=NULL;
        start->right=NULL;
        prev=start;
        head=start;
        //cout<<start->data<<"  ";
    }
    else
    {
        start->right=root;
        start=start->right;
        start->left=prev;
        prev=start;
       // cout<<start->left->data<<"  ";
    }
    func(root->right);
}
}
int main()
{
int n;

cout<<"Enter the number of nodes\n";
cin>>n;
int k=n;
int value;
while(n--)
{
   cin>>value; 
   tree=insert(tree,value);
}
inorder(tree);
cout<<endl;
func(tree);
cout<<endl;
while(head!=NULL)
{
    cout<<head->data<<"  ";
    head=head->right;
}
return 0;
}
4

2 に答える 2

2

の元のツリーを変更していますfunc。たとえば、 への最初の呼び出しではfuncstart->right = NULLと をfunc(root->right);一緒に使用することはほとんど意味がありません。start = root(および同様のことを)行う代わりに、ノードを使用してメモリを割り当てnew、ノードをリストにコピーできます。

于 2012-08-17T19:37:05.217 に答える
0

問題は、func データ= 1のノードの場合、右側のサブツリーをオーバーライドしてNULLにすることです。

于 2012-08-17T20:20:18.693 に答える