|
2019年9月11日09:13:41 二叉树的遍历向来是 二叉树学习和应用的重中之重，虽然树结构 使用递归会使得我们的代码更加简洁，但是在这里 我也把非递归版本代码也进行详解。而二叉树 作为DSA中极为重要的一种数据结构，二叉树的基础学习是给后面学习 更加高级的数据结构做铺垫的。话不多说，先看一下 二叉树的遍历吧。
二叉树的遍历
基本概念二叉树的遍历方式先序遍历1.1 先序遍历的递归版本如下：1.2 先序遍历的非递归版本如下：
中序遍历2.1 中序遍历的递归版本如下：2.2 中序遍历的非递归版本如下：
后序遍历3.1 后序遍历的递归版本如下：3.2 后序遍历的非递归版本如下：
层次遍历4.1 层次遍历的递归版本如下：4.2 层次遍历的非递归版本如下：
基本概念
遍历：从这棵树的根节点出发，按照某种 次序 逐个依次访问树中的每个节点，直到所有节点都被 有且只有一次被访问到为止。 次序：树的一对多的关系，也就决定了 不同于之前线性结构的比较简单的遍历次序（从头到尾、从尾到头、循环、双向等）。正如这种一对多的结构，决定了 树不存在所谓的 唯一前驱和后继的关系，那么在成功遍历一个节点之后 遍历哪个节点是有多个选择的。正是这里不同的选择也确定了不同的遍历次序，因此树就有了这几种遍历方式。 访问：上面说的访问的意思就是：根据我们的需要所进行的动作。最常见的访问其值val，或者进行一些其他的节点操作等。
二叉树的遍历方式
二叉树的遍历方式是有很多种的，但是通常我们规定为从左到右的遍历方式（当然从右到左也是可以的，只是可能不太符合人们的习惯），遍历主要分为以下四种：
先序遍历中序遍历后序遍历层序遍历
先序遍历
其定义：若二叉树为空，则空操作返回；不为空则先访问根结点，然后先序遍历左子树，再先序遍历右子树。遍历过程如下图所示：  因此上面这棵二叉树的 先序遍历，次序为：ABDGHCEIF 遍历步骤如下：
二叉树不空，访问根节点，即AA的左子树不空，先序遍历A的左子树。左子树的根节点为B，访问 即：ABB的左子树不空，先序遍历B的左子树。左子树的根节点为D，访问 即：ABDD的左子树不空，先序遍历D的左子树。左子树的根节点为G，访问 即：ABDGG的左子树为空 返还上一层G的右子树为空 返还上一层D的右子树不空，先序遍历D的右子树。右子树的根节点为H，访问 即：ABDGHH的左子树为空 返还上一层H的右子树为空 返还上一层B的右子树为空 返还上一层A的右子树不空，先序遍历A的右子树。右子树的根节点为C，访问 即：ABDGHCC的左子树不空，先序遍历C的左子树。左子树的根节点为E，访问 即：ABDGHCEE的左子树为空 返还上一层E的右子树不空，先序遍历E的右子树。右子树的根节点为I，访问 即：ABDGHCEII的左子树为空 返还上一层I的右子树为空 返还上一层C的右子树不空，先序遍历C的右子树。右子树的根节点为F，访问 即：ABDGHCEIFF的左子树为空 返还上一层F的右子树为空 返还上一层
代码如下：
1.1 先序遍历的递归版本如下：
/**
* 先序遍历的递归实现，直接根据定义，首先先访问根节点，
* 然后先序遍历左子树，接着先序遍历右子树。
* 上述的每个先序遍历就是一个递归的过程。
*/
class TreeNode
{
public:
TreeNode(char C):val(C),left(nullptr),right(nullptr){}
//先序遍历 递归实现
static void preOrder_Operator(TreeNode* this_root, vector& vec)
{
if (this_root != nullptr)
{
vec.push_back(this_root->val);
preOrder_Operator(this_root->left, vec);
preOrder_Operator(this_root->right, vec);
}
}
//先序遍历 把顺序保存在一个数组中 递归实现
vector preOrder(TreeNode* root)
{
vectormyvec;
if (root == nullptr)
return myvec;
preOrder_Operator(root, myvec);
return myvec;
}
char val;
TreeNode* left;
TreeNode* right;
};
测试如下：  代码如下：
1.2 先序遍历的非递归版本如下：
/*
* 先序遍历的非递归实现，需要借助栈这个数据结构，由于前先遍历是
* 先访问根节点，然后前序遍历左子树，接着前序遍历右子树。
* 那么非递归实现的话，先压入根节点，然后打印栈顶元素，但是由于
* 出栈和入栈的顺序是相反的，因此我们接着需要先压入右孩子，再压入左孩子
* 然后打印栈顶元素，继续压入左孩子的右孩子，左孩子的左孩子···
* 上述便是迭代循环的过程。
*/
//先序遍历 把顺序保存在一个数组中 非递归实现
vector preOrder(TreeNode* root)
{
vectormyvec;
if (root == nullptr)
return myvec;
stackmystack;
mystack.push(root);
while (!mystack.empty())
{
TreeNode* top_node = mystack.top();
myvec.push_back(top_node->val);
mystack.pop();
//出栈和入栈的顺序是相反的
if (top_node->right != nullptr)
{
mystack.push(top_node->right);
}
if (top_node->left != nullptr)
{
mystack.push(top_node->left);
}
}
return myvec;
}
中序遍历
其定义：若二叉树为空，则空操作返回；不为空则从根结点开始(注：并不是先访问根结点)，中序遍历根结点的左子树，然后是访问根结点，最后中序遍历右子树。遍历过程如下图所示： 因此上面这棵二叉树的 中序遍历，次序为：GDHBAEICF 遍历步骤如下：
二叉树不空，根节点A存在左子树，则中序遍历其左子树。左子树根为BB存在左子树，则中序遍历其左子树。左子树根为DD存在左子树，则中序遍历其左子树。左子树根为GG的左子树为空，返还上一层访问节点G，即GG的右子树为空，返还上一层访问节点D，即GDD存在右子树，则中序遍历其右子树。右子树根为HH的左子树为空，返还上一层访问节点H，即GDHH的右子树为空，返还上一层访问节点B，即GDHBB的右子树为空，返还上一层访问节点A，即GDHBAA存在右子树，则中序遍历其右子树。右子树根为CC存在左子树，则中序遍历其左子树。左子树根为EE的左子树为空，返还上一层访问节点E，即GDHBAEE存在右子树，则中序遍历其右子树。右子树根为II的左子树为空，返还上一层访问节点I，即GDHBAEII的右子树为空，返还上一层访问节点C，即GDHBAEICC存在右子树，则中序遍历其右子树。右子树根为FF的左子树为空，返还上一层访问节点F，即GDHBAEICFF的右子树为空，返还上一层
代码如下：
2.1 中序遍历的递归版本如下：
/*
* 中序遍历的递归实现，根据定义，首先中序遍历左子树，
* 再打印根节点，然后再中序遍历右子树。
* 上述的每个中序遍历就是一个递归的过程。
*/
//中序遍历 递归实现
static void inOrder_Operator(TreeNode* this_root, vector& vec)
{
if (this_root != nullptr)
{
inOrder_Operator(this_root->left, vec);
vec.push_back(this_root->val);
inOrder_Operator(this_root->right, vec);
}
}
//中序遍历 把顺序保存在一个数组中 递归实现
vectorinOrder(TreeNode* root)
{
vectormyvec;
if (root == nullptr)
return myvec;
inOrder_Operator(root, myvec);
return myvec;
}
测试如下：  代码如下：
2.2 中序遍历的非递归版本如下：
/*
* 中序遍历的非递归实现，首先应该一直向左遍历，将结点压栈，
* 直到结点为空，然后我们打印该节点值，并将其出栈，并继续遍历该节点的右子树
* 继续上述过程。
*/
//中序遍历 把顺序保存在一个数组中 非递归实现
vectorinOrder(TreeNode* root)
{
vectormyvec;
if (root == nullptr)
return myvec;
stackmystack;
TreeNode* top_node = root;
while (!mystack.empty() || top_node!=nullptr)
{
if (top_node!= nullptr)//左孩子存在 一直走
{
mystack.push(top_node);
top_node = top_node->left;
}
else
{
top_node = mystack.top();
myvec.push_back(top_node->val);
mystack.pop();
top_node = top_node->right;
}
}
return myvec;
}
后序遍历
其定义：若二叉树为空，则空操作返回；不为空则从左到右先叶子后结点的方式遍历访问左右子树，最后是访问根结点。遍历过程如下图所示：  因此上面这棵二叉树的 后序遍历，次序为：GHDBIEFCA 遍历步骤如下：
二叉树不空，根节点A存在左子树，则后序遍历其左子树。左子树根为BB存在左子树，则后序遍历其左子树。左子树根为DD存在左子树，则后序遍历其左子树。左子树根为GG的左子树为空，返还上一层G的右子树为空，返还上一层访问节点G，即GD存在右子树，则后序遍历其左子树。右子树根为HH的左子树为空，返还上一层H的右子树为空，返还上一层访问节点H，即GH访问节点D，即GHDB的右子树为空，返还上一层访问节点B，即GHDBA存在右子树，则后序遍历其右子树。右子树根为CC存在左子树，则后序遍历其左子树。左子树根为EE的左子树为空，返还上一层E存在右子树，则后序遍历其右子树。右子树根为II的左子树为空，返还上一层I的右子树为空，返还上一层访问节点I，即GHDBI访问节点E，即GHDBIEC存在右子树，则后序遍历其右子树。右子树根为FF的左子树为空，返还上一层F的右子树为空，返还上一层访问节点F，即GHDBIEF访问节点C，即GHDBIEFC访问节点A，即GHDBIEFCA
代码如下：
3.1 后序遍历的递归版本如下：
/*
* 后序遍历的递归实现，只需先后序遍历左子树，再后序遍历右子树
* 最后打印根节点值即可。
* 上述的每个后序遍历就是一个递归的过程。
*/
//后序遍历 递归实现
static void lastOrder_Operator(TreeNode* this_root, vector& vec)
{
if (this_root != nullptr)
{
lastOrder_Operator(this_root->left, vec);
lastOrder_Operator(this_root->right, vec);
vec.push_back(this_root->val);
}
}
//后序遍历 把顺序保存在一个数组中 递归实现
vectorlastOrder(TreeNode* root)
{
vectormyvec;
if (root == nullptr)
return myvec;
lastOrder_Operator(root, myvec);
return myvec;
}
测试如下：  代码如下：
3.2 后序遍历的非递归版本如下：
/*
* 后序遍历的非递归实现，由于其根节点最后打印，因此这里需要借助两个栈来完成，
* 因为需要借助一个辅助栈来保存其父节点，而另一个栈则用来保存我们的结果集。
* 注意压栈顺序，本来应该先压右孩子，再压左孩子。但是使用另一个结果栈
* 来存储结果集，辅助栈中的元素最终是出栈并压入结果栈的，因此，程序中
* 应该先压入左孩子，再压入右孩子。
* 然后每次循环将栈顶元素出栈并压入结果栈中。
* 最后，结果栈中所存储的就是我们所需的后序遍历结果集。打印出栈中所有的
* 元素即可
*/
//后序遍历 把顺序保存在一个数组中 非递归实现
vectorlastOrder(TreeNode* root)
{
vectormyvec;
if (root == nullptr)
return myvec;
stackmystack;//这个作为工作栈
mystack.push(root);
while (!mystack.empty())
{
TreeNode* top_node = mystack.top();
myvec.push_back(top_node->val); //这个入结果数组顺序是反向的
mystack.pop();
if (top_node->left != nullptr)//因为入栈和出栈顺序相反
mystack.push(top_node->left);
if (top_node->right != nullptr)
mystack.push(top_node->right);
}
//把最终的顺序一反序即可 不用再用临时结果栈了
reverse(myvec.begin(), myvec.end());
return myvec;
}
|