具有父节点的二叉树的 C++ 复制构造函数

Question

我需要为一个二叉树类编写一个复制构造函数来制作给定二叉树的深层拷贝，但是当我执行我的复制构造函数时我总是遇到段错误，更具体地说，父节点导致了问题，但我想不出正确的做法。

class Node
{
 public:
  int value;;
  Node();
  Node(int v);
  Node * left;
  Node * right;
  Node * parent;
};
Node::Node()
{
  left=nullptr;
  right=nullptr;
  parent=nullptr;
  value=0;
}
Node::Node(int v)
{
  val = v;
  left = nullptr;
  right = nullptr;
  parent = nullptr;
}


class BT
{
  public:
   BT();
   BT(const BTr & t);
   Node *root;
   int size;
   Node * copy(Node *p);
   //other functions..
};

BT::BT()
{
  root = nullptr;
  size = 0;
}

//No need to consider if t.root is nullptr here
//assume t is always a non-empty valid binary tree here
BT::BT(const BT &t)
{
   size = t.size;
   root = copy(t.root); 
}

Node * BT::copy(Node *p)
{
  if (p == nullptr)
  {
    return nullptr;
  }
  Node * n = new TNode(p->val);
  n->left = copy(p->left);
  n->left->parent = n;
  n->right = copy(p->right);
  n->right->parent = n;
  return n;
}


int main()
{
  BT y;
  y.root = new Node(11);
  y.root->left = new Node(12);
  y.root->right = new Node(13);
  y.root->left->left = new Node(14);
  y.root->left->right = new Node(15);
  y.root->right->left = new Node(16);
  y.root->left->parent = y.root;
  y.root->right->parent = y.root;
  y.root->parent = nullptr;
  y.root->left->left->parent = y.root->left;
  y.root->left->right->parent = y.root->left;
  y.root->right->left->parent = y.root->right;
  y.size = 6;
  BT b(y);
  return 0;
}

Answer 1

n->left->parent = n;
n->right->parent = n;

您执行这些分配时没有先检查 left 或 right 是否为 nullptr。

添加检查:

if(n->left) n->left->parent = n;

同样适用于right。