在计算机科学中，二叉树是一种非常重要和常见的数据结构，它具有广泛的应用，例如在搜索引擎和数据库中都有广泛的应用。在二叉树的遍历过程中，我们可以使用递归和非递归两种方法来实现。本文将介绍如何使用C++实现二叉树的非递归遍历。

一、中序遍历

中序遍历的顺序为：左子树、根节点、右子树。使用栈的非递归写法如下：

void inorder(TreeNode* root) {
  stack<TreeNode*> st;
  TreeNode* node = root;
  while(!st.empty() || node != NULL) {
    while(node != NULL) {
      st.push(node);
      node = node->left;
    }
    if(!st.empty()) {
      node = st.top();
      cout << node->val << " ";
      st.pop();
      node = node->right;
    }
  }
}

我们使用一个栈来帮助我们实现二叉树的中序遍历。将树的根节点入栈，然后将栈顶元素出栈并输出，再将当前节点的右子树和左子树分别入栈。如果当前节点为空且栈为空，则中序遍历完成。

二、前序遍历

前序遍历的顺序为：根节点、左子树、右子树。使用栈的非递归写法如下：

void preorder(TreeNode* root) {
  if(root == NULL) return;
  stack<TreeNode*> st;
  st.push(root);
  while(!st.empty()) {
    TreeNode* node = st.top();
    cout << node->val << " ";
    st.pop();
    if(node->right != NULL) {
      st.push(node->right);
    }
    if(node->left != NULL) {
      st.push(node->left);
    }
  }
}

我们使用一个栈来帮助我们实现二叉树的前序遍历。首先将根节点入栈，然后将栈顶元素出栈并输出，再将当前节点的右子树和左子树分别入栈。

三、后序遍历

后序遍历的顺序为：左子树、右子树、根节点。使用栈的非递归写法如下：

void postorder(TreeNode* root) {
  stack<TreeNode*> st;
  TreeNode* node = root;
  TreeNode* last_visited = NULL;
  while(!st.empty() || node != NULL) {
    while(node != NULL) {
      st.push(node);
      node = node->left;
    }
    TreeNode* tmp = st.top();
    if(tmp->right == NULL || tmp->right == last_visited) {
      cout << tmp->val << " ";
      st.pop();
      last_visited = tmp;
    } else
      node = tmp->right;
    
  }
}

我们使用一个栈来帮助我们实现二叉树的后序遍历。我们先将根节点入栈，并且使用一个指针记录上一个访问的节点。当栈顶元素没有右子树或者右子树已经被访问过的时候，我们就可以将其弹出并输出。如果当前节点有右子树，则将其压入栈中并将当前节点指向右子树。

总结

本文介绍了如何使用C++实现二叉树的非递归遍历。中序遍历、前序遍历和后序遍历是二叉树最重要的三种遍历方式，在实际开发中都有广泛的应用。通过本文的介绍，相信读者们已经掌握了如何实现二叉树的非递归遍历，并且可以根据需要灵活的使用二叉树的遍历方式。

相似文章
• C++代码实现部分接收并显示数据
  在C++语言中，使用输入流实现数据的输入，使用输出流实现数据的输出。对于部分数据的输入，可以使用输入流的一些方法来实现。
  
  
• C++重载++i运算符
  在C++编程中，重载运算符是一种非常有用的功能，使用它可以轻松地实现各种复杂的操作。在这些运算符中，++i运算符是一种特殊的运算符，它可以用来自增变量的值。在本文中，我们将学习如何重载++i运算符以方便我们的编程。
  
  
• 学习C++所需计算机配置要求
  C++是一种面向对象的编程语言，是众多程序员的首选。想要学习C++，需要一台良好的计算机配置。这篇文章将为您介绍学习C++所需的计算机配置要求。
  
  
• C++数组的使用方法
  C++是一种面向对象的编程语言，它提供了许多常用的数据结构来存储和操作数据。数组是其中一种非常常见的数据结构，它可以用于存储一系列相同类型的数据，并且支持快速的元素访问和修改。
  
  
• C++使用for循环打印10次“你好”
  C++是一种高级编程语言，它在计算机编程中广泛应用。它可以通过编写一些代码来实现各种任务，其中包括使用for循环打印10次“你好”。
  
  
• C++实现二分查找
  在计算机中，二分查找是一种常用的搜索算法，也被称为折半查找。C++是一种高级编程语言，它也有内置的函数可以实现二分查找。
  
  
• C++ 多维向量（vector）
  C++是一种流行的编程语言，它提供了多种数据结构，其中多维向量（vector）是一种非常有用的数据结构，可用于存储任意数量的元素。
  
  
• C++如何打包exe文件
  C++是一种广泛使用的编程语言，它被用于许多不同类型的应用程序的开发。在某些情况下，您可能需要将您的C++应用程序打包成exe文件以便用户可以轻松地运行它。下面，我们将探讨如何打包C++
  
  
• 深入理解C++中数值类型的转换操作
  在C++中，数值类型转换操作是一个非常重要的知识点，其涉及到了类型的精度、数据的有效性以及程序的性能等问题。因此，我们需要深入理解C++中数值类型的转换操作，以便正确地使用和优化程序。
  
  
• C++时间函数：获取毫秒级时间
  C++是一门强大的编程语言，可以用于开发各种类型的应用，从通用的桌面应用程序到嵌入式系统和游戏。在开发应用程序时，了解如何测量程序执行时间是非常关键的。为了实现这一目标，C++提供了许多时间函数，这些函数可以帮助程序员测量程序运行时间。
  
  
• C++循环结构详解
  C++作为一门编程语言，在循环结构上具有丰富的特性和功能，可以大大提高程序的效率，降低编程难度，更好地满足不同编程需求。
  
  
• C++整型数据类型的范围简介
  C++是一种面向对象的编程语言，也是许多程序员喜欢使用的语言之一。在C++语言中，整型数据类型是一种非常常见的数据类型，它可以用来存储整数值。然而，不同的整型数据类型具有不同的范围，因此在选择适当的数据类型时需要了解其范围。
  
  
• C++如何输出字符数组
  在C++语言中，输出字符数组是一项基本操作。一个字符数组实际上就是一个字符类型的指针，它指向一个包含多个字符的数组。输出一个字符数组的含义就是将该数组的所有字符按顺序依次输出。
  
  
• C++如何添加DLL文件
  C++是一种强大的编程语言，具有许多功能，其中一个是添加DLL文件。DLL文件（动态链接库）是预编译并包含代码和数据的文件，其可在应用程序之间共享。
  
  
• 微软 Visual C++ 2015-2019
  微软
  
  
• C++中的向上取整函数
  C++是一种高级编程语言，支持许多数学函数，包括向上取整函数。向上取整函数是对一个浮点数进行取整操作，使其变为不小于该数的最小整数。在C++中，向上取整函数由
  
  
• 【教程】C++如何求解方程组
  在数学的世界里，求解方程组是一项基本的技能。C++语言作为计算机科学中的一门编程语言，也可以通过其强大的计算能力来求解方程组。在本文中，我将为大家介绍如何使用C++语言来求解方程组。
  
  
• 如何在C++中使用取余运算？
  在C++中，取余运算是一个非常重要的运算符。它也常常被称为模运算或者是余数运算。在本文中，我们将会探讨如何在C++中使用取余运算。
  
  
• C++ 构造函数
  C++
  
  
• C++如何获取当前时间戳
  C++是一种快速、高效的编程语言，广泛应用于各种应用程序和领域。在某些情况下，您可能需要在C++程序中获取当前时间戳。时间戳是指特定时间点的数字表示形式，通常是距离某个基准日期/时间的秒数。
  
  
• C++面向对象计算圆面积
  C++是一种流行的编程语言，它支持面向对象编程范式的实现，并且易于学习和使用。在本文中，我们将探讨如何使用C++来计算圆的面积。
  
  
• C++标准库的作用是什么？
  C++标准库是为C++编程语言提供的一套标准化的库文件，它包含了C++编程中常用的函数和对象等内容。C++标准库的作用是方便C++编程人员进行程序开发，提高程序开发效率和程序的可维护性。
  
  
• C++ 实现英文文章中指定单词出现次数的统计
  C++是一种常用的计算机编程语言，可以用来实现各种实用的工具和程序。在英文文章中，我们有时需要对特定的单词出现次数进行统计，这可以帮助我们更好地理解文章的主题和内容。
  
  
• C++跳一跳课程设计报告
  C++
  
  
• C++新手必看：超简洁的刷题网站推荐
  C++是一门广受欢迎的编程语言，同时也是一门需要不断练习的语言。尤其对于C++初学者来说，刷题是不可或缺的练习方法。然而，许多新手发现，大多数的题库都非常庞大且复杂，导致难以入手。有没有一个简洁易懂的刷题网站呢？答案是有的，下面介绍几个超简
  
  
• C++中OP的含义是什么？
  C++是一种广泛使用的编程语言，它有许多不同的运算符，在其中一个常见的运算符是OP。那么OP在C++中的含义是什么呢？
  
  
• C++对象实例化的方式和方法
  在C++语言中，对象是解决问题的一种重要方式。实例化一个对象是将类定义机械化的过程。对象实例化的方式和方法有以下几种：
  
  
• C++中的模运算操作
  C++的模运算操作被广泛用于计算机编程当中，尤其是在数学运算方面。C++中的模运算操作符为“%”，它表示除法后所得的余数，也被称为取模运算。
  
  
• C++继承关系示例
  C++是一门流行的编程语言，它能够处理许多不同的编程任务。其中一项重要的功能就是C++继承关系，它是编写高效可重用代码的关键。下面是一个C++继承关系示例，它能够帮助你更好地了解这个重要的概念。
  
  
• 用Node.js打造C++扩展的作者
  在今天的编程领域，C++和Node.js已经成为非常流行的开发语言之一。Node.js提供了强大的后端开发能力，而C++则提供了高性能的计算能力。那么，如何将这两者结合起来，打造出一个高性能的扩展呢？
  
  
• C++中的“
  C++是一种面向对象的编程语言，是被广泛应用于软件开发、游戏开发、算法设计等领域的编程语言之一。在C++中，“|”是一个按位或运算符。
  
  
• C++字符串输出格式详解
  C++是一种广为使用的编程语言，其中字符串输出格式是编程中常用的功能之一。在C++中，字符串输出格式可以使用不同的方式实现，具体取决于所需的输出格式。下面将详细介绍C++中常用的字符串输出格式：
  
  
• C++ 新建文件步骤详解
  C++
  
  
• C++数据可视化库：提升数据分析和表达效果
  C++数据可视化库是针对C++语言开发的一种图形化数据呈现工具，主要用于帮助开发者向用户直观、清晰地呈现数据分析结果和数据表达过程。随着大数据时代的到来，对于数据的定量分析和可视化展现要求越来越高，C++数据可视化库应运而生，并且在不断地发
  
  
• 电脑下载Visual C++的方法和步骤
  Visual
  
  
• C++字符串转整数教程
  在C++中，我们经常会遇到需要将字符串转换成整数的情况。例如，当我们从用户输入中获取数据时，通常会看到输入的是字符串类型，需要将输入的字符串转换成整数类型以便进行计算或比较操作。
  
  
• "C++中哪个类是用于输出文件流的类？"
  C++中文件流是一种非常常用的输入输出方式，可以读取和写入文件中的数据。其中输出文件流是一种非常重要的类，它能够将数据输出到文件中。
  
  
• C++中如何表达负数
  在计算机科学中，C++是一种流行的编程语言，用于开发各种应用程序和软件。在C++中，可通过不同的方式表示和处理负数。下面将介绍一些C++中表达负数的方法以及它们之间的区别。
  
  
• 如何在DevC++中新建C++项目
  DevC++是一个流行的C++开发工具，它提供了一个简单易用的界面，帮助程序员快速创建和开发C++项目。这篇文章将介绍如何在DevC++中新建C++项目。
  
  
• C++ 字符长度：计算字符串中字符的个数
  在
  
  
• C++ 如何从键盘输入数据
  C++
  
  
• C++ 数组倒置函数实现
  在C++中，数组是一种常见的数据结构用于存储相同类型的数据。当需要对数组中的元素进行倒置操作时，可以使用数组倒置函数来实现该功能。本文将介绍如何使用C++数组倒置函数实现这一操作。
  
  
• C++树的实现：孩子兄弟表达法
  在计算机科学领域，树是一种重要的数据结构，常用来表示具有层次关系的数据。在C++语言中，有多种不同的方法可以实现树的数据结构，其中一种常用的方法就是孩子兄弟表达法。
  
  
• 如何计算C++中的字节数？
  在C++编程中，有时需要计算变量类型的字节数，以进行内存分配或其他操作。下面介绍两种方法来计算C++中的字节数。
  
  
• C++基础试题练习
  C++是一种高级编程语言，广泛应用于各种计算因素领域。在学习C++编程语言的过程中，掌握其基础知识十分重要。因此，试题集是一个迅速提高技能水平的好方法。
  
  
• C++向量按降序排序
  C++中的向量是一个常用的数据结构，常用于存储一组数据，而排序也是在实际编程中非常常见的操作。本文介绍了如何使用C++向量按降序排序。
  
  
• 如何在C++中取得子窗口句柄
  要在C++中获取子窗口句柄，可以使用Windows
  
  
• C++中如何声明字符串？
  在C++中，字符串可以使用两种方式来声明：一种是使用字符数组，另一种是使用string类。
  
  
• C++实现判断两个数之间的素数
  C++是一种高级编程语言，常用于计算机科学。在计算机编程中，一个素数是一个只能被1和自身整除的正整数。C++编程语言可以实现判断两个数之间是否存在素数的算法。
  
  
• C++单链表基本操作实现
  在C++中，单链表是一种常见的数据结构。它是一种线性表，由节点组成，每个节点包含一个存储元素的数据部分和一个指向下一个节点的指针部分。单链表的基本操作包括创建、插入、删除、查找和遍历等。
  
  

友情链接
• 网站定制开发
• 帮你发
• 小蓄群站获客