Почему мое оригинальное дерево бинарного поиска изменяется, хотя я скопировал корневой узел в другой узел?

Question

Мой учитель дал нам задание на код Binary Search Tree.Большая часть работы выполнена, но у меня возникли проблемы с зеркальным отображением двоичного дерева.Учитель сказал нам, что мы должны создать зеркальное отображение без изменения исходного дерева.Я пытался создать его, но код также изменяет исходный BST, как показано в моих выходных данных ниже.Я не понимаю, где это идет не так.Любая помощь будет оценена.

Мой код:

#include<iostream>
using namespace std;
struct node
{
    int data;
        node *left,*right;
};
class BST
{
    node *root,*root1;
    public:
        int ch;
    BST(){   root=NULL;     ch=0;    }    
        void create();
    void insert(node*,node*);
    void disin();   
    void inorder(node*);
    void dispre();  
    void preorder(node*);
    void dispost(); 
    void postporder(node*);
    void search();
    node* actualsearch(node*,int);
    void min();
    void max();
    void actmin(node*);
    void actmax(node*);
    void height();
    int actheight(node*);
    void mirror();
    void actmirror(node*);
};
int main()
{
    int cho;
    BST b;
    char choice;
    do  {
    cout<<"\nEnter Your Choice = ";
    cout<<"\n1.Insert";
    cout<<"\n2.Inorder Traversal";
    cout<<"\n3.Preorder Traversal";
    cout<<"\n4.Postorder Traversal";
    cout<<"\n5.Search an element in tree";
    cout<<"\n6.Find Maximum element in tree";
    cout<<"\n7.Find Minimum elemnt in tree";
    cout<<"\n8.Total No Of Nodes In Longest Path";
    cout<<"\n9.Mirror Image = ";
    cin>>cho;
    switch(cho)
    {
        case 1:
            b.create();
            break;

        case 2:
            cout<<"---------------------------------------------------";
            cout<<"\nInorder Treaversal = "<<endl;
            b.disin();
            cout<<"\n---------------------------------------------------";      
            break;

        case 3:
            cout<<"---------------------------------------------------";
            cout<<"\nPreorder Treaversal = "<<endl;
            b.dispre();
            cout<<"\n---------------------------------------------------";      
            break;

        case 4:
            cout<<"---------------------------------------------------";
            cout<<"\nPostorder Treaversal = "<<endl;
            b.dispost();
            cout<<"\n---------------------------------------------------";      
            break;  

        case 5:
            b.search();
            cout<<"\n---------------------------------------------------";
            break;
        case 6:
            b.max();
            cout<<"\n---------------------------------------------------";
            break;
        case 7:
            b.min();
            cout<<"\n---------------------------------------------------";
            break;
        case 8:
            b.height();
            cout<<"\n---------------------------------------------------";
            break;
        case 9:
            b.mirror();
            cout<<"\n---------------------------------------------------";
            break;

    }
    cout<<"\nDo you want to continue opreations(y/n) = ";
    cin>>choice;    
    }while(choice=='y'||choice=='Y');
    return 0;
}

void BST::search()
{
    int n;
    cout<<"\nEnter element you want to search = ";
    cin>>n;
    if(root!=NULL)
        actualsearch(root,n);
    else
        cout<<"Tree is empty"<<endl;        
}
node* BST::actualsearch(node *current,int n)
{
    int dfcount=0;
    while(current)
    {
        if(current->data==n)
        {
            cout<<"Data Found"<<endl;
            dfcount++;
            break;
        }
        else if(n>current->data)
            {
                current=current->right;
            }
        else if(n<current->data)
            {
                current=current->left;
            }
    }
    if(dfcount==0)
    cout<<"Data not found!"<<endl;
    return NULL;
}

void BST::create()
{
    char ans;
    node *temp;
    do
    {
        temp=new node;
        temp->left=temp->right=NULL;
        cout<<"\nEnter no you want to insert = ";
        cin>>temp->data;
        if(root==NULL)
        {
            root=temp;
        }
        else
        {
            insert(root,temp);
        }
        cout<<"\nDo You want to continue to insert data(y/n) = ";
        cin>>ans;
    }while(ans=='y'||ans=='Y');
}

void BST::insert(node *current,node *temp)
{
    if(temp->data==current->data)
        cout<<"\nDo not add";

    else if(temp->data<current->data)
    {
        if(current->left==NULL)
            current->left=temp;
        else
            insert(current->left,temp);
    }
    else if(temp->data>current->data)
    {
        if(current->right==NULL)
            current->right=temp;
        else
            insert(current->right,temp);
    }                   
}

void BST::disin()
{

    inorder(root);
}

void BST::inorder(node *T)
{   

    if(T!=NULL)
     {
        inorder(T->left);
        cout<<T->data<<" "; 
        inorder(T->right);
    }
}


void BST::dispre()
{

    preorder(root);
}

void BST::preorder(node *T)
{   

    if(T!=NULL)
     {
        cout<<T->data<<" "; 
        preorder(T->left);
        preorder(T->right);
    }
}


void BST::dispost()
{

    postporder(root);
}

void BST::postporder(node *T)
{   

    if(T!=NULL)
     {
        postporder(T->left);    
        postporder(T->right);
        cout<<T->data<<" "; 
    }
}
void BST::max()
{
    if(root!=NULL)
    {
        actmax(root);
    }
}
void BST::min()
{
    if(root!=NULL)
    {
        actmin(root);
    }
}
void BST::actmax(node* current)
{
    while(current->right!=NULL)
    {
        current=current->right;
    }
    cout<<"Largest Number is :"<<current->data<<endl;
}
void BST::actmin(node* current)
{
    while(current->left!=NULL)
    {
        current=current->left;
    }
    cout<<"Smallest Number is :"<<current->data<<endl;
}
void BST::height()
{
    int i=actheight(root);
    cout<<"Total No Of Nodes In Longest Path is:"<<i<<endl;
}
int BST::actheight(node* current)
{
    if(current==NULL)
    {
        return 0;
    }
    else
    {
        int lh = actheight(current->left);
        int rh = actheight(current->right);
        if (lh > rh)  
           return(lh+1);
        else return(rh+1);
    }

}
void BST::mirror()
{   root1=root;
    actmirror(root1);
    cout<<"Mirror Image of given tree is Created!"<<endl;
    cout<<"\nInorder Travesral Is = "<<endl;
    inorder(root1);
    cout<<"\nPreorder Travesral Is = "<<endl;
    preorder(root1);
    cout<<"\nPostorder Travesral Is = "<<endl;
    postporder(root1);

}
void BST::actmirror(node* current)
{
    node* holder=new node;
    if(current==NULL)
    {
        return ;    
    }

    holder=current->left;
    current->left=current->right;
    current->right=holder;
    actmirror(current->left);
    actmirror(current->right);
}

Его вывод:

Enter Your Choice =
1.Insert
2.Inorder Traversal
3.Preorder Traversal
4.Postorder Traversal
5.Search an element in tree
6.Find Maximum element in tree
7.Find Minimum elemnt in tree
8.Total No Of Nodes In Longest Path
9.Mirror Image = 1

Enter no you want to insert = 5

Do You want to continue to insert data(y/n) = y

Enter no you want to insert = 6

Do You want to continue to insert data(y/n) = y

Enter no you want to insert = 7

Do You want to continue to insert data(y/n) = y

Enter no you want to insert = 2

Do You want to continue to insert data(y/n) = y

Enter no you want to insert = 3

Do You want to continue to insert data(y/n) = n

Do you want to continue opreations(y/n) = y

Enter Your Choice =
1.Insert
2.Inorder Traversal
3.Preorder Traversal
4.Postorder Traversal
5.Search an element in tree
6.Find Maximum element in tree
7.Find Minimum elemnt in tree
8.Total No Of Nodes In Longest Path
9.Mirror Image = 2
---------------------------------------------------
Inorder Treaversal =
2 3 5 6 7
---------------------------------------------------
Do you want to continue opreations(y/n) = y

Enter Your Choice =
1.Insert
2.Inorder Traversal
3.Preorder Traversal
4.Postorder Traversal
5.Search an element in tree
6.Find Maximum element in tree
7.Find Minimum elemnt in tree
8.Total No Of Nodes In Longest Path
9.Mirror Image = 9
Mirror Image of given tree is Created!

Inorder Travesral Is =
7 6 5 3 2
Preorder Travesral Is =
5 6 7 2 3
Postorder Travesral Is =
7 6 3 2 5
---------------------------------------------------
Do you want to continue opreations(y/n) = y

Enter Your Choice =
1.Insert
2.Inorder Traversal
3.Preorder Traversal
4.Postorder Traversal
5.Search an element in tree
6.Find Maximum element in tree
7.Find Minimum elemnt in tree
8.Total No Of Nodes In Longest Path
9.Mirror Image = 2
---------------------------------------------------
Inorder Treaversal =
7 6 5 3 2
---------------------------------------------------
Do you want to continue opreations(y/n) = n

--------------------------------
Process exited after 41 seconds with return value 0
Press any key to continue . . .

Здесь вы можете видеть, что, хотя я использовал обычный Inorder Traversal Он нене показывает обход оригинального BST, скорее он показывает зеркальное прохождение BST.

Answer 1

Обход Это не показывает обход исходного BST, а показывает зеркальный Обход BST.

в

void BST::actmirror(node* current)
{
    node* holder=new node;
    if(current==NULL)
    {
        return ;    
    }

    holder=current->left;
    current->left=current->right;
    current->right=holder;
    actmirror(current->left);
    actmirror(current->right);
}

выделенныйновый узел потерян из-за holder=current->left;, и вы изменяете текущий , а не новый узел, как сказал drescherjm в замечании

---

Предложение: вclass BST изменить сигнатуру BST :: actmirror на node* BST::actmirror(node* current), а его определение:

node*  BST::actmirror(node* current)
{
    if(current==NULL)
    {
        return 0;    
    }

    node* holder=new node;

    holder->data = current->data;
    holder->left = actmirror(current->right);
    holder->right = actmirror(current->left);
    return holder;
}

, как вы видите, что делает зеркало, созданное вв то же время скопируйте

и обновите BST :: mirror () следующим образом:

void BST::mirror()
{   node * copy1 = actmirror(root);
    cout<<"Mirror Image of given tree is Created!"<<endl;
    cout<<"\nInorder Travesral Is = "<<endl;
    inorder(copy1);
    cout<<"\nPreorder Travesral Is = "<<endl;
    preorder(copy1);
    cout<<"\nPostorder Travesral Is = "<<endl;
    postporder(copy1);

    // WARNING here you need to delete the copy !
}

Как я уже сказал в замечании, лучше, если зеркало сделаетСкопировать и зеркало одновременно, я сделал это выше.

И теперь исполнение:

Enter Your Choice = 
1.Insert
2.Inorder Traversal
3.Preorder Traversal
4.Postorder Traversal
5.Search an element in tree
6.Find Maximum element in tree
7.Find Minimum elemnt in tree
8.Total No Of Nodes In Longest Path
9.Mirror Image = 1

Enter no you want to insert = 5

Do You want to continue to insert data(y/n) = y

Enter no you want to insert = 6

Do You want to continue to insert data(y/n) = y

Enter no you want to insert = 7

Do You want to continue to insert data(y/n) = y

Enter no you want to insert = 2

Do You want to continue to insert data(y/n) = y

Enter no you want to insert = 3

Do You want to continue to insert data(y/n) = n

Do you want to continue opreations(y/n) = y

Enter Your Choice = 
1.Insert
2.Inorder Traversal
3.Preorder Traversal
4.Postorder Traversal
5.Search an element in tree
6.Find Maximum element in tree
7.Find Minimum elemnt in tree
8.Total No Of Nodes In Longest Path
9.Mirror Image = 2
---------------------------------------------------
Inorder Treaversal = 
2 3 5 6 7 
---------------------------------------------------
Do you want to continue opreations(y/n) = y

Enter Your Choice = 
1.Insert
2.Inorder Traversal
3.Preorder Traversal
4.Postorder Traversal
5.Search an element in tree
6.Find Maximum element in tree
7.Find Minimum elemnt in tree
8.Total No Of Nodes In Longest Path
9.Mirror Image = 9
Mirror Image of given tree is Created!

Inorder Travesral Is = 
7 6 5 3 2 
Preorder Travesral Is = 
5 6 7 2 3 
Postorder Travesral Is = 
7 6 3 2 5 
---------------------------------------------------
Do you want to continue opreations(y/n) = y

Enter Your Choice = 
1.Insert
2.Inorder Traversal
3.Preorder Traversal
4.Postorder Traversal
5.Search an element in tree
6.Find Maximum element in tree
7.Find Minimum elemnt in tree
8.Total No Of Nodes In Longest Path
9.Mirror Image = 2
---------------------------------------------------
Inorder Treaversal = 
2 3 5 6 7 
---------------------------------------------------
Do you want to continue opreations(y/n) = n