C/C++教程

二叉树中序遍历(递归法和迭代法(非递归法))——C++

本文主要是介绍二叉树中序遍历(递归法和迭代法(非递归法))——C++,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

 声明:本文原题主要来自力扣,记录此博客主要是为自己学习总结,不做任何商业等活动!

二叉树的遍历有前序遍历、中序遍历、后序遍历和层次遍历,其中二叉树基本知识点可以参考博主上篇博客(二叉树基本知识点图文介绍(全网最简洁)_净无邪博客-CSDN博客),二叉树的前序遍历可以参考博主这篇博客(二叉树前序遍历(递归法和迭代法(即非递归法))——C++_净无邪博客-CSDN博客),本文主要总结二叉树的中序遍历。

一、二叉树中序遍历

中序遍历是先遍历左子节点left,在遍历父节点parent,最后遍历右子节点right,即遍历顺序:

left ——> parent ——> right

下面是力扣原题,写一个中序遍历程序。

给定一个二叉树的根节点 root ,返回它的 中序 遍历。

示例 1:

输入:root = [1,null,2,3]
输出:[1,3,2]

1.1递归法

递归法主要用编译器栈自动压入递归的函数参数和局部变量,依次按照中序遍历顺序有且仅有一次访问二叉树。下面是具体示例代码:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        if(root == nullptr)
            return datas;
        if(root->left != nullptr)
            inorderTraversal(root->left);
        datas.push_back(root->val);
        if(root->right != nullptr)
            inorderTraversal(root->right);
        return datas;
    }

private:
    vector<int> datas;
};

结果:

 1.2迭代法

迭代法是采用非递归方法实现二叉树的中序遍历,主要利用数据结构std::stack来实现,利用栈std::stack的先进后出特性依次压入待访问的节点,然后依次按照中序遍历顺序弹出和访问节点,确保每个节点有且仅有一次访问。

具体步骤如下:

a1 先将所有父节点和左子节点依次压入栈;

这样做的目的是为了先弹出左子节点,再弹出父节点,可以在弹出左子节点的时候进行遍历,同时处理右节点,比如将右节点压入栈,这样就实现了先访问左节点,然后父节点,最后右子节点。

while (cur != nullptr)
{
    nodeStack.push(cur);
    cur = cur->left;
}

a2 然后弹出一个节点,进行遍历;

此时弹出的节点前提是左子节点为空,则该节点是父节点,故需要在后面遍历右子节点

cur = nodeStack.top();
nodeStack.pop();
datas.push_back(cur->val);

a3 遍历右子节点,将其作为一棵右子节点树的父节点,继续循环第a1步骤,直到整个栈为空即可

while (cur != nullptr || !nodeStack.empty())
{
    while (cur != nullptr) // 控制父节点和左子树非空,则先压入父节点,然后压入左节点
    {
        // 循环将做父节点和左子树压入栈 ......
    }
    // 弹出栈和遍历节点 ......
    cur = cur->right; // 将弹出栈的右子节点当作右子树的父节点进行循环遍历
}

下面是完整代码实现:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        TreeNode* cur = root;
        std::stack<TreeNode *> nodeStack;
        while(cur != nullptr || !nodeStack.empty()) // 循环截止条件是父节点为空或栈为空
        {
            while(cur != nullptr) // 控制父节点和左子树非空,则先压入父节点,然后压入左节点
            {
                nodeStack.push(cur);
                cur = cur->left;
            }
            cur = nodeStack.top();
            nodeStack.pop();
            datas.push_back(cur->val);
            cur = cur->right; // 将弹出栈的右子节点当作父节点进行循环遍历
        }
        return datas;
    }
private:
    vector<int> datas;
};

结果:

1.3总结

二叉树的中序遍历递归法跟前序遍历差不多,但是迭代法在代码结构上却有较大差别,前序遍历主要通过一个栈先访问当前节点也就是父节点,然后再遍历左节点,接着遍历右节点,代码结构清晰易于理解;但是中序遍历的迭代法代码实现结构却不同,主要还是数据结构栈的性质,决定了中序遍历需要先将父节点压入栈,然后压入左节点,这是一个循环的步骤,直到左子树为空才停止压栈,此时需要弹出栈进行遍历该节点(可以看成父节点,左节点为空),遍历完后再将该节点的右节点作为右子树的父节点,重复前面步骤,直到整个栈为空即可完成每个节点中序遍历。

这篇关于二叉树中序遍历(递归法和迭代法(非递归法))——C++的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!