二叉搜索树：根在 Inorder 期间保持为空 (C++)

Question

所以我对二叉搜索树有点陌生，我正在尝试制作一棵二叉树，其中每个节点都是一个字符串向量。那么每次插入都需要一个字符串，并且只考虑该字符串的第一个字母。基于前 2 个字母，它将将该字符串附加到现有节点，其中所有字符串共享相同的前 2 个字母，或者创建一个新节点，该节点将包含具有所有相同前 2 个字母的字符串向量。我知道很奇怪。这不是我的主意。

我尝试通过在每次插入时显示根目录来缩小问题所在的范围。插入似乎都工作正常，但只要我想按 Inorder 显示节点，根似乎就消失了，但几乎就像它不可见一样。基于输出，这是非常明显的。我的猜测是它为空，但我不确定。抱歉，如果这不是最好的提问方式。这是我的第一个问题。

这是我的代码：

#include <iostream> 
#include <string>
#include <vector>
//#include "stringSlicer.h"
using namespace std; 
  
class BST  
{ 
    vector<string> data; 
    BST *left, *right; 
  
public: 
    // Default constructor. 
    BST(); 
  
    // Parameterized constructor. 
    BST(string); 
  
    // Insert function. 
    BST* Insert(BST*, string); 
  
    // Inorder traversal. 
    void Inorder(BST*); 

    // PreOrder Traversal.
    void PreOrder(BST*);

    // PostOrder Traversal
    void PostOrder(BST*);

    // string slicer
    string strSlice(string);

    // print vector
    void printVector(vector<string>);
}; 
  
// Default Constructor definition. 
BST ::BST() 
    : data(0) 
    , left(NULL) 
    , right(NULL) 
{ 
} 
  
// Parameterized Constructor definition. 
BST ::BST(string value) 
{ 
    if(data.empty()){
        data.push_back(strSlice(value));
    }
        data.push_back(value); 
    
    left = right = NULL; 
} 
  
// String slicing function definition
string BST ::strSlice(string word){
    string word2 = "";
    word2 += word[0];
    word2 += word[1];
    return word2;
}


// print vector function definition
void BST ::printVector(vector<string> dataVector){
    for(int i = 0; i < dataVector.size(); i ++){
        cout << dataVector.at(i) << " ";
        cout << "end of this node";
    }
}

// Insert function definition. 
BST* BST ::Insert(BST* root, string value) 
{ 
    if (!root)  
    { 
        // Insert the first node, if root is NULL. 

        return new BST(value); 
    } 
  
    // Insert data. 
    if (strSlice(value).compare(root->data.at(0)) > 0)  
    { 
        // Insert right node data, if the 'value' 
        // to be inserted is greater than 'root' node data. 
        cout << value << " is being put in the right node " << value << " > " << root->data.at(0) << endl;
        // Process right nodes. 
        root->right = Insert(root->right, value); 
        
    } else if (strSlice(value).compare(root->data.at(0)) == 0) {

        cout << value << " is being put in the same node " << value << " = " << root->data.at(0)  << endl;
        root->data.push_back(value);
    }
    else 
    { 
        // Insert left node data, if the 'value' 
        // to be inserted is greater than 'root' node data. 
        cout << value << " is being put in the left node " << value << " < " << root->data.at(0) << endl;
        // Process left nodes. 
        root->left = Insert(root->left, value); 
    } 
  
    // Return 'root' node, after insertion. 
    cout << "after insert root is " << root << endl;
    return root; 
} 
  
// Inorder traversal function. 
// This gives data in sorted order. 
void BST ::Inorder(BST* root) 
{ 
    cout << "root is " << endl;
    if (!root) { 
        return; 
    } 
    Inorder(root->left); 
    printVector(data);
    cout << endl; 
    Inorder(root->right); 
} 

int main() {
    const int size = 5;
    string array [size] = {"hi","hillo","bye","chao","elo"};


     BST b, *root = NULL;
     cout << "root is " << root << endl;
     root = b.Insert(root, array[0]); 
     for (int i = 1; i < size; i ++){
         b.Insert(root, array[i]);
     }
     
     
  
    b.Inorder(root); 
    return 0; 
}

这是输出：

root is 0
hillo is being put in the same node hillo = hi
after insert root is 0xeb7f10
bye is being put in the left node bye < hi
after insert root is 0xeb7f10
chao is being put in the left node chao < hi
chao is being put in the right node chao > by
after insert root is 0xeb7f30
after insert root is 0xeb7f10
elo is being put in the left node elo < hi
elo is being put in the right node elo > by
elo is being put in the right node elo > ch
after insert root is 0xeb7f88
after insert root is 0xeb7f30
after insert root is 0xeb7f10
root is
root is
root is

root is
root is

root is
root is

root is

root is

Answer 1

问题：

您的节点不是 NULL，但您没有打印其中任何节点的数据。使用语句 printVector(data); 您只打印对象 b.

的数据

解法：

将 printVector(data); 更改为 printVector(root->data);。

附加信息：

using namespace std; 被认为是一种不好的做法（更多信息 here）。
与其创建对象 b 只是为了使用 class BST 的方法，不如将方法设为静态并将节点作为参数传递。它更简洁，有助于避免这种情况下的混淆。
我个人建议您在 C++ 中使用 nullptr 而不是 NULL。
即使 root 是 NULL，Inorder 方法也会在返回之前执行 "cout << "root is " << endl;"，因此会输出不必要的行。
您应该使用 delete 来释放您使用 new 存储的数据。

二叉搜索树：根在 Inorder 期间保持为空 (C++)

Binary Search Tree: root remains null during Inorder (C++)

c++

binary-tree

vector