所以我的代码如下。我没有收到任何错误,它把所有东西都放在节点中就好了。但是根据我的调试语句,每次插入任何东西时,它都会找到根。我不确定这是否正确。但是根据作业的输出文件,当涉及到树的高度、遍历时,我的答案是不同的,而且我的叶子计数函数仍然有问题。不过是另一个故事。
根据调试语句,看起来一切都在正确进行。但我想我可能需要新的眼睛。我完全看不出我的遍历会如何改变,因为这实际上只是我在何处处理应该影响中序、前序和后序的节点的问题。
template <class T>
void BT<T>::insert(const T& item)
{
Node<T>* newNode;
newNode = new Node<T>(item);
insert(root, newNode);
}
template <class T>
void BT<T>::insert(struct Node<T> *&root, struct Node<T> *newNode)
{
if (root == NULL)
{
cout << "Root Found" << newNode->data << endl;
root = newNode;
}
else
{
if (newNode->data < root->data)
{
insert(root->left, newNode);
cout << "Inserting Left" << newNode-> data << endl;
}
else
{
insert(root->right, newNode);
cout << "Inserting Right" << newNode->data << endl;
}
}
}
我的高度函数如下,以防我的插入确实没问题。
template <class T>
int BT<T>::height() const
{
return height(root);
}
template <class T>
int BT<T>::height(Node<T>* root) const
{
if (root == NULL)
return 0;
else
{
if (height(root->right) > height(root->left))
return 1 + height(root-> right);
return 1 + height(root->left);
}
}
最佳答案
您需要更改调试语句的措辞
真的应该读(不是根节点)
cout << "Leaf Node Found" << newNode->data << endl;
它只有在第一次调用时才是根,之后任何对 node->left 或 node->right 的调用都会使它成为中间节点。
要写 height() 我会这样做:
template <class T>
int BT<T>::height(Node<T>* root) const
{
if (root == NULL) {return 0;}
return 1 + max(height(root->left),height(root->right));
}
关于C++ 二叉搜索树通过递归插入,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/207496/