递归非递归两种算法遍历二叉树讲解
- 格式:doc
- 大小:124.56 KB
- 文档页数:16
中序遍历二叉树t的非递归算法-回复中序遍历是二叉树遍历的一种方法,它的特点是先访问左子树,然后访问根节点,最后访问右子树。
在非递归算法中,我们需要借助栈来实现中序遍历。
下面我们将逐步分析如何用非递归算法中序遍历二叉树。
首先,我们需要了解栈的基本知识。
栈是一种后进先出(LIFO)的数据结构,它有两个基本操作:入栈(push)和出栈(pop)。
在中序遍历中,我们将节点按照遍历顺序依次入栈,然后出栈并访问节点。
接下来,我们来介绍中序遍历二叉树的非递归算法。
我们可以通过模拟递归来实现中序遍历。
首先,我们定义一个栈用于存储待访问的节点。
初始时,将根节点入栈。
在每一次迭代中,我们需要判断栈是否为空。
若不为空,则将栈顶节点出栈,并访问该节点。
然后,我们将栈顶节点的右子树入栈。
接下来,将栈顶节点的左子树依次入栈,直到左子树为空。
下面,我们以一个简单的例子来说明这个过程。
假设我们有如下二叉树t:1/ \2 3/ \ / \4 5 6 7我们使用中序遍历的非递归算法来遍历这棵树。
首先,将根节点入栈,此时栈中的元素为[1]。
然后,循环执行以下步骤:1. 判断栈是否为空,栈不为空,执行以下步骤;2. 将栈顶节点出栈,访问该节点;3. 将栈顶节点的右子树入栈;4. 将栈顶节点的左子树依次入栈,直到左子树为空。
按照这个步骤,我们首先将1出栈并访问,然后将右子树入栈,栈中的元素为[2, 3]。
然后,我们继续将左子树入栈,栈中的元素变为[4, 2, 3]。
此时,我们将4出栈并访问,然后将栈中的元素变为[2, 3]。
接着,我们将2出栈并访问,将右子树入栈,栈中的元素变为[5, 3]。
继续将左子树入栈,栈中的元素为[5, 6, 3]。
接着,我们将5出栈并访问,将栈中的元素变为[6, 3]。
最后,我们将6出栈并访问,将右子树入栈,栈中的元素变为[7, 3]。
最后,我们将7出栈并访问,此时栈为空,遍历结束。
通过这个例子,我们可以看到中序遍历的非递归算法确实按照中序遍历的顺序访问了二叉树的所有节点。
golang 中序遍历递归非递归中序遍历是二叉树遍历的一种方式,以左子树、根节点、右子树的顺序访问节点。
在Golang中,我们可以使用递归和非递归两种方式实现中序遍历。
一、递归实现中序遍历递归实现中序遍历是最简单直观的方式。
我们可以定义一个递归函数,用于按中序遍历访问树的节点。
```gopackage mainimport "fmt"type TreeNode struct {Val intLeft *TreeNodeRight *TreeNode}func inorderTraversal(root *TreeNode) {if root != nil {inorderTraversal(root.Left)fmt.Printf("%d ", root.Val)inorderTraversal(root.Right)}}func main() {// 构造一棵二叉树root := &TreeNode{Val: 1}root.Left = &TreeNode{Val: 2}root.Right = &TreeNode{Val: 3}root.Left.Left = &TreeNode{Val: 4}root.Left.Right = &TreeNode{Val: 5}fmt.Println("中序遍历结果:")inorderTraversal(root)}```以上代码中,我们先构造了一棵二叉树,然后调用`inorderTraversal`函数进行中序遍历。
递归函数首先检查根节点是否为空,如果不为空,则按照左子树、根节点、右子树的顺序递归调用自身。
二、非递归实现中序遍历非递归实现中序遍历使用栈来模拟递归的过程。
具体实现过程如下:```gopackage mainimport "fmt"type TreeNode struct {Val intLeft *TreeNodeRight *TreeNode}func inorderTraversal(root *TreeNode) { stack := []*TreeNode{}cur := rootfor len(stack) > 0 || cur != nil {for cur != nil {stack = append(stack, cur)cur = cur.Left}cur = stack[len(stack)-1]stack = stack[:len(stack)-1]fmt.Printf("%d ", cur.Val)cur = cur.Right}}func main() {// 构造一棵二叉树root := &TreeNode{Val: 1}root.Left = &TreeNode{Val: 2}root.Right = &TreeNode{Val: 3}root.Left.Left = &TreeNode{Val: 4}root.Left.Right = &TreeNode{Val: 5}fmt.Println("中序遍历结果:")inorderTraversal(root)}```以上代码中,我们定义了一个栈和一个指针`cur`,其中栈用于存储遍历过程中的节点。
二叉树后序遍历的非递归算法
二叉树后序遍历是指按照左子树、右子树、根节点的顺序遍历二叉树的过程。
与前序遍历和中序遍历不同,后序遍历需要考虑根节点的位置,因此需要使用栈来存储节点信息。
非递归算法一般使用栈来实现,因为后序遍历的过程中需要先遍历左子树和右子树,最后才遍历根节点,所以存储节点信息的栈需要进行一些特殊处理。
下面是二叉树后序遍历的非递归算法:
1. 创建一个空栈,并将根节点入栈。
2. 创建一个辅助变量pre表示上一个被遍历的节点。
3. 当栈不为空时,取出栈顶元素top,判断它是否为叶子节点或者它的左右子节点都被遍历过了(被遍历过的节点可以通过辅助变量pre来判断)。
4. 如果top为叶子节点或者它的左右子节点都被遍历过了,则将top出栈,并将它的值输出。
5. 如果不满足条件3,判断top的右子节点是否为pre,如果是,则说明右子树已经遍历完了,此时可以直接输出top的值,并将top出栈;如果不是,则将top的右子节点入栈。
6. 将top的左子节点入栈。
7. 将上一个被遍历的节点pre更新为top。
根据这个算法,我们可以分别对左子树和右子树进行遍历,并保证根节点最后被遍历到,从而实现二叉树的后序遍历。
这个算法的时间复杂度为O(n),空间复杂度为O(n)。
总的来说,二叉树的后序遍历是一种比较复杂的遍历方式,需要使用栈保存节点信息,并且需要特殊处理根节点的位置。
使用非递归算法实现后序遍历可以优化空间复杂度和避免栈溢出的问题。
中序遍历非递归算法一、前言在二叉树的遍历中,中序遍历是一种重要的遍历方式。
中序遍历非递归算法是指不使用递归函数,通过循环和栈等数据结构实现对二叉树进行中序遍历。
本文将详细介绍中序遍历非递归算法的实现过程和相关知识点。
二、中序遍历的定义在二叉树中,对每个节点的访问顺序有三种方式:先访问左子树,再访问根节点,最后访问右子树;先访问根节点,再访问左子树和右子树;先访问左子树和右子树,最后访问根节点。
这三种方式分别称为前序遍历、中序遍历和后序遍历。
其中,中序遍历是指按照“先访问左子树,再访问根节点,最后访问右子树”的顺序进行访问。
三、中序遍历非递归算法的思路1. 定义一个空的辅助栈;2. 从二叉树的跟节点开始循环:a. 将当前节点压入辅助栈;b. 如果当前节点存在左孩子,则将当前节点设置为其左孩子,继续循环;c. 如果当前节点不存在左孩子,则从辅助栈中弹出一个节点,并将该节点的值输出;d. 如果被弹出的节点存在右孩子,则将当前节点设置为其右孩子,继续循环;e. 如果被弹出的节点不存在右孩子,则回到步骤c。
四、中序遍历非递归算法的实现1. 定义一个空的辅助栈和一个指向二叉树跟节点的指针cur;2. 对于每个节点,如果该节点不为空或者辅助栈不为空,则进行循环:a. 如果当前节点不为空,则将其压入辅助栈中,并将当前节点更新为其左孩子;b. 如果当前节点为空,则从辅助栈中弹出一个元素,并输出该元素的值;i. 将当前节点更新为被弹出元素的右孩子。
3. 循环结束后,即可完成对二叉树的中序遍历。
五、代码实现以下是Java语言实现中序遍历非递归算法的代码:```public static void inOrder(TreeNode root) {Stack<TreeNode> stack = new Stack<>();TreeNode cur = root;while (cur != null || !stack.isEmpty()) {if (cur != null) {stack.push(cur);cur = cur.left;} else {cur = stack.pop();System.out.print(cur.val + " ");cur = cur.right;}}}```六、时间和空间复杂度中序遍历非递归算法的时间复杂度为O(n),其中n为二叉树节点的个数。
二叉树的各种算法1.二叉树的前序遍历算法:前序遍历是指先访问根节点,再访问左子树,最后访问右子树的遍历顺序。
具体算法如下:-如果二叉树为空,则直接返回。
-访问根节点,并输出或进行其他操作。
-递归地前序遍历左子树。
-递归地前序遍历右子树。
2.二叉树的中序遍历算法:中序遍历是指先访问左子树,再访问根节点,最后访问右子树的遍历顺序。
具体算法如下:-如果二叉树为空,则直接返回。
-递归地中序遍历左子树。
-访问根节点,并输出或进行其他操作。
-递归地中序遍历右子树。
3.二叉树的后序遍历算法:后序遍历是指先访问左子树,再访问右子树,最后访问根节点的遍历顺序。
具体算法如下:-如果二叉树为空,则直接返回。
-递归地后序遍历左子树。
-递归地后序遍历右子树。
-访问根节点,并输出或进行其他操作。
4.二叉树的层序遍历算法:层序遍历是按照从上到下、从左到右的顺序逐层遍历二叉树的节点。
具体算法如下:-如果二叉树为空,则直接返回。
-创建一个队列,将根节点入队。
-循环执行以下步骤,直到队列为空:-出队并访问当前节点,并输出或进行其他操作。
-若当前节点的左子节点不为空,则将左子节点入队。
-若当前节点的右子节点不为空,则将右子节点入队。
5.二叉树的深度算法:二叉树的深度是指从根节点到叶节点的最长路径的节点数。
具体算法如下:-如果二叉树为空,则深度为0。
-否则,递归地计算左子树的深度和右子树的深度,然后取较大的值加上根节点的深度作为二叉树的深度。
6.二叉树的查找算法:二叉树的查找可以使用前序、中序或后序遍历来完成。
具体算法如下:-如果二叉树为空,则返回空。
-如果当前节点的值等于目标值,则返回当前节点。
-否则,先在左子树中递归查找,如果找到则返回找到的节点。
-如果左子树中未找到,则在右子树中递归查找,如果找到则返回找到的节点。
-如果左右子树中都未找到,则返回空。
7.二叉树的插入算法:二叉树的插入可以使用递归或循环来实现。
具体算法如下:-如果二叉树为空,则创建一个新节点作为根节点,并返回根节点。
二叉树的遍历实验报告一、实验目的1.了解二叉树的基本概念和性质;2.理解二叉树的遍历方式以及它们的实现方法;3.学会通过递归和非递归算法实现二叉树的遍历。
二、实验内容1.二叉树的定义在计算机科学中,二叉树是一种重要的数据结构,由节点及它们的左右儿子组成。
没有任何子节点的节点称为叶子节点,有一个子节点的节点称为一度点,有两个子节点的节点称为二度点。
二叉树的性质:1.每个节点最多有两个子节点;2.左右子节点的顺序不能颠倒,左边是父节点的左子节点,右边是父节点的右子节点;3.二叉树可以为空,也可以只有一个根节点;4.二叉树的高度是从根节点到最深叶子节点的层数;5.二叉树的深度是从最深叶子节点到根节点的层数;6.一个深度为d的二叉树最多有2^(d+1) -1个节点,其中d>=1;7.在二叉树的第i层上最多有2^(i-1)个节点,其中i>=1。
2.二叉树的遍历方式二叉树的遍历是指从根节点出发,按照一定的顺序遍历二叉树中的每个节点。
常用的二叉树遍历方式有三种:前序遍历、中序遍历和后序遍历。
前序遍历:先遍历根节点,再遍历左子树,最后遍历右子树;中序遍历:先遍历左子树,再遍历根节点,最后遍历右子树;后序遍历:先遍历左子树,再遍历右子树,最后遍历根节点。
递归算法:利用函数调用,递归实现二叉树的遍历;非递归算法:利用栈或队列,对二叉树进行遍历。
三、实验步骤1.创建二叉树数据结构并插入节点;2.实现二叉树的前序遍历、中序遍历、后序遍历递归算法;3.实现二叉树的前序遍历、中序遍历、后序遍历非递归算法;4.测试算法功能。
四、实验结果1.创建二叉树数据结构并插入节点为了测试三种遍历方式的算法实现,我们需要创建一个二叉树并插入节点,代码如下:```c++//定义二叉树节点struct TreeNode {int val;TreeNode* left;TreeNode* right;TreeNode(int x) : val(x), left(NULL), right(NULL) {}};递归算法是实现二叉树遍历的最简单方法,代码如下:```c++//前序遍历非递归算法vector<int> preorderTraversal(TreeNode* root) {stack<TreeNode*> s;vector<int> res;if (!root) return res;s.push(root);while (!s.empty()) {TreeNode* tmp = s.top();s.pop();res.push_back(tmp->val);if (tmp->right) s.push(tmp->right);if (tmp->left) s.push(tmp->left);}return res;}4.测试算法功能return 0;}```测试结果如下:preorderTraversal: 4 2 1 3 6 5 7inorderTraversal: 1 2 3 4 5 6 7postorderTraversal: 1 3 2 5 7 6 4preorderTraversalNonRecursive: 4 2 1 3 6 5 7inorderTraversalNonRecursive: 1 2 3 4 5 6 7postorderTraversalNonRecursive: 1 3 2 5 7 6 4本次实验通过实现二叉树的递归和非递归遍历算法,加深了对二叉树的理解,并熟悉了遍历算法的实现方法。
二叉树经典例题的题解本文将为大家详细介绍几个经典的二叉树例题,并提供对应的解题思路和代码实现。
1. 二叉树的遍历二叉树的遍历是二叉树操作中最基础的操作。
它分为三种遍历方式:前序遍历、中序遍历和后序遍历。
其中,前序遍历是按照“根左右”顺序遍历,中序遍历是按照“左根右”顺序遍历,后序遍历是按照“左右根”顺序遍历。
遍历的实现方式主要有两种:递归和非递归。
递归实现比较简单,非递归实现可以利用栈来实现。
以下是前序遍历的递归实现:void preorderTraversal(TreeNode* root) {if (root != nullptr) {cout << root->val << ' ';preorderTraversal(root->left);preorderTraversal(root->right);}}以下是前序遍历的非递归实现:void preorderTraversal(TreeNode* root) {if (root == nullptr) return;stack<TreeNode*> st;st.push(root);while (!st.empty()) {TreeNode* node = st.top();st.pop();cout << node->val << ' ';if (node->right != nullptr) st.push(node->right);if (node->left != nullptr) st.push(node->left);}}2. 二叉树的最大深度二叉树的最大深度是指从根节点到叶子节点的最长路径上的节点数。
求二叉树的最大深度可以使用递归或BFS(广度优先搜索)实现。
以下是递归实现:int maxDepth(TreeNode* root) {if (root == nullptr) return 0;int leftDepth = maxDepth(root->left);int rightDepth = maxDepth(root->right);return 1 + max(leftDepth, rightDepth);}以下是BFS实现:int maxDepth(TreeNode* root) {if (root == nullptr) return 0;int depth = 0;queue<TreeNode*> q;q.push(root);while (!q.empty()) {int size = q.size();depth++;for (int i = 0; i < size; i++) {TreeNode* node = q.front();q.pop();if (node->left != nullptr) q.push(node->left);if (node->right != nullptr) q.push(node->right);}}return depth;}3. 判断两个二叉树是否相同判断两个二叉树是否相同可以通过递归实现。
二叉树的创建与遍历的实验总结引言二叉树是一种重要的数据结构,在计算机科学中有着广泛的应用。
了解二叉树的创建和遍历方法对于数据结构的学习和算法的理解至关重要。
本文将对二叉树的创建和遍历进行实验,并总结相应的经验和思考。
二叉树的定义在开始实验之前,我们首先需要了解二叉树的定义和基本概念。
二叉树是一种每个节点最多拥有两个子节点的树形结构。
每个节点包含一个值和指向其左右子节点的指针。
根据节点的位置,可以将二叉树分为左子树和右子树。
创建二叉树二叉树的创建可以采用多种方法,包括手动创建和通过编程实现。
在实验中,我们主要关注通过编程方式实现二叉树的创建。
1. 递归方法递归是一种常用的创建二叉树的方法。
通过递归,我们可以从根节点开始,逐层创建左子树和右子树。
具体步骤如下:1.创建一个空节点作为根节点。
2.递归地创建左子树。
3.递归地创建右子树。
递归方法的代码实现如下所示:class TreeNode:def __init__(self, value):self.value = valueself.left = Noneself.right = Nonedef create_binary_tree(values):if not values:return None# 使用队列辅助创建二叉树queue = []root = TreeNode(values[0])queue.append(root)for i in range(1, len(values)):node = TreeNode(values[i])# 当前节点的左子节点为空,则将新节点作为左子节点if not queue[0].left:queue[0].left = node# 当前节点的右子节点为空,则将新节点作为右子节点elif not queue[0].right:queue[0].right = node# 当前节点的左右子节点已经齐全,可以从队列中删除该节点queue.pop(0)# 将新节点添加到队列中,下一次循环时可以使用该节点queue.append(node)return root2. 非递归方法除了递归方法,我们还可以使用非递归方法创建二叉树。
二叉树的前序、后序的递归、非递归遍历算法学生姓名:贺天立指导老师:湛新霞摘要本课程设计主要解决树的前序、后序的递归、非递归遍历算法,层次序的非递归遍历算法的实现。
在课程设计中,系统开发平台为Windows 2000,程序设计设计语言采用Visual C++,程序运行平台为Windows 98/2000/XP。
用除递归算法前序,后续,中序遍历树外还通过非递归的算法遍历树。
程序通过调试运行,初步实现了设计目标,并且经过适当完善后,将可以应用在商业中解决实际问题。
关键词程序设计;C++;树的遍历;非递归遍历1 引言本课程设计主要解决树的前序、后序的递归、非递归遍历算法,层次序的非递归遍历算法的实现。
1.1课程设计的任务构造一棵树并输入数据,编写三个函数,非别是树的前序递归遍历算法、树的后序递归遍历算法、树的非递归中序遍历算法(这里的非递归以中序为例)。
在主程序中调用这三个函数进行树的遍历,观察用不同的遍历方法输出的数据的顺序和验证递归与非递归输出的数据是否一样。
1.2课程设计的性质由要求分析知,本设计主要要求解决树的前序、后序的递归、非递归遍历算法,层次序的非递归遍历算法的实现。
所以设计一个良好的前序、后序的递归、非递归遍历算法非常重要。
1.3课程设计的目的在程序设计中,可以用两种方法解决问题:一是传统的结构化程序设计方法,二是更先进的面向对象程序设计方法[1]。
利用《数据结构》课程的相关知识完成一个具有一定难度的综合设计题目,利用C语言进行程序设计。
巩固和加深对线性表、栈、队列、字符串、树、图、查找、排序等理论知识的理解;掌握现实复杂问题的分析建模和解决方法(包括问题描述、系统分析、设计建模、代码实现、结果分析等);提高利用计算机分析解决综合性实际问题的基本能力。
树的遍历分为前序、中序和后序,可以用递归算法实现树的三种遍历。
除了递归外还可以构造栈,利用出栈和入栈来实现树的前序遍历、中序遍历和后序遍历。
二叉树遍历解题技巧
二叉树遍历是指按照一定规则,依次访问二叉树的所有节点的过程。
常见的二叉树遍历有前序遍历、中序遍历和后序遍历。
以下是一些二叉树遍历解题技巧:
1. 递归遍历:递归是最直观、最简单的遍历方法。
对于一个二叉树,可以递归地遍历其左子树和右子树。
在递归的过程中,可以对节点进行相应的处理。
例如,前序遍历可以先访问根节点,然后递归遍历左子树和右子树。
2. 迭代遍历:迭代遍历可以使用栈或队列来实现。
对于前序遍历,可以使用栈来记录遍历路径。
首先将根节点入栈,然后依次弹出栈顶节点,访问该节点,并将其右子节点和左子节点分别入栈。
中序遍历和后序遍历也可以使用类似的方法,只是访问节点的顺序会有所不同。
3. Morris遍历:Morris遍历是一种空间复杂度为O(1)的二叉树遍历方法。
它利用二叉树节点的空闲指针来存储遍历下一个节点的信息,从而避免使用额外的栈或队列。
具体步骤可以参考相关算法书籍或博客。
4. 层次遍历:层次遍历是一种逐层遍历二叉树的方法。
可以使用队列来实现。
首先将根节点入队,然后依次将队首节点出队并访问,同时将其左子节点和右子节点入队。
不断重复这个过程,直到队列为空。
层次遍历可以按照从上到下、从左到右的顺序访问二叉树的节点。
除了以上技巧,还可以根据具体问题的特点来选择合适的遍历方法。
在实际解题中,可以尝试不同的遍历方法并选择效率高、代码简洁的方法。
先序遍历二叉树的算法非递归算法一、引言二叉树是一种常见的数据结构,其遍历方式包括先序遍历、中序遍历和后序遍历。
先序遍历是一种常用的遍历方式,它按照根节点-左子树-右子树的顺序访问每个节点。
在递归实现先序遍历二叉树的基础上,非递归算法的出现使得算法的实现更为简洁和高效。
二、非递归算法原理非递归算法的实现原理基于栈数据结构。
我们首先将根节点入栈,然后不断弹出栈顶元素并访问,同时将右子树和左子树分别入栈。
当栈为空时,表示遍历完成。
这种方法避免了递归调用可能导致的堆栈溢出问题,同时提高了算法的效率。
三、非递归算法实现以下是用Python实现的非递归先序遍历二叉树的算法:```pythondefpreorder_traversal_non_recursive(node):ifnodeisNone:return#将当前节点入栈stack.append(node)#当栈不为空时,不断弹出栈顶元素并访问whilestack:curr=stack.pop()#弹出栈顶元素print(curr.value)#访问当前节点#将右子节点入栈ifcurr.right:stack.append(curr.right)#将左子节点入栈ifcurr.left:stack.append(curr.left)```四、算法应用与讨论非递归算法的应用范围广泛,不仅可以应用于二叉树的遍历,还可以应用于二叉树的创建、插入、删除等操作。
在实际应用中,我们可以通过Python中的列表或者类来实现栈数据结构,进而实现非递归算法。
此外,非递归算法还可以与其他算法结合,如深度优先搜索(DFS)和广度优先搜索(BFS),以实现更复杂的数据处理任务。
五、总结非递归先序遍历二叉树的算法是一种实用的技术,它能够简化代码、提高效率并避免堆栈溢出问题。
通过使用栈数据结构,我们可以轻松地实现非递归算法,并将其应用于各种二叉树操作中。
这种技术对于理解和应用二叉树数据结构具有重要的意义。
C++⼆叉树的先序,中序,后序遍历三种遍历⽅式都分为递归与⾮递归的⽅式。
三种遍历⽅式的递归思想相同。
后序遍历⾮递归⽅法分为两种,具体见代码。
构造⽅式:1 #include<iostream>2 #include<stack>3using namespace std;45 typedef struct BiTNode{6char data;7int lvisited,rvisited;//左、右孩⼦是否访问过,1表⽰已访问(此项只在后序⾮递归2算法中需要)8struct BiTNode *lchild,*rchild;9 }BiTNode,*BiTree;1011void InitBiTree(BiTree &T)//构造空⼆叉树12 {13 T=NULL;14 }15void CreateBiTree(BiTree &T)//⽣成⼆叉树16 {17char ch;18 cin>>ch;19if(ch=='0')//0代表空20 T=NULL;21else22 {23 T=(BiTree)malloc(sizeof(BiTNode));//⽣成根结点24if(!T)25 {26 cout<<"⽣成结点错误!"<<endl;27return;28 }29 T->data=ch;30 T->lvisited=0;31 T->rvisited=0;32 CreateBiTree(T->lchild);33 CreateBiTree(T->rchild);34 }35 }三种遍历⽅式代码:1void PreOrder(BiTree T)//先序递归遍历2 {3if(T!=NULL)4 {5 cout<<T->data<<"";6 PreOrder(T->lchild);7 PreOrder(T->rchild);8 }9 }10void SqlPreOrder(BiTree T)//先序⾮递归遍历11 {12 stack<BiTree> s;13 BiTree p=T;14while(p || !s.empty())15 {16if(p)17 {18 cout<<p->data<<"";19 s.push(p);20 p=p->lchild;21 }22else23 {24 p=s.top();25 p=p->rchild;26 s.pop();27 }28 }29 }30313233void InOrder(BiTree T)//中序递归遍历34 {35if(T!=NULL)36 {37 InOrder(T->lchild);38 cout<<T->data<<"";39 InOrder(T->rchild);40 }41 }42void SqInOrder(BiTree T)//中序⾮递归遍历43 {44 stack<BiTree> s;45 BiTree p=T;46while(p || !s.empty())47if(p)48 {49 s.push(p);50 p=p->lchild;51 }52else53 {54 p=s.top();55 cout<<p->data<<"";56 s.pop();57 p=p->rchild;58 }59 }60616263void PostOrder(BiTree T)//后序递归遍历64 {65if(T!=NULL)66 {67 PostOrder(T->lchild);68 PostOrder(T->rchild);69 cout<<T->data<<"";70 }71 }7273//后序⾮递归遍历1思路:因为后序⾮递归遍历⼆叉树的顺序是先访问左⼦树,再访问后⼦树,最后 74//访问根结点。
用递归、非递归两种方法遍历二叉树一、设计思想1. 用递归算法遍历设计思想:主要是通过不同程序顺序,从而实现递归的顺序遍历前序遍历:先判断节点是否为空,如果不为空,则输出。
再判断左节点是否为空,如果不为空,则递归调用,直到遍历到最左边。
接着再遍历最左边的右子树,如果此时右子树不为空,则递归遍历左子树的操作,直到遍历到叶子节点。
如果右子树为空,则回溯上次的递归调用,重复输出和遍历右子树的操作。
中序遍历:先遍历左节点是否为空,如果不为空,则递归调用,直到遍历到最左边或者叶子节点,然后输出,接着再遍历最左边的右子树,如果此时右子树不为空,则递归重复遍历左子树的操作,直到遍历到叶子节点。
如果右子树为空,则回溯到上次递归调用,重复输出和遍历右子树的操作。
后序遍历:先判断左节点是否为空,如果不为空则一直递归直到遍历到最左边,然后遍历右节点,再接着遍历到左子树的最右边,直到遍历到叶子节点。
此时输出,回溯到上次递归,继续执行后面的操作,重复,直到将整个树遍历完毕。
2. 用非递归算法遍历设计思想:主要是通过栈的存取,判空,从而实现树的遍历前序遍历:通过一个循环实现。
先输出节点的数值,因为栈的特性,则需要先判断右子树是否为空,如果不为空,则将右子树压栈。
然后判断左子树是否为空,如果不为空,则将左子树压栈。
接着再将栈里面的子树弹出赋给给当前节点变量,重复上述操作,直到栈为空后退出循环。
中序遍历:通过循环实现。
将树一直遍历到最左端,并将中间所经过的节点保存在栈中,当遍历到最左边的时候,则弹出栈里面的子树。
输出数值,将当前节点赋值为当前节点的右子树,遍历右子树,即重复上述操作,直到当前节点为空,并且栈内元素为0。
后序遍历:通过循环和标记栈实现。
将数一直遍历到最左端,并将中间的节点保存在树栈中,同时同步的添加一个标记栈。
当遍历到最左边的时候,弹栈并赋值给当前栈,然后判断标记栈的数值,如果数值为0的话则代表当前树没有遍历过,遍历右子树。
然后重复上面的操作,如果数值为1的话则代表此时数已经遍历过了,可以开始输出了,为了避免重复输出,将当前栈赋为空。
重复循环操作,直到栈内没有元素,且当前节点为空(因为一直左的操作并没有将右子树压栈)。
- 1 -用递归、非递归两种方法遍历二叉树二、算法流程图开开开Root=Tree t Root=Tree t Root=Tree tYYYRoot=nullRoot=nullRoot=nullNNNN输出数NRoot.getRoot.getTree=nullNTree=nullRoot.get YTree=nullY输出数NYRoot.getTree=nullNNRoot.getRoot.get YTree=nullTree=null输出数YY结束结束结束图2 递归算法-后序遍历先序遍历-递归算法图1 图3 递归算法-中序遍历- 2 -用递归、非递归两种方法遍历二叉树开始开Tree t=root Tree t=root NNt = null压t = null outpu YYt=current.getLtree()Nt.getRtree=t=Pus nullstack.Pop()Youtpu Nt.getLtree=Pusnullt=current.getRltree()YNt=栈为Nstack.pop()栈为YY结束结束 -5 -4 图非递归算法先序遍历图非递归算法中序遍历- 3 -用递归、非递归两种方法遍历二叉树开Tree t=rootNt = null标签栈压PushYt=t.getLtree()t=stack.pop()标签栈出赋值给标志N判断栈是否t=t.getRTree(标签栈压经入栈Yt出栈并赋OutputCurrent=nullN树栈为空且当前节点为Y结束-6 图非递归算法后序遍历- 4 -用递归、非递归两种方法遍历二叉树三、源代码#include<stdio.h>#include<stdlib.h>typedef char ElemType;//定义树结构typedef struct tree{ElemType data;struct tree * lchild;struct tree * rchild;unsigned int isOut; //专为后序遍历设置的,0为不需要被输出,1为需要被输出}TreeNode, *Tree;//定义栈结构typedef struct stack{Tree * base;Tree * top;int stacksize;}SqStack;void InitStack( SqStack &s );void Push( SqStack &s, Tree e );void GetTop( SqStack s, Tree &e );void Pop( SqStack &s, Tree &e );int StackEmpty( SqStack s );void CreateTree(Tree &t);void PreOrder(Tree t);void PreOrder1(Tree t);void InOrder(Tree t);void InOrder1(Tree t);void PostOrder(Tree t);void PostOrder1(Tree t);int main(){Tree T;printf(\按先序序列输入结点序列,'*'代表空:);CreateTree(T);printf(\递归先序遍历的结果:);PreOrder(T);- 5 -用递归、非递归两种方法遍历二叉树printf(\非递归先序遍历的结果:);PreOrder1(T);printf(\递归中序遍历的结果:);InOrder(T);printf(\非递归中序遍历的结果:);InOrder1(T);printf(\递归后序遍历的结果:);PostOrder(T);printf(\非递归后序遍历的结果:);PostOrder1(T);printf(\);return 0;}初始化栈void InitStack( SqStack &s ) // {s.base = (Tree *)malloc(100*sizeof(Tree));if ( !s.base ){程序将推出执行!\n); printf(InitStack内存分配出错,exit (-1);}s.top = s.base;s.stacksize = 100;}void Push (SqStack &s, Tree e ) //元素入栈接收一个stack 类型变量和一个tree* 类型变量{if ( s.top - s.base >= s.stacksize ){s.base = (Tree *)realloc(s.base,(s.stacksize+20)*sizeof(Tree));if ( !s.base ){printf(Push内存分配出错,程序将退出执行\n);exit (-1);}// s.top = s.base + s.stacksize;s.stacksize += 20;}e->isOut = 0;*s.top++ = e;}void GetTop( SqStack s, Tree &e ) //获得栈顶元素- 6 -用递归、非递归两种方法遍历二叉树{e = *(s.top - 1); //s.top为tree** 类型}出栈void Pop( SqStack &s, Tree &e ) // {if ( s.top == s.base ){牰湩晴尨栈为空\n);return ;}e = *(--s.top);}int StackEmpty( SqStack s ) //判断栈是否为空{if ( s.top == s.base )return 1;return 0;}//void CreateTree(Tree &t) 以先序序列建立树{ char ch;scanf(%c,&ch);if ( ch == '*' )t = NULL;else{t = (Tree)malloc(sizeof(TreeNode));if ( !t ){); 牰湩晴尨分配内存出错!return ;}t->data = ch;CreateTree(t->lchild);CreateTree(t->rchild);}}// void PreOrder(Tree t) 递归先序遍历,遍历顺序:根、左、右{- 7 -用递归、非递归两种方法遍历二叉树//先访问根节点,再先序遍历左子树,再先序遍历右子树if ( t ) //如果树t 不为空树,才继续执行先序遍历{printf(%c ,t->data);PreOrder(t->lchild);PreOrder(t->rchild);}}递归中序遍历,遍历顺序:左、中、右void InOrder(Tree t) // {//先中序遍历左子树,再访问根节点,再中序遍历右节点t 为空树,则停止向下遍历//如果树if ( t ) {InOrder(t->lchild);printf(%c ,t->data);InOrder(t->rchild);}}//递归后序遍历,遍历顺序:左、右、根void PostOrder(Tree t){if ( t ){PostOrder(t->lchild);PostOrder(t->rchild);printf(%c ,t->data);}}非递归先序遍历void PreOrder1(Tree t) // {为//p 类型变量Tree p = t; tree*SqStack s;InitStack(s);//while ( p || !StackEmpty(s) ) 当树的节点不为空或栈不为空执行循环{ // 当数的此节点不为空时,打印此节点值且将此节点入栈if ( p ){printf(%c ,p->data);Push(s,p);p = p->lchild;}- 8 -用递归、非递归两种方法遍历二叉树else //否则父节点出栈,p指向父节点的右子树{Pop(s,p);p = p->rchild;}}}//非递归中序遍历void InOrder1(Tree t){Tree p = t;SqStack s;InitStack(s);while ( p || !StackEmpty(s) ){if ( p ){Push(s,p);p = p->lchild;}else{Pop(s,p);printf(%c ,p->data);p = p->rchild;}}}void PostOrder1(Tree t) //非递归后序遍历,遍历顺序:左、右、根{// t->isOut = 0; 初始值表示不输出Tree p = t;SqStack s;InitStack(s);或节点非空while ( p || !StackEmpty(s) ) // 栈非空执行循环{if ( p ){if ( p->isOut )左右子树都已输出,则该节点也输出// {Pop(s,p);printf(%c ,p->data);- 9 -用递归、非递归两种方法遍历二叉树if (!StackEmpty(s))GetTop(s,p); //得到该节点元素的父节点elsep = NULL;}else{if ( (p->lchild) && (p->lchild->isOut == 1) ){ , //如果存在左子树并且左子树已经遍历完,则说明该节点已经入栈p->isOut = 1;p = p->rchild;}否则入栈该节点的树,并且走向它的左子树//else{Push(s,p);p = p->lchild;}}}else{GetTop(s,p);if ( p->rchild ){p = p->rchild;}else{Pop(s,p);printf(%c ,p->data);p->isOut = 1;if (!StackEmpty(s)){GetTop(s,p);if ( p->lchild == NULL )// p->isOut = 1;置isOut 右子树已输出,将父节点1}elsep = NULL;}}}}- 10 -用递归、非递归两种方法遍历二叉树四、运行结果7 遍历二叉树运行结果图图五、遇到的问题及解决这部分我主要遇到了如下三个问题,其内容与解决方法如下所列:?第一个问题:递归的使用,没有完全理解递归的含义描述:递归的使用是每次都将上次调用的现场保留,直到本次的方法的完成才会返回上次的调用的现场,由于没有完全的了解,所以在调用的时候回忽略掉上次保存的现场。