溫故而知新。本文將回顧二叉搜索樹的基本知識，并用C++將它的三種depth-first search: 前序遍歷、中序遍歷和后序遍歷，以及一種breath first search: 層序遍歷算法分別實現(xiàn)出來。
1. BST的結(jié)構(gòu)
首先，我們先定義樹的結(jié)構(gòu)：
struct node
{
int data;
node *leftchild;
node *rightchild;
node(int val)
{
data = val;
leftchild = NULL;
rightchild = NULL;
}
};
接下來，我們實現(xiàn)基本的插入節(jié)點操作。根據(jù)BST的特點，要求保持節(jié)點之間的有序性，即左節(jié)點<根節(jié)點<右節(jié)點。首先找到新節(jié)點的插入位置，再將其插入即可。
void insert(node* root,int val)
{
node* tmp = new node(val);//創(chuàng)建新節(jié)點
if(root == NULL)
{
root = tmp;
return;
}
node* pre = root;
while(true)
{
if(pre->data >= val)
{
if(pre->leftchild == NULL)
{
pre->leftchild = tmp;
return;
}
pre = pre->leftchild;
}
else
{
if(pre->rightchild == NULL)
{
pre->rightchild = tmp;
return;
}
pre = pre->rightchild;
}
}
};
2. 前序、中序、后序遍歷的遞歸實現(xiàn)
首先明確一下三種遍歷的基本概念：
- 前序遍歷：根節(jié)點->左子樹->右子樹
- 中序遍歷：左子樹->根節(jié)點->右子樹
- 后序遍歷：左子樹->右子樹->根節(jié)點
其中中序遍歷比較特別，因為按照中序遍歷BST能夠得到有序的數(shù)列，這在很多題目中都有所應(yīng)用。
只要理解了三種遍歷的基本概念，它們的遞歸實現(xiàn)都比較容易寫出。
void preordertree(node* root)
{
if(root == NULL) return;
if(root!=NULL)
{
std::cout << root->data << " ";
preordertree(root->leftchild);
preordertree(root->rightchild);
}
};
void postordertree(node* root)
{
if(root == NULL) return;
if(root)
{
postordertree(root->leftchild);
postordertree(root->rightchild);
std::cout << root->data << " ";
}
}
void inordertree(node* root)
{
if(root)
{
inordertree(root->leftchild);
std::cout << root->data << " ";
inordertree(root->rightchild);
}
}
3. 前序、中序、后序遍歷的非遞歸實現(xiàn)
3.1 前序遍歷的非遞歸實現(xiàn)
前序遍歷的非遞歸實現(xiàn)主要需要借助stack。對于stack中任意一個節(jié)點，先訪問其本身并將其pop出來，再將其右節(jié)點和左節(jié)點分別壓入棧中即可。
void iterpreordertree(node* root)
{
if(root == NULL) return;
std::stack<node *> nstack;
nstack.push(root);
while(!nstack.empty())
{
node* tmp = nstack.top();
std::cout << tmp->data << " ";
nstack.pop();
if(tmp->rightchild)
nstack.push(tmp->rightchild);
if (tmp->leftchild)
nstack.push(tmp->leftchild);
}
std::cout << std::endl;
}
3.2 中序遍歷的非遞歸實現(xiàn)
中序遍歷的非遞歸實現(xiàn)的主要難點在于：因為首先要尋找到左節(jié)點，訪問完畢后需要回到根節(jié)點，并轉(zhuǎn)換方向?qū)ふ矣覀?cè)子樹。這里，我們用一個棧stack和一個節(jié)點cur來追蹤。首先將cur指定為根節(jié)點。
- 不斷搜尋cur的左子樹，并將中間路過的節(jié)點壓入棧中。
- 當(dāng)左子樹搜尋完畢之后，將cur重新賦值為nstack.top()，訪問過后將其彈出。
- 轉(zhuǎn)換cur到其右子樹上，并重復(fù)步驟1。
void iterinordertree(node* root)
{
if(root == NULL) return;
std::stack<node *> nstack;
node* cur = root;
while(cur || !nstack.empty())
{
//if cur is not NULL
if(cur)
{
nstack.push(cur);
cur = cur->leftchild;
}
else{
cur = nstack.top();
std::cout << cur->data << " ";
nstack.pop();
cur = cur->rightchild;
}
}
std::cout << std::endl;
}
3.3 后序遍歷的非遞歸實現(xiàn)
后序遍歷的非遞歸實現(xiàn)是三者中最難的，需要借助兩個stack來實現(xiàn)。
void iterpostordertree(node* root)
{
if(root == NULL) return;
std::stack<node *> first,second;
first.push(root);
while(!first.empty())
{
node* tmp = first.top();
first.pop();
second.push(tmp);
if(tmp->leftchild)
first.push(tmp->leftchild);
if (tmp->rightchild)
first.push(tmp->rightchild);
}
while (!second.empty()) {
std::cout << second.top()->data << " ";
second.pop();
}
std::cout << std::endl;
}
4. 層序遍歷
層序遍歷利用的是廣度優(yōu)先搜索，利用隊列，每次訪問一層，并將下一層的節(jié)點入隊。
void breathfirst(node* root)
{
if(root == NULL) return;
std::queue<node *> nqueue;
nqueue.push(root);
while (!nqueue.empty()) {
int n = nqueue.size();
for(int i = 0; i < n; i++)
{
node* cur = nqueue.front();
std::cout << cur->data << " ";
nqueue.pop();
if (cur->leftchild)
nqueue.push(cur->leftchild);
if(cur->rightchild)
nqueue.push(cur->rightchild);
}
}
std::cout << std::endl;
}
以上即是本文的全部內(nèi)容，感謝關(guān)注。
代碼清單： https://github.com/ShulinLiu/DataStructure-Algorithm/blob/master/BasicDataStructure/tree/tree.cpp
