我有一个简单的BST C++实现。我只是想按顺序添加数字并打印出来。问题是，在我尝试添加的 16 个数字中，我只能添加 12(省略 32、15、14 和 3(。我的控制台的输出如下所示：
在添加数字之前打印树：
列表为 空
已添加键 32。
关键 15 已经 已添加。
密钥 14 已添加。
键 3 有 已添加。
添加后按顺序打印树 数字：
2 4 21 50 52 64 70 76 80 83 87 100
节目结束于 退出代码：0
#include <iostream>
using namespace std;
class BST {
private:
struct node {
int data;
node * left;
node * right;
};
node * root;
void addLeafPrivate(int data, node * n);
void printInOrderPrivate(node *);
public:
BST();
node * createLeaf(int data);
void addLeaf(int data);
void printInOrder();
};
int main() {
int TreeKeys[16]= {50, 76, 21, 4, 32, 64, 15, 52, 14, 100, 83, 2, 3, 70, 87, 80};
BST bst;
cout << "Printing the tree before adding numbers: n";
bst.printInOrder();
for (int i = 0; i < 16; i++) {
bst.addLeaf(TreeKeys[i]);
}
cout << "Printing the tree in order after adding numbers: n";
bst.printInOrder();
return 0;
}
BST::BST() {root = NULL;}
BST::node * BST::createLeaf(int data) {
node * n = new node;
n->data = data;
n->right = NULL;
n->left = NULL;
return n;
}
void BST::addLeaf(int data) {
addLeafPrivate(data, root);
}
void BST::addLeafPrivate(int data, node * n) {
if (root == NULL) {
root = createLeaf(data);
}
else if (data < n->data) { // add recursively on left left side.
if (n->left != NULL){
addLeafPrivate(data, n->left);
}
else { // if left is empty
n->left = createLeaf(data);
}
}
else if (data > root->data) { // add recursively on right left side.
if (n->right != NULL) {
addLeafPrivate(data, n->right);
}
else { // right is empty
n->right = createLeaf(data);
}
}
else {
cout << "The key " << data << " has already been added.n";
}
}
void BST::printInOrder() {
printInOrderPrivate(root);
}
void BST::printInOrderPrivate(node * n) {
if (n != NULL) {
if (n->left != NULL) {
printInOrderPrivate(n->left);
}
cout << n->data << " ";
if (n->right != NULL) {
printInOrderPrivate(n->right);
}
}
else {
cout << "The list is emptyn";
}
}
else if (data > root->data) { // add recursively on right left side.
应该是
else if (data > n->data) { // add recursively on right left side.
问题始于你来32.由于21已经50，你的算法认为它已经插入32，当你执行root->data而不是正确的n->data时，而不是比较data值并抛出异常。
所以：检查左右是否有null，比较data是大于还是小于，并检查相等性。这样做可以让你更容易地找到这样的错误。