开发者社区

文档建议反馈控制台

最新优惠活动

文章/答案/技术大牛

发布

递归vs迭代树遍历

递归和迭代是两种常见的算法思想，用于解决问题或处理数据结构。树遍历是指按照一定规则遍历树的所有节点。

递归是一种通过调用自身的方式来解决问题的方法。在树遍历中，递归可以用来遍历树的所有节点。递归的思想是将一个大问题划分为一个或多个相同或相似的子问题，并通过递归调用解决这些子问题，最终得到整个问题的解。递归的实现通常包括两个部分：基本情况和递归调用。基本情况是指递归的终止条件，当满足终止条件时，递归停止。递归调用是指在解决子问题时，再次调用自身来解决更小规模的子问题。

迭代是一种通过循环来解决问题的方法。在树遍历中，迭代可以用来遍历树的所有节点。迭代的思想是通过循环来重复执行一段代码，直到满足某个条件时停止循环。迭代的实现通常使用循环结构，通过不断更新循环变量来控制循环的执行次数。

树遍历是指按照一定规则遍历树的所有节点。常见的树遍历方式有前序遍历、中序遍历和后序遍历。前序遍历是指先访问根节点，然后按照左子树、右子树的顺序遍历子树的节点。中序遍历是指按照左子树、根节点、右子树的顺序遍历子树的节点。后序遍历是指按照左子树、右子树、根节点的顺序遍历子树的节点。

递归和迭代在树遍历中都可以使用。递归的实现相对简单，但可能会导致堆栈溢出的问题。迭代的实现相对复杂一些，但可以避免堆栈溢出的问题。在实际应用中，可以根据具体情况选择递归或迭代来实现树遍历。

以下是腾讯云相关产品和产品介绍链接地址，供参考：

云服务器（CVM）：提供弹性、可靠、安全的云服务器实例，支持多种操作系统和应用场景。详细信息请参考：https://cloud.tencent.com/product/cvm
云数据库 MySQL 版（CDB）：提供高性能、高可用的云数据库服务，适用于各种规模的应用。详细信息请参考：https://cloud.tencent.com/product/cdb_mysql
腾讯云函数（SCF）：无服务器计算服务，支持按需运行代码，无需管理服务器。详细信息请参考：https://cloud.tencent.com/product/scf
腾讯云对象存储（COS）：提供安全、稳定、低成本的云存储服务，适用于存储和处理各种类型的数据。详细信息请参考：https://cloud.tencent.com/product/cos
腾讯云人工智能（AI）：提供丰富的人工智能服务，包括图像识别、语音识别、自然语言处理等。详细信息请参考：https://cloud.tencent.com/product/ai

请注意，以上仅为腾讯云的部分产品和介绍链接，其他云计算品牌商的产品和服务也值得关注和了解。

页面内容是否对你有帮助？

有帮助

没帮助

相关·内容

二叉树的遍历(递归And迭代)

二叉树的遍历以 1 二叉树为例讲解： 2 3 4 5 6 7 递归法思路：按照递归调用的机制，我们按照只要遍历到就打印的方式得到的数据为：【1，2，4，4...，4，2，5，5，5，2，1，3，6，6，6，3，7，7，7，3，1】前序遍历我们将前序遍历所得到的数据都是在调用递归机制的元素首次出现的位置，那么按照前序遍历：【中 - 左 - 右】的顺序即可完成...= null){ this.right.prefix(); } } 中序遍历中序遍历所得到的数据都是在调用递归机制的元素第二次出现的位置，那么按照前序遍历：【左 - 中 -...= null){ this.right.infix(); } } 后序遍历后序遍历所得到的数据都是在调用递归机制的元素最后一次出现的位置，那么按照前序遍历：【左 - 右 -...= null){ this.right.suffix(); } System.out.println(this); } 迭代法思路：首先我们来了解一下递归的实现

801 0

非递归遍历树

先序非递归遍历二叉树，中序非递归遍历二叉树，后序非递归遍历二叉树及双栈法。...先序非递归遍历二叉树先序非递归遍历比较简单，感觉与DFS类似，根据先序遍历的规则根左右，先将根节点压入栈，然后遍历左子树，再遍历左子树的左子树，一头走到NULL，把每次遍历的左子树的根节点依次入栈并把当前结点数据打印出来...//测试样例 //输入前三行 //9 //1 2 4 7 3 5 8 9 6 //先序 //4 7 2 1 8 5 9 3 6 // 中序 //7 4 2 8 9 5 6 3 1 // 后序中序非递归遍历二叉树...i<n;++i) { scanf("%d",&b[i]); } Tree = Creat(a,b,n); travel_in(Tree); } return 0; } 后序非递归遍历二叉树及双栈法...单栈法后序非递归遍历和先序中序非递归开始类似，先将左子树的左孩子的的左孩子的….每个节点压入栈。

8681 0

树的非递归遍历

树使用递归遍历非常方便，如果将代码拉伸开来，我们能否是否非递归代码来实现呢？当然是可以的，我们只要把递归的循环步骤修改为while就可以了。...并放弃其左子树；如果结点没有左子树，访问该结点；步骤2：如果结点有右子树，重复步骤1；如果结点没有右子树（结点访问完毕），根据栈顶指示回退，访问栈顶元素，并访问右子树，重复步骤1 如果栈为空，表示遍历结束...TirTNode* findLeft(TirTNode* tree, std::stack& st) { if (nullptr == tree) return nullptr; // 持续遍历...= pLeft->rightChild) { // 如果有，则遍历这个树下最深的左子树 pLeft = findLeft(pLeft->rightChild, st); } else //如果节点没有右子树...st.empty()) { // 访问栈顶元素 pLeft = st.top(); // 弹出 st.pop(); } else { // 遍历完成 return; } } } } 调用时，只需给 myTreeOrder

1912 0

树的遍历--树的广度遍历（层次遍历），深度遍历（前序遍历，中序遍历，后序遍历的递归和非递归实现）

spring-jpa，webjars，Aspect，drools-drt，rabbitmq，zookeeper，mongodb，mysql存储过程，前端的延迟加载，netty，postgresql 这次就来整合下树的遍历...递归很好理解就是非递归...debug几次，细心点就好了 ps. 广度遍历叫层次遍历，一层一层的来就简单了。...bt.levelIterator(bt.root); System.out.println("***非递归实现****(前序遍历)遍历*****************");...bt.nonRecPreOrder(bt.root); System.out.println("***非递归实现****(中序遍历)遍历*****************");...bt.nonRecInOrder(bt.root); System.out.println("***非递归实现****(后序遍历)遍历*****************");

4.6K4 0

树的遍历非递归实现

#include <iostream> #include <stdio.h> #include <stdlib.h> #include <algorithm> ...

7852 0

非递归方式实现二叉树后序遍历_二叉树递归遍历

二叉树前序遍历对于一种数据结构而言，我们最常见的就是遍历，那么关于二叉树我们该如何去遍历呢？请看大屏幕。。。。...上图是一棵二叉树，前序遍历结果：1 2 4 5 3 6 咦，我想你可能会疑惑什么叫做前序遍历，其实很简单，就是按照根 -》左 -》右的方式去遍历二叉树。...首先让我们来看看如何递归的去前序遍历二叉树注：在这里我特别强调一点，在我们二叉树中，如果采用递归的方式，大部分都采用的根左右的方式，即采用子问题的方式，即先处理跟节点，再处理左子树，再处理右子树的这样一种思想...前序递归遍历 /** * Definition for a binary tree node...那么接下来我们再看看非递归的方式前序非递归遍历 /** * Definition for a binary tree node.

4111 0

【二叉树进阶】二叉树的前中后序遍历（非递归迭代实现）

二叉树的前序遍历题目链接: link 不用递归，用迭代算法如何实现对二叉树的前序遍历？最终放到一个vector里面返回。...1.1 思路分析前序遍历的非递归呢我们可以这样来搞：题目中给的二叉树比较简单，下面通过这样一棵二叉树给大家讲解：对它进行非递归的前序遍历，它是这样搞的：前序遍历是根、左子树、右子树...所以非递归的前序遍历是这样处理的：他把一棵二叉树分为两个部分：左路结点左路结点的右子树对于每一棵左子树，也是同样划分为这两个部分进行处理。...二叉树的中序遍历题目链接: link 接下来我们就来看一下二叉树中序遍历的非递归如何实现 2.1 思路分析其实大体的思路还是跟上一道题的差不多，最后写出来跟上一题的代码也基本一样，其中一句代码换一下位置就行了...二叉树的后序遍历题目链接: link 那后序遍历的非递归又如何实现呢？这里提供两种思路 3.1 思路1 思路1呢是这样的：大家想前序是根、左子树、右子树。

2041 0

二叉树的非递归遍历（递归和非递归）

二叉树是一种非常重要的数据结构，很多其它数据结构都是基于二叉树的基础演变而来的。对于二叉树，有前序、中序以及后序三种遍历方法。...因为树的定义本身就是递归定义，因此采用递归的方法去实现树的三种遍历不仅容易理解而且代码很简洁。而对于树的遍历若采用非递归的方法，就要采用栈去模拟实现。...在三种遍历中，前序和中序遍历的非递归算法都很容易实现，非递归后序遍历实现起来相对来说要难一点。一.前序遍历前序遍历按照“根结点-左孩子-右孩子”的顺序进行访问。 ...//非递归前序遍历 void pre_order(BTree *root) { stack s; BTree *p = root; while... 后序遍历的非递归实现是三种遍历方式中最难的一种。

1.5K10 0

二叉树遍历算法递归实现+层次遍历

; struct BTNode *rchild; }BTNode; 二叉树的遍历算法 1 先序遍历先序遍历的操作如下。...如果二叉树为空树，则什么都不做；否则： 1）访问根节点 2）先序遍历左子树 3）先序遍历右子树描述如下： void preorder(BTNode *p) { if(p !...如果二叉树为空树，则什么都不做；否则： 1）中序遍历左子树 2）访问根节点 3）中序遍历右子树描述如下： void inorder(BTNode *p) { if(p !...如果二叉树为空树，则什么都不做；否则： 1）后序遍历左子树 2）后序遍历右子树 3）访问根节点描述如下： void postorder(BTNode *p) { if(p !..." /> 上图所示为二叉树的层次遍历，即按照箭头所指方向，按照1、2、3、4的层次顺序，对二叉树中各个结点进行访问（此图反映的是自左至右的层次遍历，自右至左的方式类似）要进行层次遍历，需要建立一个循环队列先将二叉树头结点入队列

1.4K0 0

递归遍历-LeetCode 124、112、113（递归遍历二叉树，回溯法）

【LeetCode #124 二叉树的最大路径和】给定一个非空二叉树，返回其最大路径和。本题中，路径被定义为一条从树中任意节点出发，达到任意节点的序列。...因此使用递归算法从根节点开始遍历，如果左右子树最大路径和大于0，则取出该路径的最大值，否则为零，也就是说如果大于零，则加上之后result是可以增加的！...因此对result进行更新，同时递归函数也返回root->val + max(0, max(left, right))。...解题思路：和上一题的思路一模一样，但这一题需要我们将中间遍历的节点值保存起来，因此需要一个tmp数组来保存我们遍历过的节点！...这里面需要注意的一点就是回溯法的使用，当修改了一个状态之后，递归结束后，需要把这个状态重新置为之前的状态。比如tmp中push_back了一个值，当递归结束进行回溯阶段，需要pop_back()。

9017 0

二叉树的递归遍历

> //二叉树的递归遍历 struct BinaryNode { //数据域 char ch; //指针域 BinaryNode* lchild; //指向左孩子的指针 BinaryNode...* rchild; //指向右孩子的指针 }; //递归遍历:传入根结点指针 void recursion(BinaryNode* root) { //先序遍历 if (root == NULL)... //二叉树的递归遍历 struct BinaryNode { //数据域 char ch; //指针域 BinaryNode* lchild; //指向左孩子的指针 BinaryNode...* rchild; //指向右孩子的指针 }; //递归遍历:传入根结点指针 void recursion(BinaryNode* root) { //中序遍历 if (root == NULL)... //二叉树的递归遍历 struct BinaryNode { //数据域 char ch; //指针域 BinaryNode* lchild; //指向左孩子的指针 BinaryNode

5162 0

二叉树的递归遍历

特点1 虽然是从root开始，但是严重依赖从下到上的反馈的数据，例如求tree的高度题目1 最近公共祖先（LCA）给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。...Balanced Binary Tree 依赖下面反馈合并在一起特点2 从上到下，依赖当前root节点判断 1 翻转等价二叉树我们可以为二叉树 T 定义一个翻转操作，如下所示：选择任意节点，然后交换它的左子树和右子树...只要经过一定次数的翻转操作后，能使 X 等于 Y，我们就称二叉树 X 翻转等价于二叉树 Y。编写一个判断两个二叉树是否是翻转等价的函数。...这些树由根节点 root1 和 root2 给出选择任意节点，然后交换它的左子树和右子树左子树和右子树是否继续交换呢？是否选择了任意节点？...翻转一棵二叉树 root保持不变左右子树交换重复步骤1和2 测试翻转一棵二叉树 code class Solution { public: TreeNode* invertTree(TreeNode

5392 0

二叉树的遍历——递归和非递归

二叉树是一种非常重要的数据结构，很多其它数据结构都是基于二叉树的基础演变而来的。对于二叉树，有前序、中序以及后序三种遍历方法。...因为树的定义本身就是递归定义，因此采用递归的方法去实现树的三种遍历不仅容易理解而且代码很简洁。而对于树的遍历若采用非递归的方法，就要采用栈去模拟实现。...在三种遍历中，前序和中序遍历的非递归算法都很容易实现，非递归后序遍历实现起来相对来说要难一点。一.前序遍历前序遍历按照“根结点-左孩子-右孩子”的顺序进行访问。 ... 后序遍历的非递归实现是三种遍历方式中最难的一种。...若存在，则由x带回完整值并返回真，否则返回假该算法类似于前序遍历，若树为空则返回false结束递归，若树根结点的值就等于x的值，则把结点值赋给x后返回true结束递归，否则先向左子树查找，若找到则返回

1.2K8 0

使用MySQL 8的递归CTE遍历树

从根遍历到叶 2. 从叶遍历到根 3. ...从根遍历到叶 mysql> with recursive x (sid,id,pid) -> as ( -> select cast(id as char(100)),...从叶遍历到根 mysql> with recursive x (sid,id,pid) -> as ( -> select cast(id as char(100

7903 0

递归迭代

递归： A调用B，B调用C，…… 都在等待上一步结果返回迭代： A问B，B不知道，A再问C，……每次结果都依赖于上一次迭代器协议：对象必须提供一个next方法，执行该方法要么返回迭代中的下一项，要么就引起一个...StopIteration异常，以终止迭代（只能往后走不能往前退）可迭代对象：在内部定义有__iter__() #可使用__next__() 也可直接用iter() l = [1,2,3] l.

1603 0

聊聊二叉树的遍历（递归和非递归）

，对其进行中序遍历后，会得到一个有序的列表，这是我们经常用到的一种数的结构平衡二叉树：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树，并且满足二叉搜索树的规则...满二叉搜索树二叉树的遍历 ? 二叉树的遍历有三种方式：先序遍历，中序遍历，后序遍历。思路很简单，这里面说的顺序的序是指每个子树根节点的遍历（打印）顺序。...递归版本（先、中、后序）递归版的遍历算法很简单了，我们只需要改变打印次序就好了，也没有什么可讲的！...（先、中、后序）首先我们要清楚，任何算法的递归版本都可以改成非递归版本，因为函数递归调用其实质就是压栈的过程，那么我们完全可以使用堆栈来模拟这个过程！...// 迭代版 void printPreorder2(TreeNode* head){ cout << "Pre Order:" << endl; if (head !

9433 0

二叉树的非递归遍历

递归实现先序 public void preOrder(){ preOrder(root); } private void preOrder(Node node){ if(node !...非递归前序 public void preOrderNew(){ preOrderNew(root); } private void preOrderNew(Node node){ if

6412 0

二叉树的非递归遍历

一.二叉树的非递归前序遍历 public static void preOrderUnRecur(TreeNode root){ if (root == null) return; Stack...= null){ stack.add(temp.left); } } } 二.二叉树的非递归中序遍历 image.png public static...System.out.print(temp.val+" "); root = temp.right; } } } 三.二叉树的非递归后序遍历...采用2个栈，这个与前序遍历类似，只不过是在该打印的时候，用一个栈将其存放起来，最后打印。

1.3K5 0

二叉树的遍历 → 不用递归，还能遍历吗

深度遍历　　当我们对各种遍历有了概念上的了解之后，我们来看下具体实现　　先序遍历　　递归实现很简单，相信大家已经烂熟于心了　　如果不用递归，我们怎么实现先序遍历？　　...，实现如下　　中续遍历　　递归实现　　非递归实现　　这个可能没那么好理解，结合具体的二叉树示例，脑中逐行模拟下代码执行，慢慢的就有感觉了　　后续遍历　　递归实现　　非递归实现　　...用到了双栈，大家仔细揣摩下代码　　深度优先遍历　　指的就是先序遍历，前面已经实现过，这里就不再赘述广度遍历　　一层一层的遍历二叉树，如果未明确指明，都是从左至右遍历　　广度遍历不满足递归的条件...广度优先遍历　　　　指的就是从上至下层次遍历，不再赘述总结　　1、递归的实现往往比迭代实现要简单，也更好理解，但两者存在控件使用率的差异　　　　递归没有我们想象的那么简单，不同的问题有不同的决策过程...　　　　而如何正确的找到决策过程，没有答案，全凭个人的感觉，可以通过多练题来提高这种感觉　　2、二叉树遍历是解决二叉树相关问题的基础，不同的遍历可以解决不同的问题　　　　下一篇讲二叉树相关的具体案例

6074 0

二叉树的非递归遍历

二叉树的非递归遍历二叉树是一种非常重要的数据结构，很多其它数据结构都是基于二叉树的基础演变而来的...对于二叉树，有前序、中序以及后序三种遍历方法。因为树的定义本身就是递归定义，因此采用递归的方法去实现树的三种遍历不仅容易理解而且代码很简洁。而对于树的遍历若采用非递归的方法，就要采用栈去模拟实现。...在三种遍历中，前序和中序遍历的非递归算法都很容易实现，非递归后序遍历实现起来相对来说要难一点。一.前序遍历前序遍历按照“根结点-左孩子-右孩子”的顺序进行访问。 ...1.递归实现 void preOrder1(BinTree *root) //递归前序遍历 { if(root!... 后序遍历的非递归实现是三种遍历方式中最难的一种。

7261 0

点击加载更多

扫码

添加站长进交流群

领取专属 10元无门槛券

手把手带您无忧上云

扫码加入开发者社群

相关资讯

热门标签

活动推荐

运营活动

活动名称

广告关闭