数据结构小组课题——遍历二叉树(递归、非递归遍历算法)

⼆叉树的⾮递归遍历算法我们都知道，⼆叉树常见的操作之⼀就是遍历，leetcode上很多对⼆叉树的操作都是基于遍历基础之上的。

⼆叉树的遍历操作分为深度优先遍历和⼴度优先遍历，深度优先遍历包括前序、中序、后序三种遍历⽅式；⼴度优先遍历⼜叫层序遍历。

这两种遍历⽅式都是⾮常重要的，树的层序遍历⼀般是没法通过递归来实现，其遍历过程需要借助⼀个队列来实现，本质上就是图的BFS的⼀种特例，可以⽤来求⼆叉树的⾼度、宽度等信息。

我们今天要讲的是⼆叉树的前、中、后序遍历的⾮递归算法。

⼆叉树前、中、后序遍历的递归算法形式上上是⾮常简洁明了的，只要你熟练使⽤递归这⼀⽅法，应该都能写出来。

⽽⾮递归算法则显得不那么容易。

但是⾮递归算法也⾮常重要，有⼀些题⽤⾮递归算法解会简单⼀点。

其实，我觉得我们⼈类的思维就是典型的⾮递归形式的，所以，要想实现⼀个⾮递归算法，其实就是把我们脑中的求解过程转换成相应的代码。

前序⾮递归例如，对于下⾯这棵⼆叉树，我们要对其进⾏⾮递归前序遍历，该如何做？前序遍历，就是先访问根节点，再访问左⼦树，再访问右⼦树，左⼦树和右⼦树的访问过程也是这样递归进⾏。

那么我们⼀开始是依次访问1、2、4、6。

到了6的时候我们为什么要停下来呢？因为这时候我们发现，6的左⼦树为空，相当于它的左⼦树已经访问完了，按照前序遍历的定义，这个时候我们应该访问其右⼦树，我们发现6的右⼦树也为空，相当于它的右⼦树访问完了。

这个时候我们该怎么办呢？没错，这个时候说明以6为根节点的⼦树都已经访问完了，我们应该往上回溯，回到6的⽗亲结点。

从这⾥，我们发现了⼏个问题：我们每个结点都要经过3次第⼀次是从该结点的根结点往下⾛到该结点的时候经过的第⼆次是从其左⼦树返回到该结点时经过的第三次是从其右⼦树返回到该结点时经过的。

前序遍历⼀开始是不断地往左下⾓⽅向⾛，每经过⼀个结点就访问它，直到到达最左下⾓位置停下来。

每当从左孩⼦返回到根结点的时候，需要判断⼀下右⼦树是不是为空，不为空的话才去访问右⼦树。

遍历二叉树的递归与非递归算法浅析作者：李彦来源：《电脑知识与技术》2011年第24期摘要：二叉树是数据结构中最常见的一种存储形式，而遍历二叉树又是二叉树中最重要的操作。

该文分别以递归和非递归两种不同的算法来分析遍历二叉树的过程，旨在用简单明了的方法来实现二叉树的遍历，且先序、中序、后序三种遍历方式都可通过这两种算法实现。

关键词：二叉树；遍历；递归；非递归中图分类号：TP311文献标识码：A文章编号：1009-3044(2011)24-5941-02二叉树是数据结构中最常见的一种存储形式，许多实际问题抽象出来的数据结构通常都能够表示为二叉树，其运算和存储结构都较为简练，因此在算法与数据结构中经常使用。

而遍历算法又是二叉树最重要的操作。

所谓遍历二叉树，就是按照某条搜索路径寻访树中每个结点，使得每个结点均被访问一次，且仅被访问一次。

二叉树的遍历分为先序、中序和后序遍历三种方法，如何才能使初学者更好地理解二叉树的遍历算法呢？本文将从递归和非递归两种方法分别讲述二叉树的遍历过程。

1 递归算法递归是指在定义自身的同时，又出现了对自身的引用。

如果一个算法直接或间接调用自己，则称这个算法是一个递归算法。

在遍历二叉树时，递归就是将二叉树的元素分为根结点、左结点和右结点，按照左根右、根左右或左右根的顺序依次访问结点并对其做各种处理。

为了使初学者更容易理解，我们可以借助二叉树的图示来讲解。

对于三种遍历方法：前序、中序、后序，我们将二叉树拆分为根（T）和左（L）、右（R）子树，此时我们发现，无论是哪种遍历方法，左子树均在右子树之前被访问，因此可以将根结点（T）与其左、右子树拆分开来，确定了遍历的顺序，即确定了访问根结点（T）的时间是在左子树之前还是之后。

例如求下图（1）所示二叉树的中序遍历序列。

首先，先确定根结点（A）及其左右子树（B）、（C），按照中序遍历LTR的顺序，任一结点在以其为根的子树中的访问顺序为左子树、根结点、右子树。

数据结构—⼆叉树的三种遍历⽅式 树的概念： 树是n(n>=0)个有限个数据的元素集合，形状像⼀颗倒过来的树。 ⼆叉树的概念：

⼆叉树是⼀颗特殊的树，⼆叉树每个节点最多有两个孩⼦结点，分别称为左孩⼦、右孩⼦遍历⼆叉树三种种⽅式(递归实现，⾮递归实现)： 测试⽤例 int array[10]={1,2,3,'#','#','4','#','#',5,6};

前序遍历(先根遍历):（1）：先访问根节点； （2）：前序访问左⼦树；（3）：前序访问右⼦树； 【1 2 3 4 5 6】 中序遍历: （1）：中序访问左⼦树；（2）：访问根节点； （3）：中序访问右⼦树； 【3 2 4 1 6 5】 后序遍历(后根遍历):（1）：后序访问左⼦树；（2）：后序访问右⼦树；（3）：访问根节点； 【3 4 2 6 5 1】

struct BinaryTreeNode{ T _data; BinaryTreeNode* _left; BinaryTreeNode* _right;

BinaryTreeNode(const T& x) :_data(x) , _left(NULL) , _right(NULL) {}};templateclass BinaryTree{public: BinaryTree() :_root(NULL) {}

BinaryTree(const T* a, size_t size) { size_t index = 0; _root = _CreateTree(a, size, index); }

~BinaryTree() { _Destroy(_root); _root = NULL; }

BinaryTree(const BinaryTree& t) { _root = _Copy(t._root); } BinaryTree& operator= (BinaryTree t) { swap(_root, t._root);

实验5：二叉树的建立及遍历（第十三周星期三7、8节）一、实验目的1．学会实现二叉树结点结构和对二叉树的基本操作。

2．掌握对二叉树每种操作的具体实现，学会利用递归方法编写对二叉树这种递归数据结构进行处理的算法。

二、实验要求1．认真阅读和掌握和本实验相关的教材内容。

2．编写完整程序完成下面的实验内容并上机运行。

3．整理并上交实验报告。

三、实验内容1．编写程序任意输入二叉树的结点个数和结点值，构造一棵二叉树，采用三种递归遍历算法(前序、中序、后序)对这棵二叉树进行遍历并计算出二叉树的高度。

2 .编写程序生成下面所示的二叉树，并采用中序遍历的非递归算法对此二叉树进行遍历。

四、思考与提高1．如何计算二叉链表存储的二叉树中度数为1的结点数？2．已知有—棵以二叉链表存储的二叉树，root指向根结点，p指向二叉树中任一结点，如何求从根结点到p所指结点之间的路径?/*----------------------------------------* 05-1_递归遍历二叉树.cpp -- 递归遍历二叉树的相关操作* 对递归遍历二叉树的每个基本操作都用单独的函数来实现* 水上飘2009年写----------------------------------------*/// ds05.cpp : Defines the entry point for the console application.//#include "stdafx.h"#include <iostream>typedef char ElemType;using namespace std;typedef struct BiTNode {ElemType data;//左右孩子指针BiTNode *lchild, *rchild;}BiTNode, *BiTree;//动态输入字符按先序创建二叉树void CreateBiTree(BiTree &T) {char ch;ch = cin.get();if(ch == ' ') {T = NULL;}else {if(ch == '\n') {cout << "输入未结束前不要输入回车，""要结束分支请输入空格！" << endl;}else {//生成根结点T = (BiTNode * )malloc(sizeof(BiTNode));if(!T)cout << "内存分配失败！" << endl;T->data = ch;//构造左子树CreateBiTree(T->lchild);//构造右子树CreateBiTree(T->rchild);}}}//输出e的值ElemType PrintElement(ElemType e) { cout << e << " ";return e;}//先序遍历void PreOrderTraverse(BiTree T) { if (T != NULL) {//打印结点的值PrintElement(T->data);//遍历左孩子PreOrderTraverse(T->lchild);//遍历右孩子PreOrderTraverse(T->rchild);}}//中序遍历void InOrderTraverse(BiTree T) {if (T != NULL) {//遍历左孩子InOrderTraverse(T->lchild);//打印结点的值PrintElement(T->data);//遍历右孩子InOrderTraverse(T->rchild);}}//后序遍历void PostOrderTraverse(BiTree T) { if (T != NULL) {//遍历左孩子PostOrderTraverse(T->lchild);//遍历右孩子PostOrderTraverse(T->rchild);//打印结点的值PrintElement(T->data);}}//按任一种遍历次序输出二叉树中的所有结点void TraverseBiTree(BiTree T, int mark) {if(mark == 1) {//先序遍历PreOrderTraverse(T);cout << endl;}else if(mark == 2) {//中序遍历InOrderTraverse(T);cout << endl;}else if(mark == 3) {//后序遍历PostOrderTraverse(T);cout << endl;}else cout << "选择遍历结束！" << endl;}//输入值并执行选择遍历函数void ChoiceMark(BiTree T) {int mark = 1;cout << "请输入，先序遍历为1，中序为2，后序为3，跳过此操作为0：";cin >> mark;if(mark > 0 && mark < 4) {TraverseBiTree(T, mark);ChoiceMark(T);}else cout << "此操作已跳过！" << endl;}//求二叉树的深度int BiTreeDepth(BiTNode *T) {if (T == NULL) {//对于空树，返回0并结束递归return 0;}else {//计算左子树的深度int dep1 = BiTreeDepth(T->lchild);//计算右子树的深度int dep2 = BiTreeDepth(T->rchild);//返回树的深度if(dep1 > dep2)return dep1 + 1;elsereturn dep2 + 1;}}int _tmain(int argc, _TCHAR* argv[]){BiTNode *bt;bt = NULL; //将树根指针置空cout << "输入规则：" << endl<< "要生成新结点，输入一个字符，""不要生成新结点的左孩子，输入一个空格，""左右孩子都不要，输入两个空格，""要结束，输入多个空格（越多越好）,再回车！"<< endl << "按先序输入：";CreateBiTree(bt);cout << "树的深度为：" << BiTreeDepth(bt) << endl;ChoiceMark(bt);return 0;}/*----------------------------------------* 05-2_构造二叉树.cpp -- 构造二叉树的相关操作* 对构造二叉树的每个基本操作都用单独的函数来实现* 水上飘2009年写----------------------------------------*/// ds05-2.cpp : Defines the entry point for the console application.//#include "stdafx.h"#include <iostream>#define STACK_INIT_SIZE 100 //栈的存储空间初始分配量#define STACKINCREMENT 10 //存储空间分配增量typedef char ElemType; //元素类型using namespace std;typedef struct BiTNode {ElemType data; //结点值BiTNode *lchild, *rchild; //左右孩子指针}BiTNode, *BiTree;typedef struct {BiTree *base; //在栈构造之前和销毁之后，base的值为空BiTree *top; //栈顶指针int stacksize; //当前已分配的存储空间，以元素为单位}SqStack;//构造一个空栈void InitStack(SqStack &s) {s.base = (BiTree *)malloc(STACK_INIT_SIZE * sizeof(BiTree));if(!s.base)cout << "存储分配失败！" << endl;s.top = s.base;s.stacksize = STACK_INIT_SIZE;}//插入元素e为新的栈顶元素void Push(SqStack &s, BiTree e) {//栈满，追加存储空间if ((s.top - s.base) >= s.stacksize) {s.base = (BiTree *)malloc((STACK_INIT_SIZE+STACKINCREMENT) * sizeof(BiTree));if(!s.base)cout << "存储分配失败！" << endl;s.top = s.base + s.stacksize;s.stacksize += STACK_INIT_SIZE;}*s.top++ = e;}//若栈不空，则删除s的栈顶元素，并返回其值BiTree Pop(SqStack &s) {if(s.top == s.base)cout << "栈为空，无法删除栈顶元素！" << endl;s.top--;return *s.top;}//按先序输入字符创建二叉树void CreateBiTree(BiTree &T) {char ch;//接受输入的字符ch = cin.get();if(ch == ' ') {//分支结束T = NULL;} //if' 'endelse if(ch == '\n') {cout << "输入未结束前不要输入回车，""要结束分支请输入空格！（接着输入）" << endl;} //if'\n'endelse {//生成根结点T = (BiTNode * )malloc(sizeof(BiTree));if(!T)cout << "内存分配失败！" << endl;T->data = ch;//构造左子树CreateBiTree(T->lchild);//构造右子树CreateBiTree(T->rchild);} //Create end}//输出e的值，并返回ElemType PrintElement(ElemType e) {cout << e << " ";return e;}//中序遍历二叉树的非递归函数void InOrderTraverse(BiTree p, SqStack &S) {cout << "中序遍历结果：";while(S.top != S.base || p != NULL) {if(p != NULL) {Push(S,p);p = p->lchild;} //if NULL endelse {BiTree bi = Pop(S);if(!PrintElement(bi->data))cout << "输出其值未成功！" << endl;p = bi->rchild;} //else end} //while endcout << endl;}int _tmain(int argc, _TCHAR* argv[]){BiTNode *bt;SqStack S;InitStack(S);bt = NULL; //将树根指针置空cout << "老师要求的二叉树序列（‘空’表示空格）：""12空空346空空空5空空，再回车！"<< endl << "请按先序输入一个二叉树序列（可另输入，但要为先序），""无左右孩子则分别输入空格。

数据结构与算法8—⼆叉树的遍历⼆叉树遍历的⼏种⽅法存储结构：typedef char ElemType;typedef struct BiTNode{ElemType data;struct BiTNode *lchild,*rchild;}BiTNode;遍历树的遍历顺序是相对⽗结点来说的。

先序遍历：先访问根结点,然后分别先序遍历左⼦树、右⼦树。

递归先序：void PreOrderTraverse(BiTree bt){ /* 最简单的Visit函数：Visit(ElemType e){printf(e);}*/if(bt){Visit(bt->data);PreOrderTraverse(bt->lchild);PreOrderTraverse(bt->rchild);}}⾮递归先序：1. p=根结点地址，初始化栈2. while(p!=NULL || 栈不空)while(p!=NULL ) 访问p, p⼊栈, p=p->lchild若栈不空，出栈p，p=p->rchildvoid inorder_fdg(BiTNode *bt) /*⾮递归先序遍历*/{ int top=0;BiTNode *p,*s[20]; p=bt;while(p!=NULL||top>0) {while(p!=NULL){printf("%c ",p->data); // 先序遍历s[top++]=p; p=p->lchild;}if(top>0){ p=s[--top];//printf("%c ",p->data); // 中序遍历p=p->rchild;}}}中序遍历：先中序遍历左⼦树，然后访问根结点，最后中序遍历右⼦树。

void InOrderTraverse(BiTree bt){if(bt){PreOrderTraverse(bt->lchild);Visit(bt->data);PreOrderTraverse(bt->rchild);}}后序遍历：先后序遍历左、右⼦树，然后访问根结点。

实现二叉链表存储结构下二叉树的先序遍历的非递归算法要实现二叉链表存储结构下二叉树的先序遍历的非递归算法，可以使用栈来辅助存储节点。

首先，创建一个空栈，并将树的根节点压入栈中。

然后，循环执行以下步骤，直到栈为空：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。

二叉树非递归不用栈遍历算法二叉树非递归不用栈遍历算法在计算机科学中，二叉树是一种非常重要的数据结构。

在实际应用中，对于树的遍历是一项基本操作。

一般来说，二叉树的遍历有三种方式，分别为前序遍历、中序遍历和后序遍历。

在递归方式中，三种遍历方式都可以通过递归完成。

然而，递归的实现方式较为复杂，不易理解。

因此，非递归遍历方法，是广大程序员非常喜欢使用的方法。

在非递归遍历方式中，常见的使用栈数据结构。

但是，在某些特殊情况下，栈空间会失去平衡，从而导致程序崩溃。

因此，一种使用较少的方式被提出，实现树的遍历的非递归方法。

这种方式可以不使用栈数据结构，从而有效地避免栈空间的问题。

此方法又称为 Morris Traversal 算法。

Morris Traversal 算法是通过对树的中序遍历，以及一些特殊处理节点指针的方式来实现的。

该算法将空间复杂度降至 O(1)，并且时间复杂度为 O(N)，其中 N 表示节点的个数。

Morris Traversal 的实现步骤如下：1. 将当前节点设为根节点。

2. 如果节点的左子树不为空，则找到该左子树的最右节点，并将该最右节点的右孩子节点指向当前节点。

此步骤的目的是为了下一次回到该节点，方便访问该节点的右子树。

如果这个右孩子为空，说明该节点已经访问过了，直接打印该节点的值，并将该节点的当前子树赋值为其右子树。

3. 如果节点的左子树为空，在该节点打印自己的值，并以当前节点的右子树节点作为根继续遍历。

4. 重复执行以上步骤，直至遍历所有的节点。

通过以上步骤，我们可以实现二叉树的中序遍历，不用栈数据结构，减少空间的使用，节约内存，更加节约资源。

另外，Morris Traversal 算法还可以用于解决一些其他的问题，如寻找一个无右节点的节点，以及对二叉搜索树的操作等。

综上所述，Morris Traversal 算法是一种非常优秀的二叉树遍历方法，可以降低复杂度，提高代码的执行效率。

二叉树的遍历算法二叉树是一种常用的数据结构，它由节点（node）组成，每个节点最多有两个子节点，分别称为左子节点（left child）和右子节点（right child）。

在二叉树中，我们可以使用不同的遍历算法来访问和操作节点。

常见的二叉树遍历算法有三种，分别是前序遍历（pre-order traversal）、中序遍历（in-order traversal）和后序遍历（post-order traversal）。

下面将详细介绍这三种遍历算法，并给出它们的递归和非递归实现。

一、前序遍历前序遍历的顺序是先访问根节点，然后访问左子树，最后访问右子树。

递归实现：1.如果树为空，则返回。

2.访问当前节点。

3.递归调用前序遍历函数，传入左子树为参数。

4.递归调用前序遍历函数，传入右子树为参数。

非递归实现：1.创建一个空栈，将根节点压入栈。

2.当栈不为空时，执行以下操作：-弹出栈顶节点，并访问该节点。

-如果存在右子树，将右子树压入栈。

-如果存在左子树，将左子树压入栈。

二、中序遍历中序遍历的顺序是先访问左子树，然后访问根节点，最后访问右子树。

递归实现：1.如果树为空，则返回。

2.递归调用中序遍历函数，传入左子树为参数。

3.访问当前节点。

4.递归调用中序遍历函数，传入右子树为参数。

非递归实现：1.创建一个空栈和一个指向当前节点的指针，初始化指向根节点。

2.当栈不为空或当前节点不为空时，执行以下操作：-如果当前节点不为空，将当前节点压入栈，并将当前节点指向其左子树。

-如果当前节点为空，弹出栈顶节点，访问该节点，并将当前节点指向其右子树。

三、后序遍历后序遍历的顺序是先访问左子树，然后访问右子树，最后访问根节点。

递归实现：1.如果树为空，则返回。

2.递归调用后序遍历函数，传入左子树为参数。

3.递归调用后序遍历函数，传入右子树为参数。

4.访问当前节点。

非递归实现：1.创建一个空栈和一个指向当前节点的指针，初始化指向根节点。