复制二叉树C++的构造函数

Question

我有一个具有以下定义的Tree类:

class Tree {
  Tree();
private:
  TreeNode *rootPtr;
}

TreeNode表示一个节点并具有数据,leftPtr和rightPtr.

如何使用复制构造函数创建树对象的副本？我想做的事情如下:

Tree obj1;
//insert nodes

Tree obj2(obj1); //without modifying obj1.

任何帮助表示赞赏!

Answer 1

伪代码:

struct Tree {
  Tree(Tree const& other) {
    for (each in other) {
      insert(each);
    }
  }

  void insert(T item);
};

具体的例子(改变你走树的方式很重要,但是减少了显示复制ctor如何工作,并且可能在这里做了太多的人的作业):

#include <algorithm>
#include <iostream>
#include <vector>

template<class Type>
struct TreeNode {
  Type data;
  TreeNode* left;
  TreeNode* right;

  explicit
  TreeNode(Type const& value=Type()) : data(value), left(0), right(0) {}
};

template<class Type>
struct Tree {
  typedef TreeNode<Type> Node;

  Tree() : root(0) {}
  Tree(Tree const& other) : root(0) {
    std::vector<Node const*> remaining;
    Node const* cur = other.root;
    while (cur) {
      insert(cur->data);
      if (cur->right) {
        remaining.push_back(cur->right);
      }
      if (cur->left) {
        cur = cur->left;
      }
      else if (remaining.empty()) {
        break;
      }
      else {
        cur = remaining.back();
        remaining.pop_back();
      }
    }
  }
  ~Tree() {
    std::vector<Node*> remaining;
    Node* cur = root;
    while (cur) {
      Node* left = cur->left;
      if (cur->right) {
        remaining.push_back(cur->right);
      }
      delete cur;
      if (left) {
        cur = left;
      }
      else if (remaining.empty()) {
        break;
      }
      else {
        cur = remaining.back();
        remaining.pop_back();
      }
    }
  }

  void insert(Type const& value) {
    // sub-optimal insert
    Node* new_root = new Node(value);
    new_root->left = root;
    root = new_root;
  }

  // easier to include simple op= than either disallow it
  // or be wrong by using the compiler-supplied one
  void swap(Tree& other) { std::swap(root, other.root); }
  Tree& operator=(Tree copy) { swap(copy); return *this; }

  friend
  ostream& operator<<(ostream& s, Tree const& t) {
    std::vector<Node const*> remaining;
    Node const* cur = t.root;
    while (cur) {
      s << cur->data << ' ';
      if (cur->right) {
        remaining.push_back(cur->right);
      }
      if (cur->left) {
        cur = cur->left;
      }
      else if (remaining.empty()) {
        break;
      }
      else {
        cur = remaining.back();
        remaining.pop_back();
      }
    }
    return s;
  }

private:
  Node* root;
};

int main() {
  using namespace std;

  Tree<int> a;
  a.insert(5);
  a.insert(28);
  a.insert(3);
  a.insert(42);
  cout << a << '\n';      

  Tree<int> b (a);
  cout << b << '\n';

  return 0;
}

Answer 2

这取决于您是想要浅色还是深色.假设有一个深层复制品,你需要能够复制悬挂在TreeNode物体上的"叶子"上的任何东西; 所以理想情况下功能应该是TreeNode(除非你设计Tree的朋友类TreeNode非常熟悉它的实现,当然通常是这样;-).假设像...:

template <class Leaf>
class TreeNode {
  private:
    bool isLeaf;
    Leaf* leafValue;
    TreeNode *leftPtr, *rightPtr;
    TreeNode(const&Leaf leafValue);
    TreeNode(const TreeNode *left, const TreeNode *right);
  ...

然后你可以添加一个

  public:
    TreeNode<Leaf>* clone() const {
      if (isLeaf) return new TreeNode<Leaf>(*leafValue);
      return new TreeNode<Leaf>(
        leftPtr? leftPtr->clone() : NULL,
        rightPtr? rightPtr->clone() : NULL,
      );
    }

如果Tree正在处理这种级别的功能(作为朋友类),那么显然你将具有完全等价但是将节点克隆为显式arg.