二叉树的遍历整体上是分成两种的,一种是递归的方式,一种是非递归的方式。
前序遍历的递归方式:
根据每个节点的步骤来,先输出当前节点的值,再去管左子节点、最后再管右子节点。
递归的方法有个特点就是,只需要考虑当前步骤该做什么,下一步应该往哪走,即可。
void Pre(TreeNode* root){
if(root!=nullptr)
{
cout <<root->val;
Pre(root->left);
Pre(root->right);
}
}
前序遍历的非递归方式:
前序遍历的非递归方式是相对比较简单的,因为是从根节点开始,优先输出当前节点的值,再去管左子节点和右子节点。
这里我们取一个栈,将root节点先存入初始化的栈中,然后设定循环条件是,栈不为空,每次取栈顶节点的值,再将栈顶节点的右子节点和左子节点依次压入栈中。
(这里考虑非空并且由于栈的后入先出特性)
void Pre(TreeNode* root){
stack<TreeNode*> res;
res.push(root);
while(!res.empty()){
TreeNode* temp = res.top();
res.pop();
cout << temp->val;
if(temp->right)
res.push(temp->right);
if(temp->left)
res.push(temp->left);
}
}
中序遍历的递归方式:
递归的方式总的来说大同小异,只是每个步骤的逻辑处理顺序不一样。
void Ord(TreeNode* root){
if(root!=nullptr)
{
Ord(root->left);
cout << root->val;
Ord(root->right);
}
}
中序遍历的非递归方式:
这里其实就比较复杂了,因为我们在当前节点的处理,是优先当前节点的左子节点。不用递归的话,我们怎么样才能实现每个节点处理时,都优先处理
左子节点呢?优先输出左子节点,那就把从根节点开始左子节点依次入栈,那这样压栈完毕后,出栈的第一个必定是根节点左子树的最深的左子节点。
接着我们在查看当前出栈的右子节点是否为空,如果不为空便在输出当前节点的值之后将其入栈。整体代码如下。
void Ord(TreeNode* root){
stack<TreeNode*> res;
TreeNode* temp = root;
while(temp||!res.empty()){
while(temp)
{
res.push(temp);
temp = temp->left;
}
if(!res.empty())
{
temp = res.top();
res.pop();
cout << temp->val ;
temp = temp->right;
}
}
}
后序遍历的递归方式:
同上递归。
void Post(TreeNode* root){
if(root!=nullptr)
{
Post(root->left);
Post(root->right);
cout << root->val;
}
}
后序遍历的非递归方式:
取一个栈作为临时存储栈,由于栈的先进后出特性,所以得先把当前节点的右子节点先入栈,再将左子节点再入栈。
void Post(TreeNode* root){
TreeNode* temp = root;
stack<TreeNode*> res;
stack<TreeNode*> tempres;
while (temp || !tempres.empty()) {
if (temp) {
tempres.push(temp);//
res.push(temp);
temp = temp->right;
}
else {
temp = tempres.top();
tempres.pop();
temp = temp->left;
}
}
while(!res.empty()){
post.push_back(res.top()->val);
res.pop();
}
}
网友评论