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

Question

我需要为二叉树编写一个复制构造函数 class 来制作给定二叉树的深层副本，但是当我执行复制构造函数时我总是运行进入分段错误，更具体地说，父节点导致了问题，但我想不出正确的方法。

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.

也一样

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

C++ Copy constructor for binary tree with parent nodes

c++

binary-tree

deep-copy