详解二叉树的各种非递归遍历

简介: 详解二叉树的各种非递归遍历

   递归的本质就是压栈、回溯、弹栈,那我们模拟他这个过程。

大概可以写成下面的过程:

  1. 创建一个栈(可以是数组实现的栈或者使用语言提供的栈数据结构),用于暂存遍历过程中的节点。
  2. 初始化当前节点为根节点。
  3. 进入循环,判断条件为当前节点不为空或栈不为空。
  4. 在循环中,执行以下操作:
  • 如果当前节点不为空,将当前节点入栈,并将当前节点指向其左子节点(进入左子树)。
  • 如果当前节点为空,说明已经到达左子树的最底部,从栈中取出一个节点,访问该节点,并将当前节点指向其右子节点(进入右子树)。
  • 不断重复上述过程,直到当前节点为空且栈为空,完成遍历。

前序:

  • 创建一个栈,将根节点入栈。
  • 进入循环,判断条件为栈不为空。
  • 在循环中,取出栈顶节点,访问该节点,并依次将其右子节点和左子节点入栈。
// 非递归前序遍历函数
void preOrderTraversal(TreeNode* root) {
    if (root == nullptr)
        return;
 
    stack<TreeNode*> nodeStack; // 创建一个栈用于存储结点
 
    nodeStack.push(root); // 将根结点入栈
 
    while (!nodeStack.empty()) {
        TreeNode* currentNode = nodeStack.top(); // 取出栈顶结点
        nodeStack.pop(); // 弹出栈顶结点
 
        cout << currentNode->val << " "; // 访问当前结点
 
        if (currentNode->right)
            nodeStack.push(currentNode->right); // 先将右子结点入栈,因为前序遍历的顺序是根-左-右
        if (currentNode->left)
            nodeStack.push(currentNode->left); // 再将左子结点入栈
    }
}

中序:

  • 创建一个栈。
  • 从根节点开始,将当前节点和所有左子节点按顺序入栈,直到最左的叶子节点。
  • 进入循环,判断条件为当前节点为空且栈为空。
  • 在循环中,取出栈顶节点,访问该节点,并将当前节点指向其右子节点
vector<int> inorderTraversal(TreeNode* root) {
    vector<int> result; // 存放遍历结果的向量
    stack<TreeNode*> stack; // 用于模拟递归调用的栈
    TreeNode* current = root; // 当前节点
 
    while (current != nullptr || !stack.empty()) {
        // 将当前节点以及其左子树的所有左节点入栈
        while (current != nullptr) {
            stack.push(current); // 将当前节点入栈
            current = current->left; // 移动到左子节点
        }
 
        // 当左子树为空时,弹出栈顶节点并访问
        current = stack.top();
        stack.pop();
        result.push_back(current->val);
 
        // 遍历右子树
        current = current->right;
    }
 
    return result;
}

后序:


  • 创建两个栈。一个栈用于存储节点的顺序,另一个栈用于存储实际的后序遍历结果。
  • 将根节点入栈1。
  • 进入循环,判断条件为栈1不为空。
  • 在循环中,取出栈1的栈顶节点,将该节点入栈2,并依次将其左子节点和右子节点入栈1。
  • 重复上述过程直到栈1为空。此时,栈2中存储的就是后序遍历的结果,可以按顺序访问栈2中的节点。
// 非递归后序遍历函数
void postOrderTraversal(TreeNode* root) {
    if (root == nullptr)
        return;
        
    stack<TreeNode*> nodeStack; // 创建一个栈用于存储结点
    TreeNode* prevNode = nullptr; // 记录上一个访问过的结点
 
    while (root || !nodeStack.empty()) {
        if (root) {
            nodeStack.push(root); // 将当前结点入栈
            root = root->left; // 访问左子结点
        } else {
            TreeNode* topNode = nodeStack.top();
 
            if (topNode->right && topNode->right != prevNode) {
                root = topNode->right; // 若右子结点存在且未被访问过,则访问右子结点
            } else {
                cout << topNode->val << " "; // 访问当前结点
                nodeStack.pop(); // 弹出栈顶结点
                prevNode = topNode; // 更新上一个结点为当前结点
            }
        }
    }
}
相关文章
|
关系型数据库 MySQL Java
【面试题精讲】Mysql如何实现乐观锁
【面试题精讲】Mysql如何实现乐观锁
|
Oracle 关系型数据库 MySQL
MySQL复制表结构create table as与like的区别
MySQL复制表结构create table as与like的区别
335 0
第k小的数(2种快排解法、1种堆排解法)
第k小的数(2种快排解法、1种堆排解法)
236 0
|
8月前
|
存储 Java
几种锁:偏向锁、轻量级锁、重量级锁、自旋锁
**锁机制简介:** Java中,锁分为偏向锁、轻量级锁和重量级锁。偏向锁适用于单一线程多次获取同一锁的情况,减少无竞争下的性能消耗;轻量级锁在多线程竞争时通过自旋避免阻塞,提升效率;重量级锁则是在自旋超时或多个线程竞争时,将其他线程阻塞以防止CPU空转,但性能较低。锁的升级路径为:偏向锁 → 轻量级锁 → 重量级锁,且不可降级。偏向锁默认开启,可通过JVM参数调整或关闭。
321 13
几种锁:偏向锁、轻量级锁、重量级锁、自旋锁
|
存储 Linux C语言
(2)Qt中的字符串类型
本文介绍了Qt中的字符串类型QByteArray和QString,包括它们的构造函数、数据操作方法、查找操作、遍历操作以及与其他类型之间的转换,并解释了它们之间的区别。
670 5
(2)Qt中的字符串类型
|
10月前
|
JSON 前端开发 Java
【SpringMVC】基础入门(1)
spirngMVC,RequestMapping建立连接,RequestController,Requestparam,RequestBody传递参数、对象、数组、集合、JSON数据,JSON字符串和JAVA对象的转换
|
SQL 存储 NoSQL
现代数据库技术的演进与未来趋势
随着信息时代的发展,数据库技术已经成为现代应用程序和系统的核心。本文探讨了数据库技术从传统到现代的演进历程,分析了当前流行的数据库类型及其特点,并展望了未来数据库技术的发展趋势。
|
10月前
|
机器学习/深度学习 新零售 人工智能
基于阿里云AI购物助手解决方案的深度评测
阿里云推出的AI购物助手解决方案,采用模块化架构,涵盖智能对话引擎、商品知识图谱和个性化推荐引擎。评测显示其在智能咨询问答、个性化推荐和多模态交互方面表现出色,准确率高且响应迅速。改进建议包括提升复杂问题理解、简化推荐过程及优化话术。总体评价认为该方案技术先进,应用效果好,能显著提升电商购物体验并降低运营成本。
666 0
|
编解码 算法 计算机视觉
使用NumPy进行傅里叶变换:基础概念与实践应用
使用NumPy进行傅里叶变换:基础概念与实践应用
475 0
|
Web App开发 搜索推荐 NoSQL
如何搭建一个集成导航与在线工具的个性化浏览器私有书签(附详细搭建教程)
在这个信息爆炸的时代,我们都希望拥有一个能够轻松解决多端、多浏览器的收藏和笔记同步问题的神奇工具。Mtab书签正是为此而设计的顶级应用。它将基础导航、记事本、在线小工具和多端同步集于一身,为用户提供了更便利的网络浏览体验,并解决了多端同步的烦恼。
407 0
如何搭建一个集成导航与在线工具的个性化浏览器私有书签(附详细搭建教程)