我们都知道在中序遍历的过程中，我们需要用一个栈来存储之前访问过的节点，主要是为了找到当前节点的后继节点，为此我们发现如下图所示的规律。

上图可以看出节点1的后继节点为2，节点2的后继节点为3，节点3的后继节点为4，节点4的后继节点为5，由上述描述可以发现当某个右节点没有右孩子时，其后继节点为其祖父，当其有右孩子时，其后继节点为其右孩子。当某个左节点没有右孩子时，其后继节点为其父亲，反之其后继节点为其右孩子。

从这段寻找后继节点的过程发现，其后继节点的位置与其是否存在右孩子有关，也即与其指向右侧的指针有关，因此我们是否可以使用右指针来指定其后继节点呢？答案是可以的。下图所示为使用右指针指向其后继节点后构成的新的图。

构造上图之后我们再一次遍历二叉查找树时，只需先向左找到第一个不存在左孩子的节点，然后依次打印其key值，打印完之后遍历其右孩子，则其遍历的路径如下图所示

从上图可以看出这样处理之后刚好实现了二叉查找树的中序遍历。下面为代码的具体实现。

构建一颗二叉查找树

node* create(const string& s)
{
?node* res = new node;
?res->left = nullptr;
?res->right = nullptr;
?res->s = s;
?return res;
}
node* insert(node* root, const string& s)
{
?if(root == nullptr)
?{
? root = create(s);
? return root;
?}
?node* temp = root;
?while(temp!=nullptr)
?{
? if(temp->s > s)
? {
? ?if(temp->left == nullptr)
? ?{
? ? temp->left = create(s);
? ? return root;
? ?}
? ?else
? ? temp = temp->left;
? }
? else
? {
? ?if(temp->right == nullptr)
? ?{
? ? temp->right = create(s);
? ? return root;
? ?}
? ?temp = temp->right;
? }
?}
}

遍历二叉查找树

void in_order_traverse_BST(node* root)
{
?node* cur = root;
?node* pre=nullptr;
?while(cur!=nullptr)
?{
? if(cur->left == nullptr)
? {
? ?cout<s<<" ";
? ?cur = cur->right;
? }
? 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<s<<" ";
? ? pre->right = nullptr;
? ? cur = cur->right;
? ?}
? }
?}
}

下面这段代码是创建右链接，以及恢复原来树的形状的代码，若有什么不明白的地方可以画一颗树来具体实现就行。

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<s<<" ";
? ? pre->right = nullptr;
? ? cur = cur->right;
? ?}
? }

测试代码

#include
#include
#include
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"<? exit(0);
?}
?node* root = nullptr;
?while (!in.eof())
?{
? string s;
? in>>s;
? root = insert(root,s);
?}
?in_order_traverse_BST(root);
}

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