c++ - 为什么即使我将根节点复制到另一个节点中，我的原始二叉搜索树也会被修改？

Question

我的老师给了我们一个任务来编写二叉搜索树。大部分部分都完成了，但我在二叉树的镜像上遇到了麻烦。老师告诉我们，我们应该在不改变原来的树的情况下创建一个镜像。我尝试创建它，但代码也修改了原始 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 . . .

在这里您可以看到，即使我使用了普通的中序遍历，它也没有显示原始 BST 的遍历，而是显示了镜像 BST 的遍历。

标签： c++binary-search-tree

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 在评论中所说

---

一个提议：在 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