温故而知新。本文将回顾二叉搜索树的基本知识，并用C++将它的三种depth-first search: 前序遍历、中序遍历和后序遍历，以及一种breath first search: 层序遍历算法分别实现出来。
1. BST的结构
首先，我们先定义树的结构：
struct node
{
int data;
node *leftchild;
node *rightchild;
node(int val)
{
data = val;
leftchild = NULL;
rightchild = NULL;
}
};
接下来，我们实现基本的插入节点操作。根据BST的特点，要求保持节点之间的有序性，即左节点<根节点<右节点。首先找到新节点的插入位置，再将其插入即可。
void insert(node* root,int val)
{
node* tmp = new node(val);//创建新节点
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. 前序、中序、后序遍历的递归实现
首先明确一下三种遍历的基本概念：
- 前序遍历：根节点->左子树->右子树
- 中序遍历：左子树->根节点->右子树
- 后序遍历：左子树->右子树->根节点
其中中序遍历比较特别，因为按照中序遍历BST能够得到有序的数列，这在很多题目中都有所应用。
只要理解了三种遍历的基本概念，它们的递归实现都比较容易写出。
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. 前序、中序、后序遍历的非递归实现
3.1 前序遍历的非递归实现
前序遍历的非递归实现主要需要借助stack。对于stack中任意一个节点，先访问其本身并将其pop出来，再将其右节点和左节点分别压入栈中即可。
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 中序遍历的非递归实现
中序遍历的非递归实现的主要难点在于：因为首先要寻找到左节点，访问完毕后需要回到根节点，并转换方向寻找右侧子树。这里，我们用一个栈stack和一个节点cur来追踪。首先将cur指定为根节点。
- 不断搜寻cur的左子树，并将中间路过的节点压入栈中。
- 当左子树搜寻完毕之后，将cur重新赋值为nstack.top()，访问过后将其弹出。
- 转换cur到其右子树上，并重复步骤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 后序遍历的非递归实现
后序遍历的非递归实现是三者中最难的，需要借助两个stack来实现。
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. 层序遍历
层序遍历利用的是广度优先搜索，利用队列，每次访问一层，并将下一层的节点入队。
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;
}
以上即是本文的全部内容，感谢关注。
代码清单： https://github.com/ShulinLiu/DataStructure-Algorithm/blob/master/BasicDataStructure/tree/tree.cpp
