用递归非递归两种方法遍历二叉树

数据结构⽤⾮递归算法求⼆叉树⾼度算法思想： 采⽤层次遍历的算法，设置变量level记录当前节点所在层数，设置变量last指向当前层的最右结点，每层遍历出队时与last指针⽐较，若两者相等，则层数加⼀，并让last指向下⼀层的最右结点即rear所在位置，直到变量完成。

level的值即为⼆叉树的⾼度。

代码如下：1int Btdepth(BiTree T)2 {3if(T==NULL) //树空⾼度为04return0;5int front=rear=-1;6int last=level=0; //last指向当前层的最右结点7 BiTree Q[MAXSIZE]; //设置队列Q，元素是⼆叉树结点指针且容量⾜够8 Q[++rear]=T; //将根节点⼊队9 BiTree p=T;10while(!IsEmpty(Q)) //11 {12 p=Q[++front]; //队列元素出队，即正在访问的结点13if(p->lchild)14 Q[++rear]=p->lchild; //左孩⼦⼊队15if(p->rchild)16 Q[++rear]=p->rchild; //右孩⼦⼊队17if(front==last) //访问到该层的最后⼀个结点18 {19 level++; //⾼度加⼀20 last=rear; //更新last指向下⼀层最右⼀个结点21 }2223 }24return level;25 }扩展：求某⼀层的结点个数，每层的结点个数、树的最⼤宽度，都采⽤与此题类似的思想。

当然，此题可采⽤递归算法，其实现如下代码如下：1int Btdepth(BiTree T)2 {3if(T==NULL) //空树⾼度为04return0;5 ldep=Btdepth(T->lchild); //递归遍历左⼦树6 rdep=Btdepth(T->rchild); //递归遍历右⼦树7if(ldep>rdep) //树的⾼度为⼦树的最⼤⾼度加根节点8return ldep+1;9else10return rdep+1;11 }。

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下面是递归方法的实现，以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设置为队列的长度，然后将队头元素出队，并将其左右子节点入队，直到队列为空。

判断两颗⼆叉树是否相似的两种⽅法名称:判断两个⼆叉树是否相似说明:此处的两个⽅法⼀个是⾮递归，⼀个是递归算法。

其实两个算法的本质思路是⼀样的就是，判断位置相同的两个结点是否同时为空或同时不为空。

只是具体的实现不⼀样。

对于层次遍历法：此处不⼩⼼⽤错了，本应该⽤队列来当作排列下⼀层元素的。

歪打正着，此处⽤栈也可以，只是判断的结点顺序不⼀样。

队列的话，是从每⼀层的左端到右端。

栈的话，是从右端到左端。

在此处都没影响。

我去，有发现⼀点，要从右到左访问⼀层的元素的话，应该⽤栈。

对于递归，看起来⽐⾮递归要简单不少。

基本的思路很简单，要注意的是，在程序需要从⼦树接收返回是否相似的信息。

这样的话，有⼀个问题，就是必须等树完全判断完才可以最终返回。

不想上⾯的，过程中发现不⼀样就可以⽴即返回了。

//层次遍历法判断两棵树是否相似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本次实验通过实现二叉树的递归和非递归遍历算法，加深了对二叉树的理解，并熟悉了遍历算法的实现方法。