二叉查找樹(Binary Search Tree)的遍歷的方法有很多，通常使用的是遞歸的遍歷，其便於理解，但是使用遞歸的話會造成程序運行的空間浪費，效率並不高。為此可以使用一個棧來模擬遞歸的過程，實現迭代版的二叉查找樹的遍歷。但是會使用到額外的存儲空間，雖說在運行效率上比遞歸版的有所提高，但是額外的存儲空間還是一定的浪費。但是如何減少額外的存儲空間呢？我們知道二叉查找樹是可以轉換為一個雙向環形鏈表(二叉查找樹與雙向環形鏈表的轉化)，而鏈表的遍歷是不需要額外的空間的，因此我們可以考慮通過充分利用樹的節點的兩個指針來優化遍歷的過程。
二叉樹的常見問題及其解決程序 http://www.linuxidc.com/Linux/2013-04/83661.htm
【遞歸】二叉樹的先序建立及遍歷 http://www.linuxidc.com/Linux/2012-12/75608.htm
在JAVA中實現的二叉樹結構 http://www.linuxidc.com/Linux/2008-12/17690.htm
【非遞歸】二叉樹的建立及遍歷 http://www.linuxidc.com/Linux/2012-12/75607.htm
二叉樹遞歸實現與二重指針 http://www.linuxidc.com/Linux/2013-07/87373.htm
二叉樹先序中序非遞歸算法 http://www.linuxidc.com/Linux/2014-06/102935.htm
輕松搞定面試中的二叉樹題目 http://www.linuxidc.com/linux/2014-07/104857.htm
我們都知道在中序遍歷的過程中，我們需要用一個棧來存儲之前訪問過的節點，主要是為了找到當前節點的後繼節點，為此我們發現如下圖所示的規律。
上圖可以看出節點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<<cur->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<<cur->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<<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);
}
若有不清楚的地方還請見諒，多多交流。
