复制二叉树

Question

当被要求创建二叉树的副本时，我总是被告知使用后期顺序遍历逻辑来制作副本。

是否无法按预订或按顺序处理原始树以创建副本？

任何遍历方法比其他方法更优化？

订购后方式：

NODEPTR Copy(NODEPTR p)
{
  if (p == null) return p
  NODEPTR left = Copy(p-> left)
  NODEPTR right = Copy(p-> right)
  NODEPTR root = MakeBT(p->data, left, right) //MakeBT is a helper function that makes a tree
  return (root)
}

预订方式：

NODEPTR Copy(NODEPTR p)
{
  if (p == null) return p
  NODEPTR root
  root->data = p->data
  root-> left = Copy(p-> left)
  root-> right = Copy(p-> right)      
  return (root)
}

有序方式：

   NODEPTR Copy(NODEPTR p)
    {
      if (p == null) return p
      NODEPTR left = Copy(p-> left)
      NODEPTR root
      root-> data = p-> data
      root-> left = left
      root-> right = Copy(p-> right) 
      return (root)
    }

Answer 1

这是一个将二叉树（Node）复制到新二叉树（NewNode）的cpp程序。

#include <iostream>

using namespace std;

class Node{

public:
  int val;
  Node* left=NULL;
  Node* right=NULL;

  Node(int val){
    this->val=val;
    this->right=NULL;
    this->left=NULL;
}
  void insert(int v){

    if(this->left==NULL)
      this->left=new Node(v);
    else if(this->right==NULL)
      this->right=new Node(v);
    else
      cout<<"impossible to insert the node\n";

    }
   void print(){
    cout<<this->val<<" ";
    if(this->left) this->left->print();
    if(this->right) this->right->print();

   }


};

class NewNode{
public:
  int val;
  NewNode* left=NULL;
  NewNode* right=NULL;
  NewNode* parent=NULL;

  void print(){
    cout<<this->val<<" ";
    if(this->left) this->left->print();
    if(this->right) this->right->print();

   }

};

void copy(Node* original,NewNode* duplicate){
    duplicate->val=original->val;
//  cout<<duplicate->val<<endl;
    if(original->left){
        NewNode* newLeft=new NewNode;
        newLeft->parent=duplicate;
        duplicate->left=newLeft;
//      printf("in left copying %d %d %d\n",duplicate->val,duplicate->left,duplicate->parent);
        copy(original->left,duplicate->left);

    }
    if(original->right){
        NewNode* newRight=new NewNode;
        newRight->parent=duplicate;
        duplicate->right=newRight;
//      printf("in right copying %d %d %d\n",duplicate->val,duplicate->right,duplicate->parent);
        copy(original->right,duplicate->right);
    }
}

int main(){
Node root(1);
root.insert(2);
root.insert(3);
printf("%d %d %d\n",root.val,root.left,root.right);
Node* temp=root.left;
temp->insert(4);
temp->insert(5);
printf("%d %d %d\n",temp->val,temp->left,temp->right);
NewNode root2;
copy(&root,&root2);
printf("%d %d %d\n",root2.val,root2.left,root2.right);
NewNode *temp1=root2.left;
printf("%d %d %d\n",temp1->val,temp1->left,temp1->right);
root.print();
cout<<endl;
root2.print();
return 0;
}