c - 需要帮助理解二叉搜索树中的父节点

Question

下面的代码是将节点插入树中正确位置的函数。我不明白的是父节点实际上代表什么。当它显示 root -> left ->parent = root -> left 时，这是什么意思？这不是把root的左父节点设置为它自己吗？ 难道不应该是 root -> left ->parent = root 吗？因为我们希望 root 的左子级的父级是 root 而不是 left-child 本身？您能否帮我澄清一下父节点，谢谢。

Node * insert(Node *root, int item) {
  if (root == NULL)
    return newNode(item);

  if (item <= root -> info)
    if (root -> left == NULL) {
      root -> left = newNode(item);
      root -> left -> parent = root -> left;      //**line of interest**
    }
    else
      insert(root -> left, item);
  else
    if (root -> right == NULL) {
      root -> right = newNode(item);
      root -> right -> parent = root -> right;
    }
    else
      insert(root -> right, item);
  return root;
}

Answer 1

根据您的描述，我认为节点类将是，

class node{
   int info;
   node *left;
   node *right;
   node *parent;
};

现在，在 BST 中将有一个根节点，其中父节点将为 NULL。假设我们插入第一个值。(设为 5)
现在 root 显然有 5。 root->left 为 null，root->right 为 null。

如果现在插入 2，那么 2 将位于根的左侧。

所以 root->left 将为 2。现在让我们简化一下，因为 root->left 我们指的是一个节点，而不是一个值。 因此root->left->info = 2;。 现在还有一件事要做。我们设置root->left的值。现在 root->left 的父级是什么？那将是根， 所以root->left->parent = root;

现在如果你插入另一个数据(让它为1)然后

root->left->left->info = 1;
root->left->left->parent = root->left;

所以你的代码并没有简化在 BST 中插入节点的事情。

我会做的是，

 Node n = new node();
 n = newNode(item); //as you wrote
 n->parent = root->left.