下载文档原格式
中序遍历二叉树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出栈并访问，此时栈为空，遍历结束。
通过这个例子，我们可以看到中序遍历的非递归算法确实按照中序遍历的顺序访问了二叉树的所有节点。
后序遍历的非递归算法（C详细）后序遍历是二叉树遍历的一种方式，它的顺序是先遍历左子树，然后遍历右子树，最后访问根节点。
非递归实现后序遍历的算法可以使用栈来辅助实现。
首先，我们需要定义一个树节点的数据结构，例如：```cstruct TreeNodeint val;struct TreeNode* left;struct TreeNode* right;};```接下来，我们使用一个辅助栈来进行非递归后序遍历。
首先需要创建一个空栈，并将根节点入栈。
然后开始循环，直到栈为空为止。
在循环中，首先取出栈顶节点，如果该节点没有左子树且没有右子树，说明该节点是叶子节点，可以直接输出该节点的值。
如果该节点有左子树或者右子树，需要判断是否已经遍历过该节点的子节点。
为了实现后序遍历的顺序，我们需要一个标记变量来记录上次访问的节点。
如果上次访问的节点是该节点的右子树，说明该节点的左右子节点都已经访问过了，可以直接输出该节点的值。
反之，如果上次访问的节点不是该节点的右子树，将该节点重新入栈，并以右、左、中的顺序将其右子树、左子树入栈。
下面给出完整的代码实现：```c#include <stdio.h>#include <stdlib.h>struct TreeNodeint val;struct TreeNode* left;struct TreeNode* right;};void postOrderTraversal(struct TreeNode* root)if (root == NULL)return;}struct TreeNode* lastVisited = NULL; // 上次访问的节点struct TreeNode* node = root; // 当前遍历的节点struct TreeNode* stack[100]; // 栈int top = -1; // 栈顶指针while (node != NULL ， top != -1)if (node != NULL)stack[++top] = node; // 入栈node = node->left; // 访问左子树} elsestruct TreeNode* temp = stack[top]; // 取出栈顶节点if (temp->right == NULL ， temp->right == lastVisited) printf("%d ", temp->val);top--; // 出栈lastVisited = temp; // 记录上次访问的节点} elsenode = temp->right; // 访问右子树}}}struct TreeNode* createNode(int val)struct TreeNode* node = (structTreeNode*)malloc(sizeof(struct TreeNode));if (node != NULL)node->val = val;node->left = NULL;node->right = NULL;}return node;int mai//创建一个二叉树struct TreeNode* root = createNode(1); root->left = createNode(2);root->right = createNode(3);root->left->left = createNode(4);root->left->right = createNode(5); root->right->left = createNode(6); root->right->right = createNode(7);//后序遍历二叉树printf("后序遍历结果："); postOrderTraversal(root);printf("\n");return 0;```以上代码中，我们使用了一个辅助数组作为栈来实现非递归遍历。
二叉树后序遍历的非递归算法
二叉树后序遍历是指按照左子树、右子树、根节点的顺序遍历二叉树的过程。
与前序遍历和中序遍历不同，后序遍历需要考虑根节点的位置，因此需要使用栈来存储节点信息。
非递归算法一般使用栈来实现，因为后序遍历的过程中需要先遍历左子树和右子树，最后才遍历根节点，所以存储节点信息的栈需要进行一些特殊处理。
下面是二叉树后序遍历的非递归算法：
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. 若该节点存在右子节点，则将右子节点压入栈中。
3. 若该节点存在左子节点，则将左子节点压入栈中。
注：先将右子节点压入栈中，再将左子节点压入栈中的原因是，出栈操作时会先访问左子节点。
下面是使用Python语言实现的例子：```pythonclass TreeNode:def __init__(self, value):self.val = valueself.left = Noneself.right = Nonedef preorderTraversal(root):if root is None:return []stack = []result = []node = rootwhile stack or node:while node:result.append(node.val)stack.append(node)node = node.leftnode = stack.pop()node = node.rightreturn result```这里的树节点类为`TreeNode`，其中包含节点的值属性`val`，以及左子节点和右子节点属性`left`和`right`。
`preorderTraversal`函数为非递归的先序遍历实现，输入参数为二叉树的根节点。
函数中使用了一个栈`stack`来存储节点，以及一个列表`result`来存储遍历结果。
在函数中，先判断根节点是否为None。
如果是，则直接返回空列表。
然后，创建一个空栈和结果列表。
接下来，用一个`while`循环来执行上述的遍历过程。
循环的条件是栈`stack`不为空或者当前节点`node`不为None。
中序遍历非递归算法一、前言在二叉树的遍历中，中序遍历是一种重要的遍历方式。
中序遍历非递归算法是指不使用递归函数，通过循环和栈等数据结构实现对二叉树进行中序遍历。
本文将详细介绍中序遍历非递归算法的实现过程和相关知识点。
二、中序遍历的定义在二叉树中，对每个节点的访问顺序有三种方式：先访问左子树，再访问根节点，最后访问右子树；先访问根节点，再访问左子树和右子树；先访问左子树和右子树，最后访问根节点。
这三种方式分别称为前序遍历、中序遍历和后序遍历。
其中，中序遍历是指按照“先访问左子树，再访问根节点，最后访问右子树”的顺序进行访问。
三、中序遍历非递归算法的思路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. 定义两个节点变量pre和cur，初始化pre为null3. 当栈不为空时，循环执行以下操作：- 将栈顶元素cur赋值为栈顶元素，但不弹出该元素- 如果当前节点没有左右子节点，或者左右子节点已经被访问过了，那么弹出当前节点，并将其值打印输出，并将pre赋值为当前节点- 否则，若当前节点有右子节点，就将其右子节点入栈。
若当前节点有左子节点，则将其左子节点入栈4. 循环结束可以看到，后序遍历的算法和前序遍历、中序遍历都有所区别。
与前序遍历的主要区别在于，在访问节点前，需要判断该节点的左右子节点是否已经被访问过。
而与中序遍历的主要区别在于，在访问节点后，需要将该节点的值打印输出。
此外，后序遍历还需要维护一个pre节点变量，用于记录上一个被访问过的节点。
那么，后序遍历的非递归算法有什么优点呢？相比递归算法，它的空间复杂度更低，因为递归算法需要维护函数调用栈。
而非递归算法中使用的栈只需要在遍历过程中存储节点，不需要再维护函数调用栈。
此外，非递归算法在一些嵌入式系统、服务器等资源受限的环境下表现更优秀。
总体而言，后序遍历非递归算法是一种非常实用的二叉树遍历算法，它可以帮助我们更加高效地对二叉树进行遍历，尤其是在空间限制较大的情况下。
需要注意的是，该算法的具体实现过程可能会因为树结构的复杂性而略有差异，建议大家在编写代码时用心梳理整个算法过程。
二叉树的遍历学习心得 (3)
二叉树是一种经常出现在程序设计中的数据结构。
通过对二叉树的遍历，能够完成许多复杂的任务。
因此，学习二叉树的遍历方式非常重要。
首先，二叉树的遍历包括前序遍历、中序遍历和后序遍历。
其中，前序遍历就是先遍历根节点，再遍历左节点和右节点。
中序遍历是先遍历左节点，再遍历根节点和右节点。
后序遍历是先遍历左节点，再遍历右节点和根节点。
我们需要掌握这三种遍历方式，了解其原理和具体实现方法。
其次，在实现遍历方式时，我们需要使用递归或非递归的方式。
递归方式简单易懂，但是当节点较多时，会占用大量的栈空间，会导致栈溢出。
而非递归方式需要使用辅助数据结构，比如栈或队列，来实现遍历。
虽然它的代码相对复杂，但却具有灵活性和高效性。
我们要根据具体情况，选择适合的遍历方式。
最后，我们还需要注意二叉树遍历的应用。
比如，前序遍历可以用于复制树或表达式树，中序遍历可以用于对树进行排序，后序遍历可以用于计算表达式树的值等。
因此，在学习二叉树遍历的同时，还要了解它们的常见应用场景，以便更好地进行算法设计和应用实践。
总之，掌握二叉树的遍历方式和应用，对于数据结构和算法的学习非常重要。
我们要理解其原理和代码实现，并且要多加练习，深入掌握遍历的思想和技巧。
只有这样，我们才能在实际工作中灵活运用二叉树遍历，提高代码质量和效率。
⼆叉树的遍历及相关题⽬⼆叉树的遍历及相关题⽬1.1⼆叉树遍历的概念⼆叉树结构体的定义：typedef struct node{ ElemType data; struct node * lchild; struct node * rchild;}⼆叉树的遍历是指按照⼀定的次序访问⼆叉树中的所有的节点，并且每个节点仅访问⼀次的过程。
若规定先遍历左⼦树，后遍历右⼦树，则对于⾮空⼆叉树，可得到如下3种递归的遍历⽅法：（1）先序遍历访问根节点，先序遍历左⼦树，先序遍历右⼦树。
（根，左，右）（2）中序遍历中序遍历左⼦树，访问根节点，中序遍历右⼦树。
（左，根，右）（3）后序遍历后序遍历左⼦树，后序遍历右⼦树，访问根节点。
（左，右，根）除此之外也有层次遍历。
先访问根节点，在从左到右访问第⼆层的所有节点，从左到右访问第三层的所有节点......1.2⼆叉树遍历递归算法先序遍历递归算法：void PreOrder(BTNode * b){ if(n != NULL) { cout<<b->data; PreOrder(b->lchild); PreOrder(b->rchild); }}中序遍历递归算法void InOrder(BTNode * b){ if(n != NULL) { InOrder(b->lchild); cout<<b->data; InOrder(b->rchild); }}后序遍历递归算法：void PostOrder(BTNode * b){ if(b != NULL) { PostOrder(b->lchild); PostOrder(b->rchild); cout<<b->data; }}题⽬1：输出⼀个给定⼆叉树的所有的叶⼦节点：void DispLeaf(BTNode * b){ if(b != NULL) { if(b->lchild == NULL && b->rchild == NULL) cout<<b->data; DispLeaf(b->lchild); DispLeaf(b->rchild); }}以上算法采⽤先序遍历输出了所有的叶⼦节点，所以叶⼦节点是从左到右输出的。
二叉树的遍历实验报告一、实验目的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本次实验通过实现二叉树的递归和非递归遍历算法，加深了对二叉树的理解，并熟悉了遍历算法的实现方法。
浅析一种二叉树非递归遍历算法的C语言实现论文一种二叉树非递归遍历算法的C语言实现论文导读：本论文是一篇关于一种二叉树非递归遍历算法的C语言实现的优秀论文范文,对正在写有关于递归论文的写有一定的参考和指导作用,摘要：针对二叉树的链式存储结构，分析了二叉树的各种遍历算法，探讨了递归算法的递推消除理由，提出了一种改善的非递归遍历算法并用C语言予以实现。
关键词：二叉树；遍历算法；非递归；C语言实现1009-3044（2014）01-0223-031 概述树形结构是一种非常常见的数据结构，而二叉树又是其中最重要的一种树形结构。
二叉树的遍历是指按照一定的规则和次序将二叉树中的每一个结点都访问一次，既不能重复，也不能漏掉。
一般而言，对二叉树的遍历有前序遍历、中序遍历、后序遍历和按层遍历等几种方式。
在具体的算法设计上，以上遍历方式一般采取递归算法来实现，该文将探讨采用非递归算法来实现二叉树的遍历。
2 二叉树的数据结构描述二叉树作为一种非线性结构，每个结点最多有一个双亲结点和两个子结点。
二叉树可以采用顺序存储结构和链式存储结构。
对于完全二叉树而言，采用顺序存储是非常方便并且节省空间的，但是对于大部分的非完全二叉树而言，采用顺序存储将导致空间浪费严重且结构混乱、效率低下。
因此，更多的时候，大家都更愿意用链式存储结构来表示二叉树，这样结构更加清晰，尤其是对于一种二叉树非递归遍历算法的C语言实现由写论文的好帮手.zbjy.提供,.左右子树的描述和双亲节点的描述更加方便。
该文中拟采用链式结构来表示二叉树。
用链式存储结构来表示二叉树，一个结点至少由3个域组成，即数据域、左子结点域和右子结点域（如图1所示）。
3 二叉树的遍历及递归算法实现3.1 二叉树的遍历二叉树的遍历就是一个不漏的访问树中的每个结点，同时也不能重复。
所谓“访问”，就是指对结点的数据域进行某种操作，比如说读取、删除、更新、求该节点深度等等。
对于二叉树中的任意一个部分，都可以把它看作三部分，根节点、左子树、右子树，我们用D表示访问跟结点，用L表示遍历左子树，用R表示遍历右子树，则共有以下6种遍历方式[1]。
先序遍历二叉树的算法非递归算法一、引言二叉树是一种常见的数据结构，其遍历方式包括先序遍历、中序遍历和后序遍历。
先序遍历是一种常用的遍历方式，它按照根节点-左子树-右子树的顺序访问每个节点。
在递归实现先序遍历二叉树的基础上，非递归算法的出现使得算法的实现更为简洁和高效。
二、非递归算法原理非递归算法的实现原理基于栈数据结构。
我们首先将根节点入栈，然后不断弹出栈顶元素并访问，同时将右子树和左子树分别入栈。
当栈为空时，表示遍历完成。
这种方法避免了递归调用可能导致的堆栈溢出问题，同时提高了算法的效率。
三、非递归算法实现以下是用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.定义一个栈，用于存储节点。
2.将根节点入栈。
3.当栈不为空时，执行步骤4-6，否则结束遍历。
4.弹出栈顶节点，并访问该节点。
5.若该节点有右孩子，将右孩子入栈。
6.若该节点有左孩子，将左孩子入栈。
7.返回步骤3下面是使用C语言实现先序遍历的非递归算法的示例代码：```c#include <stdio.h>#include <stdlib.h>//定义二叉树节点结构typedef struct TreeNodeint data;struct TreeNode* left;struct TreeNode* right;} TreeNode;//定义栈结构typedef struct StackTreeNode* data[100]; // 栈的最大容量int top; // 栈顶指针} Stack;Stack* createStacStack* stack = (Stack*)malloc(sizeof(Stack)); stack->top = -1;return stack;void push(Stack* stack, TreeNode* node)stack->data[++stack->top] = node;TreeNode* pop(Stack* stack)return stack->data[stack->top--];int isEmpty(Stack* stack)return stack->top == -1;//先序遍历的非递归算法void preorderTraversal(TreeNode* root)if (root == NULL)return;}Stack* stack = createStack(; // 创建栈push(stack, root); // 根节点入栈while (!isEmpty(stack))TreeNode* node = pop(stack); // 弹出栈顶节点printf("%d ", node->data); // 访问节点//右孩子先入栈，保证左孩子会在右孩子之前被访问if (node->right != NULL)push(stack, node->right);}//左孩子入栈if (node->left != NULL)push(stack, node->left);}}free(stack); // 释放栈的内存int mai//构建二叉树TreeNode* root = (TreeNode*)malloc(sizeof(TreeNode)); root->data = 1;TreeNode* node2 = (TreeNode*)malloc(sizeof(TreeNode)); node2->data = 2;TreeNode* node3 = (TreeNode*)malloc(sizeof(TreeNode)); node3->data = 3;TreeNode* node4 = (TreeNode*)malloc(sizeof(TreeNode)); node4->data = 4;TreeNode* node5 = (TreeNode*)malloc(sizeof(TreeNode)); node5->data = 5;root->left = node2;root->right = node3;node2->left = node4;node2->right = NULL;node3->left = NULL;node3->right = node5;node4->left = NULL;node4->right = NULL;node5->left = NULL;node5->right = NULL;//先序遍历printf("先序遍历结果：");preorderTraversal(root);//释放二叉树的内存free(root);free(node2);free(node3);free(node4);free(node5);return 0;```以上代码实现了二叉树先序遍历的非递归算法。
实验三：二叉树的遍历问题
题目：编制一个遍历二叉树的程序
班级：姓名：学号：完成日期：
一.需求分析
1.问题描述：很多涉及二叉树的操作的算法都是以二叉树的遍历操作为基础的。
编写程序，对一棵给定的二叉树进行先、中、后三种次序的遍历。
2.基本要求：以二叉链表为存储结构，实现二叉树的先、中、后三种次序的递归和非递归遍历。
3.测试数据：以教科书图6.9的二叉树为例。
4.实现提示：
(1).设二叉树的结点不超过30个，且每个结点的数据均为字符，这样可利用先序遍历序列作为输入顺序创建二叉树链表存储结构。
(2.)也可利用完全二叉树在顺序存储中的特性，创建二叉树的存储结构，此时，二叉树中结点数据的类型不受限制。
二.概要设计
1.为实现上述功能，应先建立二叉树。
为此，需要有一个二叉树的抽象数据类型。
该抽象数据类型的定义为：
ADT BinaryTree
{
数据对象D：D是具有相同特性的数据元素的集合
termset中每个元素包含编号，密码，和一个指向下一节点的指针数据关系R：
若D=∅，则R=∅,称BinaryTree为空二叉树；
若D≠∅，则R={H},H是如下二元关系：
(1).在R中存在唯一的称为根的数据元素root,它在关系H下无前驱；
(2).若D-(root) ≠∅, 则存在D-(root)={D1,D2},且D1∩D2=∅;
(3). D1≠∅，则D1中存在唯一的元素x1，<root,x>∈H,且存在D1上的关系
H1⊂H;若Dr≠∅,则Dr中存在唯一的元素Xr, <root,Xr>∈H,且存在Dr上的关
系Hr⊂H;H={<root,x>,<root,Xr>,H1,Hr};
(4).(D1,{H1})是一棵符合本定义的二叉树，称为根的左子树，(Dr,{Hr})是一棵
符合本定义的二叉树，称为根的右子树。
基本操作P：
createbt(BiTree& T)
操作结果：构造一棵空二叉树
PreOrder(BiTree T)
初始条件：二叉树T存在
操作结果：先序遍历T(先根，后左子树，再右子树)_ InOrder(BiTree T)
初始条件：二叉树T存在
操作结果：中序遍历T(先左子树，后根，再右子树)_ PostOrder(BiTree T)
初始条件：二叉树T存在
操作结果：后序遍历T(先左子树，后右子树，再根)_ }ADT BinaryTree
2.单向循环链表中节点的定义如下所示：
typedef struct BiTNode
{
char data; //结点数据变量
struct BiTNode *Lchild; //左孩子指针
struct BiTNode *Rchild; //右孩子指针
} BiTNode ,*BiTree;
3.本程序包含三个模块
1).主程序模块
int main( )
{
构造二叉树；
接受命令；
函数实现；
}
2).二叉树构造模块——实现二叉树的抽象数据类型
3).二叉树操作实现模块——实现二叉树的遍历
各模块之间的调用关系如下：
主程序模块
二叉树构造模块
二叉树操作的实现
三.详细设计(递归调用)
//测试序列:-+a##*b##-c##d##/e##f##
#include "stdafx.h"
#include<iostream>
using namespace std;
typedef struct BiTNode
{
char data; //结点数据变量
struct BiTNode *Lchild; //左孩子指针
struct BiTNode *Rchild; //右孩子指针
} BiTNode ,*BiTree;
//构造二叉树
void createbt(BiTree& T)
{
char ch;
cin>>ch;
if(ch=='#') T=NULL;
else
{
T=(BiTree)malloc(sizeof(BiTNode));
T->data=ch;
createbt(T->Lchild);
createbt(T->Rchild);
}
}
//先序遍历
void PreOrder(BiTree T)
{ //先序遍历以T为根指针的二叉树if(T)
{
cout<<T->data; // 通过函数指针*visit访问根结点
PreOrder(T->Lchild); //先序遍历左子树
PreOrder(T->Rchild); //先序遍历右子树}
}
//中序遍历
void InOrder(BiTree T)
{ //中序遍历以T为根指针的二叉树if(T)
{
InOrder(T->Lchild); //中序遍历左子树
cout<<T->data; //通过函数指针*visit访问根结点
InOrder(T->Rchild); //中序遍历右子树}
}
//后序遍历
void PostOrder(BiTree T)
{ //后序遍历以T为根指针的二叉树
if(T)
{
PostOrder(T->Lchild); //后序遍历左子树
PostOrder(T->Rchild); //后序遍历右子树
cout<<T->data; //通过函数指针*visit访问根结点}
}
int main()
{
BiTree T;
cout<<"输入欲建立二叉树的序列(以'#'表示结点的子树为空!): ";
createbt(T); //构造二叉树
//遍历的实现
cout<<"先序遍历: ";
PreOrder (T);
cout<<endl;
cout<<"中序遍历: ";
InOrder (T);
cout<<endl;
cout<<"后序遍历: ";
PostOrder (T);
cout<<endl;
system("PAUSE");
return 0;
}
四.调试分析
1先建立一棵二叉树，以#表示子树是否为空，最后实现数的构造
2.先序遍历该二叉树，才用先根，后左子树，再右子树的顺序实现遍历
3.中序遍历该二叉树，才用先左子树，后根，再右子树的顺序实现遍历
4.后序遍历该二叉树，才用先左子树，后右子树，再根的顺序实现遍历
五.用户手册
1．本程序的运行环境为Win7 操作系统，执行文件为：Debug/二叉树的遍历.exe 2．进入演示程序后，即现实文本方式的用户界面：
六.测试结果
依次输入上述测试序列
:-+a##*b##-c##d##/e##f##。
