下载文档原格式
中序遍历二叉树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`，其中栈用于存储遍历过程中的节点。
二叉树的后序遍历非递归算法二叉树的后序遍历是指先遍历左子树，再遍历右子树，最后遍历根节点。
在递归算法中，我们可以很容易地实现后序遍历。
但是，在非递归算法中，我们需要使用一些数据结构来模拟递归的过程。
我们需要一个栈来存储节点。
我们从根节点开始，将其入栈。
然后，我们进入一个循环，直到栈为空。
在循环中，我们首先取出栈顶节点，如果该节点没有左右子节点，或者其左右子节点已经被访问过了，那么我们就可以访问该节点。
否则，我们需要将其左右子节点依次入栈，并标记它们为未访问状态。
具体来说，我们可以使用一个辅助栈来记录每个节点的状态。
对于每个节点，我们将其入栈，并将其状态设置为未访问。
然后，我们进入一个循环，直到栈为空。
在循环中，我们首先取出栈顶节点，如果该节点的状态为已访问，那么我们就可以访问该节点，并将其从栈中弹出。
否则，我们需要将其状态设置为已访问，并将其左右子节点依次入栈，并将它们的状态设置为未访问。
下面是具体的代码实现：```void postorderTraversal(TreeNode* root) {if (!root) return;stack<TreeNode*> s1, s2;s1.push(root);while (!s1.empty()) {TreeNode* node = s1.top();s1.pop();s2.push(node);if (node->left) s1.push(node->left);if (node->right) s1.push(node->right);}while (!s2.empty()) {TreeNode* node = s2.top();s2.pop();visit(node);}}```在这个算法中，我们使用了两个栈，其中s1用于存储待访问的节点，s2用于存储已访问的节点。
我们首先将根节点入栈s1中，然后进入一个循环，直到s1为空。
数据结构求二叉树的深度二叉树深度是指从根节点到最远叶子节点的最长路径上的节点数量。
求二叉树的深度是一个常见的问题，通常可以用递归或者非递归的方式来解决。
一、递归方法：递归是一种自上而下的解决问题的方式，在求二叉树深度时，可以使用递归来解决。
递归的思路是，对于一个根节点，它的深度等于其左子树和右子树中较大的深度加1下面是递归方法的实现，以Python语言为例：```def get_depth(root):if root is None:return 0left_depth = get_depth(root.left)right_depth = get_depth(root.right)return max(left_depth, right_depth) + 1```该递归函数的基本情况是，如果根节点为空，则深度为0；否则，递归计算左子树和右子树的深度，并取较大值，最后加1即为整个二叉树的深度。
二、非递归方法：非递归方法是一种自下而上的解决问题的方式，在求二叉树深度时，可以使用非递归的方式来解决。
非递归的思路是，使用层次遍历的方式遍历二叉树的每一层，每遍历一层，深度加1，直到遍历完所有节点。
下面是非递归方法的实现，以Python语言为例：```def get_depth(root):if root is None:return 0depth = 0queue = [root]while queue:depth += 1level_size = len(queue)for _ in range(level_size):node = queue.pop(0)if node.left:queue.append(node.left)if node.right:queue.append(node.right)return depth```该非递归函数的基本思路是，首先判断根节点是否为空，如果为空则深度为0；否则，初始化深度为0和一个队列，将根节点入队，然后进入循环，每一次循环代表一层，首先将循环变量level_size设置为队列的长度，然后将队头元素出队，并将其左右子节点入队，直到队列为空。
二叉树的各种算法1.二叉树的前序遍历算法：前序遍历是指先访问根节点，再访问左子树，最后访问右子树的遍历顺序。
具体算法如下：-如果二叉树为空，则直接返回。
-访问根节点，并输出或进行其他操作。
-递归地前序遍历左子树。
-递归地前序遍历右子树。
2.二叉树的中序遍历算法：中序遍历是指先访问左子树，再访问根节点，最后访问右子树的遍历顺序。
具体算法如下：-如果二叉树为空，则直接返回。
-递归地中序遍历左子树。
-访问根节点，并输出或进行其他操作。
-递归地中序遍历右子树。
3.二叉树的后序遍历算法：后序遍历是指先访问左子树，再访问右子树，最后访问根节点的遍历顺序。
具体算法如下：-如果二叉树为空，则直接返回。
-递归地后序遍历左子树。
-递归地后序遍历右子树。
-访问根节点，并输出或进行其他操作。
4.二叉树的层序遍历算法：层序遍历是按照从上到下、从左到右的顺序逐层遍历二叉树的节点。
具体算法如下：-如果二叉树为空，则直接返回。
-创建一个队列，将根节点入队。
-循环执行以下步骤，直到队列为空：-出队并访问当前节点，并输出或进行其他操作。
-若当前节点的左子节点不为空，则将左子节点入队。
-若当前节点的右子节点不为空，则将右子节点入队。
5.二叉树的深度算法：二叉树的深度是指从根节点到叶节点的最长路径的节点数。
具体算法如下：-如果二叉树为空，则深度为0。
-否则，递归地计算左子树的深度和右子树的深度，然后取较大的值加上根节点的深度作为二叉树的深度。
6.二叉树的查找算法：二叉树的查找可以使用前序、中序或后序遍历来完成。
具体算法如下：-如果二叉树为空，则返回空。
-如果当前节点的值等于目标值，则返回当前节点。
-否则，先在左子树中递归查找，如果找到则返回找到的节点。
-如果左子树中未找到，则在右子树中递归查找，如果找到则返回找到的节点。
-如果左右子树中都未找到，则返回空。
7.二叉树的插入算法：二叉树的插入可以使用递归或循环来实现。
具体算法如下：-如果二叉树为空，则创建一个新节点作为根节点，并返回根节点。
判断两颗⼆叉树是否相似的两种⽅法名称:判断两个⼆叉树是否相似说明:此处的两个⽅法⼀个是⾮递归，⼀个是递归算法。
其实两个算法的本质思路是⼀样的就是，判断位置相同的两个结点是否同时为空或同时不为空。
只是具体的实现不⼀样。
对于层次遍历法：此处不⼩⼼⽤错了，本应该⽤队列来当作排列下⼀层元素的。
歪打正着，此处⽤栈也可以，只是判断的结点顺序不⼀样。
队列的话，是从每⼀层的左端到右端。
栈的话，是从右端到左端。
在此处都没影响。
我去，有发现⼀点，要从右到左访问⼀层的元素的话，应该⽤栈。
对于递归，看起来⽐⾮递归要简单不少。
基本的思路很简单，要注意的是，在程序需要从⼦树接收返回是否相似的信息。
这样的话，有⼀个问题，就是必须等树完全判断完才可以最终返回。
不想上⾯的，过程中发现不⼀样就可以⽴即返回了。
//层次遍历法判断两棵树是否相似bool IsSemblable1(BiTree T1,BiTree T2){stack<BiTNode* > _sta1,_sta2; //⽤来存放下⼀层元素的容器，此处栈和队列都⾏BiTNode *p1 = T1,*p2 = T2; //p1⽤来跟踪T1,p2⽤来跟踪T2while((_sta1.empty() == false || p1 != NULL) &&(_sta2.empty() == false || p2 != NULL)){if(p1 != NULL && p2 != NULL ) //如果p1和p2都不为空时{if(p1->lchild != NULL && p2->lchild != NULL) //如果p1和p2的左⼦树都不为空时{_sta1.push(p1->lchild);_sta2.push(p2->lchild);}else if( p1->lchild != NULL || p2->lchild != NULL) //如果p1的左⼦树为空，但是p2的左⼦树不为空，或者相反return false;if(p1->rchild != NULL && p2->rchild != NULL) //如果p1和p2的右⼦树都不为空时{_sta1.push(p1->rchild);_sta2.push(p2->rchild);}else if(p1->rchild != NULL || p2->rchild != NULL) //如果p1的右⼦树为空，但是p2的右⼦树不为空，或者相反return false;//访问完两棵树的当前结点后，置空让下⼀次循环弹出栈中元素（此处其实直接弹出元素也⾏）p1 = NULL;p2 = NULL;}else if(p1 != NULL || p2 != NULL) //当前节点有⼀个为空return false;else{//弹出两个树的栈顶元素p1 = _sta1.top();p2 = _sta2.top();_sta1.pop();_sta2.pop();}}return true;}//递归判断两棵树是否相似bool IsSemblable2(BiTree T1,BiTree T2){bool leftS = false,rightS = false; //⽤来接受⼦树返回的信息if(T1 == NULL && T2 == NULL) //两个结点都为空return true;else if(T1 == NULL || T2 == NULL) //有⼀个结点不为空return false;else{int leftS = IsSemblable2(T1->lchild,T2->lchild); //递归左⼦树int rightS = IsSemblable2(T1->rchild,T2->rchild); //递归右⼦树return leftS && rightS ; //返回两个⼦树的信息}}总结以上就是这篇⽂章的全部内容了，希望本⽂的内容对⼤家的学习或者⼯作具有⼀定的参考学习价值，谢谢⼤家对的⽀持。
二叉树的遍历实验报告一、实验目的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. 了解二叉树的遍历方式：前序遍历、中序遍历和后序遍历。
2. 能够使用递归和非递归两种方法实现二叉树的遍历。
3. 能够分析和比较不同遍历方式的时间复杂度和空间复杂度。
二、教学内容：1. 二叉树的遍历概念及分类。
2. 递归遍历算法的原理及实现。
3. 非递归遍历算法的原理及实现。
4. 比较不同遍历方式的时间复杂度和空间复杂度。
三、教学重点：1. 能够理解二叉树的遍历分类及其特点。
2. 能够使用递归和非递归两种方法实现二叉树的遍历。
四、教学难点：1. 非递归遍历算法的实现。
2. 比较不同遍历方式的时间复杂度和空间复杂度。
五、教学过程：1. 导入新知识，激发学生兴趣（5分钟）教师通过展示一棵二叉树的图片引入二叉树的遍历概念，并让学生猜测遍历的意义。
2. 介绍二叉树的遍历分类及特点（10分钟）教师介绍二叉树的遍历分类：前序遍历（根-左-右）、中序遍历（左-根-右）和后序遍历（左-右-根），并讲解每种遍历方式的特点。
3. 介绍递归遍历算法的原理及实现（15分钟）教师通过演示前序遍历的递归算法实现，介绍递归遍历的原理和递归函数的编写，让学生理解递归遍历的思路。
4. 演示递归遍历算法的应用（15分钟）教师在白板上画一棵二叉树，演示如何使用递归算法实现不同的遍历方式，并让学生跟随演示进行练习。
5. 介绍非递归遍历算法的原理及实现（15分钟）教师介绍非递归遍历算法的思路，包括使用栈数据结构进行遍历的原理及实现。
6. 演示非递归遍历算法的应用（15分钟）教师在白板上画一棵二叉树，演示如何使用非递归算法实现不同的遍历方式，并让学生跟随演示进行练习。
7. 比较不同遍历方式的时间复杂度和空间复杂度（10分钟）教师比较不同遍历方式的时间复杂度和空间复杂度，让学生了解不同的遍历方式在不同场景下的优劣。
8. 小结与作业布置（5分钟）教师对本节课进行小结，并布置作业：编写一个程序，实现二叉树的遍历，并分析所用遍历方式的时间复杂度和空间复杂度。
二叉树的创建与遍历的实验总结引言二叉树是一种重要的数据结构，在计算机科学中有着广泛的应用。
了解二叉树的创建和遍历方法对于数据结构的学习和算法的理解至关重要。
本文将对二叉树的创建和遍历进行实验，并总结相应的经验和思考。
二叉树的定义在开始实验之前，我们首先需要了解二叉树的定义和基本概念。
二叉树是一种每个节点最多拥有两个子节点的树形结构。
每个节点包含一个值和指向其左右子节点的指针。
根据节点的位置，可以将二叉树分为左子树和右子树。
创建二叉树二叉树的创建可以采用多种方法，包括手动创建和通过编程实现。
在实验中，我们主要关注通过编程方式实现二叉树的创建。
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语言进行程序设计。
巩固和加深对线性表、栈、队列、字符串、树、图、查找、排序等理论知识的理解；掌握现实复杂问题的分析建模和解决方法（包括问题描述、系统分析、设计建模、代码实现、结果分析等）；提高利用计算机分析解决综合性实际问题的基本能力。
树的遍历分为前序、中序和后序，可以用递归算法实现树的三种遍历。
除了递归外还可以构造栈，利用出栈和入栈来实现树的前序遍历、中序遍历和后序遍历。
先序遍历二叉树的算法非递归算法一、引言二叉树是一种常见的数据结构，其遍历方式包括先序遍历、中序遍历和后序遍历。
先序遍历是一种常用的遍历方式，它按照根节点-左子树-右子树的顺序访问每个节点。
在递归实现先序遍历二叉树的基础上，非递归算法的出现使得算法的实现更为简洁和高效。
二、非递归算法原理非递归算法的实现原理基于栈数据结构。
我们首先将根节点入栈，然后不断弹出栈顶元素并访问，同时将右子树和左子树分别入栈。
当栈为空时，表示遍历完成。
这种方法避免了递归调用可能导致的堆栈溢出问题，同时提高了算法的效率。
三、非递归算法实现以下是用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//访问根结点。
⼆叉树的三种遍历⽅式⼀、⼆叉树的定义⼆叉树(Binary Tree)的递归定义：⼆叉树要么为空，要么由根节点(root)、左⼦树(left subtree)和右⼦树(right subtree)组成，⽽左⼦书和右⼦树分别是⼀颗⼆叉树。
注意，在计算机中，树⼀般是"倒置"的，即根在上，叶⼦在下。
⼆、⼆叉树的层次遍历三种遍历⽅式：先序遍历、中序遍历、后序遍历（根据根节点的顺序）PreOrder(T) = T的根节点 + PreOrder(T的左⼦树) + PreOrder(T的右⼦树)InOrder(T) = InOrder(T的左⼦树) + T的根节点 + InOrder(T的右⼦树)PostOrder(T) = PostOrder(左⼦树) + PostOrder(右⼦树)其中加号表⽰字符串连接这三种遍历都是递归遍历或者说深度优先遍历 (DFS,Depth-First-Search)三、已知两种遍历⽅式，推出另⼀种遍历⽅式先序+中序---->后序后序+中序---->先序因为后序或先序可以直接得到根节点，然后只要在中序遍历中找到，就知道左右⼦树的中序和后序遍历，递归下去就可以构造出⼆叉树了。
四、样例(1) 题意：给⼀颗点带权（各权值都不相同，都是⼩于10000的整数）的⼆叉树的中序和后序遍历，找⼀个叶⼦节点使它到根的路径上的权应尽量少。
(2) 代码实现：1 #include<stdio.h>2 #include<iostream>3 #include<algorithm>4 #include<cstring>5 #include<string>6 #include<sstream>7using namespace std;89const int INF = 0x3f3f3f3f;10//因为各节点的权值各不相同且都只是整数，直接⽤权值作为节点编号11const int maxn = 10000 + 10;12int in_order[maxn], post_order[maxn], lch[maxn], rch[maxn];13int n;14int best, best_sum;1516//按⾏读取数据，并存到数组中17bool read_list(int *a)18{19string line;20if (!getline(cin, line)) return false;21 stringstream ss(line);22 n = 0;23int x;24while (ss >> x) a[n++] = x;25return n > 0;26}2728//把in_order[L1,R1]和post_order[L2,R2]建成⼀棵⼆叉树，返回树根29int build(int L1, int R1, int L2, int R2)30{31if (L2 > R2) return0; //空树32int root = post_order[R2];33int pos = L1;34while (in_order[pos] != root) pos++;35int cnt = pos - L1;36 lch[root] = build(L1, pos - 1, L2, L2 + cnt - 1);37 rch[root] = build(pos + 1, R1, L2 + cnt, R2 - 1);38return root;39}4041//从根节点出发，中序遍历，查找最⼩值42void dfs(int u, int sum)43{44 sum += u;4546//到达叶⼦节点，循环终⽌47if (!lch[u] && !rch[u])48 {49if (sum < best_sum)50 {51 best = u;52 best_sum = sum;53 }54return;55 }5657//加了个剪枝：如果当前的和⼤于当前的最⼩和，就不必从这条路继续搜58if (lch[u] && sum < best_sum) dfs(lch[u], sum);59if (rch[u] && sum < best_sum) dfs(rch[u], sum);60}6162int main()63{64while (read_list(in_order))65 {66 read_list(post_order);67 build(0, n - 1, 0, n - 1);6869 best_sum = INF;70 dfs(post_order[n - 1], 0);71 cout << best << endl;72 }73return0;74 }。
.一、设计思想1. 用递归算法遍历设计思想：主要是通过不同程序顺序，从而实现递归的顺序遍历前序遍历：先判断节点是否为空，如果不为空，则输出。
再判断左节点是否为空，如果不为空，则递归调用，直到遍历到最左边。
接着再遍历最左边的右子树，如果此时右子树不为空，则递归遍历左子树的操作，直到遍历到叶子节点。
如果右子树为空，则回溯上次的递归调用，重复输出和遍历右子树的操作。
中序遍历：先遍历左节点是否为空，如果不为空，则递归调用，直到遍历到最左边或者叶子节点，然后输出，接着再遍历最左边的右子树，如果此时右子树不为空，则递归重复遍历左子树的操作，直到遍历到叶子节点。
如果右子树为空，则回溯到上次递归调用，重复输出和遍历右子树的操作。
后序遍历：先判断左节点是否为空，如果不为空则一直递归直到遍历到最左边，然后遍历右节点，再接着遍历到左子树的最右边，直到遍历到叶子节点。
此时输出，回溯到上次递归，继续执行后面的操作，重复，直到将整个树遍历完毕。
2. 用非递归算法遍历设计思想：主要是通过栈的存取，判空，从而实现树的遍历前序遍历：通过一个循环实现。
先输出节点的数值，因为栈的特性，则需要先判断右子树是否为空，如果不为空，则将右子树压栈。
然后判断左子树是否为空，如果不为空，则将左子树压栈。
接着再将栈里面的子树弹出赋给给当前节点变量，重复上述操作，直到栈为空后退出循环。
中序遍历：通过循环实现。
将树一直遍历到最左端，并将中间所经过的节点保存在栈中，当遍历到最左边的时候，则弹出栈里面的子树。
输出数值，将当前节点赋值为当前节点的右子树，遍历右子树，即重复上述操作，直到当前节点为空，并且栈内元素为0。
后序遍历：通过循环和标记栈实现。
将数一直遍历到最左端，并将中间的节点保存在树栈中，同时同步的添加一个标记栈。
当遍历到最左边的时候，弹栈并赋值给当前栈，然后判断标记栈的数值，如果数值为0的话则代表当前树没有遍历过，遍历右子树。
然后重复上面的操作，如果数值为1的话则代表此时数已经遍历过了，可以开始输出了，为了避免重复输出，将当前栈赋为空。
重复循环操作，直到栈内没有元素，且当前节点为空（因为一直左的操作并没有将右子树压栈）。
.二、算法流程图图1 递归算法-先序遍历 图2 递归算法-后序遍历 图3 递归算法-中序遍历图4 非递归算法-先序遍历 图5 非递归算法-中序遍历图6 非递归算法-后序遍历三、源代码#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("\n按先序序列输入结点序列，'*'代表空：");CreateTree(T);printf("\n 递归先序遍历的结果： ");PreOrder(T);printf("\n非递归先序遍历的结果：");PreOrder1(T);printf("\n 递归中序遍历的结果： ");InOrder(T);printf("\n非递归中序遍历的结果：");InOrder1(T);printf("\n 递归后序遍历的结果： ");PostOrder(T);printf("\n非递归后序遍历的结果：");PostOrder1(T);printf("\n");return 0;}void InitStack( SqStack &s ) //初始化栈{s.base = (Tree *)malloc(100*sizeof(Tree));if ( !s.base ){printf("InitStack内存分配出错,程序将推出执行！\n");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 ) //获得栈顶元素{e = *(s.top - 1); //s.top为 tree** 类型}void Pop( SqStack &s, Tree &e ) //出栈{if ( s.top == s.base ){printf("栈为空\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 ){printf("分配内存出错！");return ;}t->data = ch;CreateTree(t->lchild);CreateTree(t->rchild);}}void PreOrder(Tree t) //递归先序遍历，遍历顺序：根、左、右{//先访问根节点，再先序遍历左子树，再先序遍历右子树if ( t ) //如果树 t 不为空树，才继续执行先序遍历{printf("%c ",t->data);PreOrder(t->lchild);PreOrder(t->rchild);}}void InOrder(Tree t) //递归中序遍历，遍历顺序：左、中、右{ //先中序遍历左子树，再访问根节点，再中序遍历右节点if ( t ) //如果树 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) //非递归先序遍历{Tree p = t; //p为 tree* 类型变量SqStack s;InitStack(s);while ( p || !StackEmpty(s) ) //当树的节点不为空或栈不为空执行循环 {if ( p ) //当数的此节点不为空时，打印此节点值且将此节点入栈{printf("%c ",p->data);Push(s,p);p = p->lchild;}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);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;}}}}四、运行结果图7 遍历二叉树运行结果图五、遇到的问题及解决这部分我主要遇到了如下三个问题，其内容与解决方法如下所列：●第一个问题：递归的使用，没有完全理解递归的含义描述：递归的使用是每次都将上次调用的现场保留，直到本次的方法的完成才会返回上次的调用的现场，由于没有完全的了解，所以在调用的时候回忽略掉上次保存的现场。
