二叉树的遍历是指从根结点出发,按照某种次序依次访问二叉树中所有结点,使得每个结点被访问一次且仅被访问一次。
在二叉树的遍历中存在三种较为常用的遍历方式:前序遍历、中序遍历、后序遍历。(从上学期一直拖到现在才去了解)
我参考了小吴师兄的一文弄懂二叉树的三种遍历
准备
在了解二叉树的三序遍历之前,先来看一下这"三序"是什么。
"前" 即为左节点
"中" 即为当前节点
"后" 即为右节点
这里的三个遍历就以我前面写的二叉搜索树为例吧。
前序遍历
使用递归方式实现前序遍历的具体过程为:
- 先访问根节点
- 再序遍历左子树
- 最后序遍历右子树
代码实现
/*****************************************************************
Function:preorderTraversal
Description:前序遍历。
*****************************************************************/
void BST::__preorderTraversal(Node* node, vector<int> &res)
{
if (node)
{
res.push_back(node->value);
__preorderTraversal(node->left, res);
__preorderTraversal(node->right, res);
}
return;
}
vector<int> BST::preorderTraversal(Node* node)
{
vector<int> res;
__preorderTraversal(node, res);
return res;
}
中序遍历
使用递归方式实现中序遍历的具体过程为:
- 先中序遍历左子树
- 再访问根节点
- 最后中序遍历右子树
代码实现
/*****************************************************************
Function:inorderTraversal
Description:中序遍历。
*****************************************************************/
void BST::__inorderTraversal(Node* node, vector<int> &res)
{
if (node)
{
__inorderTraversal(node->left, res);
res.push_back(node->value);
__inorderTraversal(node->right, res);
}
return;
}
vector<int> BST::inorderTraversal(Node* node)
{
vector<int> res;
__inorderTraversal(node, res);
return res;
}
后序遍历
使用递归方式实现后序遍历的具体过程为:
- 先后序遍历左子树
- 再后序遍历右子树
- 最后访问根节点
代码实现
/*****************************************************************
Function:postorderTraversal
Description:后序遍历。
*****************************************************************/
void BST::__postorderTraversal(Node* node, vector<int> &res)
{
if (node)
{
__postorderTraversal(node->left, res);
__postorderTraversal(node->right, res);
res.push_back(node->value);
}
return;
}
vector<int> BST::postorderTraversal(Node* node)
{
vector<int> res;
__postorderTraversal(node, res);
return res;
}