二叉查找树的遍历（迭代版，不使用栈或者队列(2)

else
  {
   pre = cur->left;
   while(pre->right != nullptr && pre->right != cur)
    pre = pre->right;
   if(pre->right == nullptr)
   {
    pre->right = cur;
    cur = cur->left;
   }
   else
   {
    cout<<cur->s<<" ";
    pre->right = nullptr;
    cur = cur->right;
   }
  }

测试代码

#include <iostream>
#include <string>
#include <fstream>
using namespace std;
struct node
{
 string s;
 node* left;
 node* right;
};
node* insert(node* root, const string& s);
void in_order_traverse_BST(node* root);
void main()
{
 ifstream in("data.txt");
 if(!in.good())
 {
  cout<<"error"<<endl;
  exit(0);
 }
 node* root = nullptr;
 while (!in.eof())
 {
  string s;
  in>>s;
  root = insert(root,s);
 }
 in_order_traverse_BST(root);
}

若有不清楚的地方还请见谅，多多交流。