下载文档原格式
中序遍历二叉树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. 用非递归算法遍历设计思想：主要是通过栈的存取，判空，从而实现树的遍历前序遍历：通过一个循环实现。
先输出节点的数值，因为栈的特性，则需要先判断右子树是否为空，如果不为空，则将右子树压栈。
然后判断左子树是否为空，如果不为空，则将左子树压栈。
接着再将栈里面的子树弹出赋给给当前节点变量，重复上述操作，直到栈为空后退出循环。
中序遍历：通过循环实现。
将树一直遍历到最左端，并将中间所经过的节点保存在栈中，当遍历到最左边的时候，则弹出栈里面的子树。
输出数值，将当前节点赋值为当前节点的右子树，遍历右子树，即重复上述操作，直到当前节点为空，并且栈内元素为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 遍历二叉树运行结果图五、遇到的问题及解决这部分我主要遇到了如下三个问题，其内容与解决方法如下所列：●第一个问题：递归的使用，没有完全理解递归的含义描述：递归的使用是每次都将上次调用的现场保留，直到本次的方法的完成才会返回上次的调用的现场，由于没有完全的了解，所以在调用的时候回忽略掉上次保存的现场。
