尝试在 avl 树中实现查找

Question

我正在使用此代码 https://rosettacode.org/wiki/AVL_tree#C.2B.2B 作为 AVL 树的基础。默认情况下，该示例使用整数，但我需要存储字符串。所以我修改了代码来调试，主要是制作根 public 并尝试打印值。

22 /* AVL tree */
 23 template <class T>
 24 class AVLtree {
 25         public:
 26                 AVLtree(void);
 27                 ~AVLtree(void);
 28                 bool insert(T key);
 29                 void deleteKey(const T key);
 30                 void printBalance();
 31                 AVLnode<T> *root;
 32 
 33         private:
 34 
 35                 AVLnode<T>* rotateLeft          ( AVLnode<T> *a );
 36                 AVLnode<T>* rotateRight         ( AVLnode<T> *a );
 37                 AVLnode<T>* rotateLeftThenRight ( AVLnode<T> *n );
 38                 AVLnode<T>* rotateRightThenLeft ( AVLnode<T> *n );
 39                 void rebalance                  ( AVLnode<T> *n );
 40                 int height                      ( AVLnode<T> *n );
 41                 void setBalance                 ( AVLnode<T> *n );
 42                 void printBalance               ( AVLnode<T> *n );
 43                 void clearNode                  ( AVLnode<T> *n );
 44 };
..................................
247 int main(void)
248 {
249         AVLtree<std::string> t;
250 
251         std::cout << "Inserting integer values 1 to 10" << std::endl;
252         for (int i = 1; i <= 10; ++i)
253                 t.insert(i+" ");
254 
255         std::cout << "Printing balance: ";
256         t.printBalance();
257         std::cout << t.root->key + "\n";
258         std::cout << t.root->left->key + "\n";
259         std::cout << t.root->left->right->key + "\n";
260         std::cout << t.root->key;
261 
262 }

然而问题是打印出来的结果是

Inserting integer values 1 to 10
Printing balance: 1 0 -1 0 0 1 0 0 1 0 
ing balance: 
Printing balance: 
g balance: 
ing balance:

我也不知道为什么。

Answer 1

我认为您在这些行中将垃圾字符串插入到您的数据结构中：

for (int i = 1; i <= 10; ++i)
    t.insert(i+" ");

" " 的类型是 const char * ，当你给它加上一个整数时，你会得到另一个 const char * 与原始指针的偏移量。因为字符串 " " 恰好存储在程序中字符串 "Printing balance:" 之前，所以当您执行该代码时，您最终会生成指向 "Printing balance:" 字符串内部各个位置的指针。

要在 C++ 中正确地将数字转换为字符串，您可以使用 std::to_string.

尝试在 avl 树中实现查找

Attempting to implement find in avl tree

c++

avl-tree