将节点添加到二叉搜索树

Question

下面的代码应该将一个节点添加到我的BST结构中，但未能这样做。新节点根本不会连接到树，包括根节点。任何人都可以指出问题出在哪里？

对树的构造：

template <typename K, typename T> 
MyBinaryTree<K, T>::MyBinaryTree() { 
    root = nullptr; 
} 

功能即会从外面叫：

并且具有附加的节点内部专用功能：

template <typename K, typename T> 
void MyBinaryTree<K, T>::addToSubtree(MyBinaryTree<K, T>::Node *node, 
      MyBinaryTree<K, T>::Node *toAdd) { 
    if(node == nullptr) { 
     node = toAdd; 
    } else { 
     if(toAdd->key > node->key) addToSubtree(node->right, toAdd); 
     else if(toAdd->key < node->key) addToSubtree(node->left, toAdd); 
    } 
} 

Answer 1

你的node变量是一个局部变量，包含指向Node的指针，当为它赋值时，它只适用于函数作用域中的该局部变量。

为了让你的函数的工作，你应该做一个node变量指向指针（因此它被称为像addToSubtree(&node->right, toAdd)或引用指针

Answer 2

你应该使用引用，像这样：MyBinaryTree<K, T>::Node *&root

因为当你在addToSubtree修改根，就只修改本地函数参数根，参数，没有根参数复制自身

Answer 3

你的代码存在两个问题：

1. 虽然它应该代表面向对象的thinkig，但代码却回到了C风格的做事方式。 root元素不应该作为参数传递。由于它是一个成员变量，它在每个成员函数范围内都存在自动的。

这样的：

template <typename K, typename T> 
void MyBinaryTree<K, T>::addToSubtree(MyBinaryTree<K, T>::Node *root, 
      MyBinaryTree<K, T>::Node *toAdd) { 
    //rest... 
} 

应该是这样的：

template <typename K, typename T> 
void MyBinaryTree<K, T>::addToSubtree(MyBinaryTree<K, T>::Node *toAdd) { 
    if(root == nullptr) { 
     root = toAdd; 
    } //rest... 
} 

功能已经知道root是什么，因为根是一个成员变量。 成员函数可以改变成员变量而不它们需要被传递到函数

真正的问题是到指针之间指针到指针的差值。每当我们想要一个函数改变给定的参数时，该参数应该作为指针或作为参考传递。

如果参数已经是一个指针，以改变指针本身应该通过无论是作为指针，指针或referene的指针

所以，让我们假设我们要继续通过root作为自变量（我们不这样做），我们应该通过它无论是作为

void MyBinaryTree<K, T>::addToSubtree(MyBinaryTree<K, T>::Node **root, 
      MyBinaryTree<K, T>::Node *toAdd) { 
    if(*root == nullptr) { 
     *root = toAdd; 
     //rest 

无论是作为

void MyBinaryTree<K, T>::addToSubtree(MyBinaryTree<K, T>::Node*& root, 
      MyBinaryTree<K, T>::Node *toAdd) { 
    if(root == nullptr) { 
     root = toAdd; 
     //the rest... 

第二种是更多的C++风格，第一种是更多的C风格，但都是有效的。