1.汉诺塔问题：
void hannoi (int n, char A, char B, char C)
{
if (n == 1)
{
cout << "Move disk " << n << " from " << A << " to " << C << endl;
}
else
{
hannoi (n-1, A, C, B);
cout << "Move disk " << n << " from " << A << " to " << C << endl;
hannoi (n-1, B, A, C);
}
}
2.二叉树的三种遍历：
(1)先序遍历
Status PreOrderTraverse (BiTree &T){
if (T){
std::cout<< T->data <<std::endl;
PreOrderTraverse (T->lchild);
PreOrderTraverse (T->rchild);
}
else return OK;
}
(2)中序遍历
Status InOrderTraverse (BiTree &T){
if (T){
InOrderTraverse (T->lchilde);
std::cout<< T->data <<std::endl;
InOrderTraverse (T->rchild);
}
else return OK;
}
(3)后序遍历
Status PostOrderTraverse (BiTree &T){
if (T){
PostOrderTraverse (T->lchild);
PostOrderTraverse (T->rchild);
std::cout<< T->data <<std::endl;
}
else return OK;
}
个人总结：感觉递归算法是非常强大的工具，尤其用在汉诺塔，树的遍历等，这样涉及大量重复性操作的问题求解中。
比如汉诺塔问题，要想将n个盘子由A移动到C，则先将前n-1个移动到B，然后再把第n个盘子由A移动到C，然后再把剩下的盘子由B移动到C。用了递归算法，只需重复调用算法即可，将负责的问题简单化。
再比如以上的三种二叉树的遍历操作，先序遍历，必定是先遍历根节点，然后遍历根的左子树，再遍历根的右子树。中序遍历，则是先遍历根的左子树，再遍历根节点，再遍历根的右子树，而在遍历左子树的过程中，将左子树当做一个单独的树，也按照先遍历左子树，根，右子树的顺序遍历，这样层次遍历下去，完成递归，在遍历左右子树的过程中不断又调用了递归方法。可以说是很好很强大的算法。
但以上四个算法，其实都还有可以改进的地方，那就是遍历过程所涉及的操作，以上四个算法就单纯的把它写死了，就是简单的输出，这样的弊端是：比如某天想要在遍历二叉树的过程中，将原来的值输出后，把原来的值加1，那么就不得不更改三个遍历算法，每个算法都要做改动，这样其实程序的可扩展性很差劲。所以最好的方法是，在遍历的时候，指定访问函数，通过访问函数对元素值就行处理:输出，更改，删除等等，这样某天想在遍历的时候，附加某些操作的时候，只需将其绑定的访问函数做更改即可即可，其他代码不需要再变动。
改动过后的以上四个算法如下所示：
1'汉诺塔问题
int i = 0;
void Move (char x, int k, char z){
std::cout << "The "<< ++i <<" step : Move " << k <<" from "<< x <<" to " << z <<std::endl;
}
void Hanoi (int n, char x, char y, char z)
{
if (1 == n){
Move (x, n, z);
}
else{
Hanoi (n-1, x, z, y);
Move (x, n, z);
Hanoi (n-1, y, x, z);
}
}
这样通过加入一个Move方法，在遍历的过程中对元素进行处理，增加了可扩展性。
如果要移动n个盘子，则总共需要2^n - 1步。
2'二叉树的先序遍历
void PrintElemType (TElemType e){
std::cout<< e <<std::endl;
}
Status PreOrderTraverse (BiTree &T. void (*Visit) (TElemType e)){
if (T){
Visit (T->data);
PreOrderTraverse (T->lchild, Visit);
PreOrderTraverse (T->rchild, Visit);
}
else return OK;
}
这样通过加入visit访问函数，使得后续遍历时想对元素做附加操作的话，只需通过更改特定的绑定函数就可以方便的完成。
另外这里用到的指针函数是一个非常差方便的概念，在NS3里面大量用到，需要注意。
3'二叉树的中序遍历
Status InOrderTraverse (BiTree &T, void (*Visit)(TElemType e)){
if (T){
InOrderTraverse (T->lchild, Visit);
Visit (T->data);
InOrderTraverse (T->rchild, Visit);
}else return OK;
}
4'二叉树的后序遍历
Status PostOrderTraverse (BiTree &T, void (*Visit)(TElemType e)){
if (T){
PostOrderTraverse (T->lchild, Visit);
PostOrderTraverse (T->rchild, Visit);
Visit (T->data);
}else return OK;
}
5''二叉树中序非递归遍历:递归遍历和非递归遍历的根本区别在于，递归时系统替你管理栈，非递归要自己管理。
typedef struct{
BiTree *base;
BiTree *top;
int stacksize;
}SqStack;
Status InitSqStack (SqStack &S){
S.base = (BiTree *) malloc (sizeof (BiTree) * STACK_INIT_SIZE);
if (!S.base) exit (OVERFLOW);
S.top = S.base;
S.stacksize = STACK_INIT_SIZE;
return OK;
}
bool IsStackEmpty (SqStack &S){
if (S.base == S.top) return true;
return false;
}
Status GetTop (SqStack &S, BiTree &e){
if (S.top == S.base) return ERROR;
e = *(S.top - 1);
return OK;
}
Status Pop (SqStack &S, BiTree &e){
if (S.top == S.base) return ERROR;
e = *--S.top;
return OK;
}
Status Push (SqStack &S, BiTree &e){
if (S.top >= S.base + STACK_INIT_SIZE){
S.base = (BiTree *) realloc (sizeof (BiTree) * (STACK_INIT_SIZE + STACK_INCREMENT));
if (!S.base) exit (OVERFLOW);
S.top = S.base + STACK_INIT_SIZE;
S.stacksize += STACK_INCREMENT;
}
*S.top++ = e;
return OK;
}
//中序遍历二叉树，非递归的第一种方法。
Status InOrderTraverseNonRecursion (BiTree &T, void (*Visit) (TElemType e)){
InitSqStack (S);
Push (S, T);
BiTree p;
while (!StackEmpty(S)){
while (GetTop (S, p) && p) Push (S, p->lchild);//入栈前不做检查，最后会入栈一个空指针
Pop (S, p);
if (!StackEmpty (S)){
Pop (S, p);
Visit (p->data);
Push (S, p->rchild);
}//if
}//while
return OK;
}
//中序遍历二叉树，非递归的第二种方法。
Status InOrderTraverseNonRecursion2 (BiTree &T, void (*Visit) (TElemType e)){
SqStack S;
InitSqStack (S);
BiTree p = T;
while (p || !StackEmpty (S)){
if (p) {//在入栈前先做检查，如果为空，表明已经到头。
Push (S, p);
p = p->lchild;
}
else {
Pop (S, p);
Visit (p->data);
p = p->rchild;
}
}//while
return OK;
}
比较以上两种中序遍历二叉树的非递归方法：
1.第一种，在将遍历指针入栈前不做检查，直接入栈，所以会出现将最后空指针加入到栈的情况。
2.第二种，在将遍历指针入栈前作检查，如果为空，表明已经到头，所以不会把空指针入栈。
3.第一种，在遍历右子树的时候，将右子树入栈Push (S, p->rchild);然后再返回while循环，继续遍历，指针入栈
4.第二种，p = p->rchild;然后返回while循环，继续判断p指针，以此来遍历右子树
除了这两点，其余的情况基本一样。
6.二叉树的先序非递归算法：
Status PreOrderTraverseNonRecursion (BiTree &T, void (*Visit) (TElemType e)){
if (!T) return ;
SqStack S;
InitSqStack (S);
Push (S, T);
BiTree p ;
while (!StackEmpty (S)){
Pop (S, p);
Visit (p->data);
if (p->rchild){
Push (S, p->rchild);
}
if (p->lchild){
Push (S, p->lchild);
}
}
return OK;
}
先序非递归遍历二叉树需要注意的是：栈不空的时候，出栈，访问出栈节点的数据，然后如果左子树和右子树不空，分别入栈，在入栈的时候，先入栈右子树，后入栈左子树，这样保证在出栈是，左子树先出。
同样的，和前序递归遍历的区别在于：非递归的时候自己管理栈，而递归的时候，操作系统替你管理栈。
7.二叉树的后序非递归算法：
Status PostTraverseNonRecursion (BiTree &T, void (*Visit) (TElemType e)){
SqStack S;
InitSqStack (S);
BiTree p = T;
BiTree previsited = NULL;
while (p || !StackEmpty (S)){
while (p) {
Push (S, p);
p = p->lchild;
}
GetTop (S, p);
if (p->rchild == NULL || p->rchild == previsited){
Pop (S, p);
Visit (p->data);
previsited = p;
p = NULL;
}
else{
p = p->rchild;
}
}
return OK;
}
二叉树的后续非递归遍历，核心在于，当一个节点的右子树为空，或者右子树已经访问过了的时候，才访问该节点，在访问该节点的同时，要同时做好三件事：
1.出栈当前节点（已经访问过了，必须出栈） Pop(S, p)
2.将前一个访问的指针指向该节点
3.当前指针指向空，为下一次循环的出栈做好准备。
如果右子树尚未被访问过，则转到右子树，继续入栈，找最左下边要被访问的第一个元素。
-------------------------------扩展：二叉树的线索化和线索二叉树的遍历------------------------------------------
不管是递归还是非递归，二叉树的遍历，都是讲二叉树线性化进行遍历。除了第一个和最后一个节点之外，每个节点都有一个直接前驱和一个直接后继，所以二叉树的前序、中序、后序都是将二叉树先序、中序、后序线性化。
同时考虑到，在含有n个节点的二叉树中，空链域有n+1个，所以考虑将这n+1个链利用起来存储线索。（n+1的由来：n个节点，总共的链域有2n个。又因为n=所有分支数+1=B+1=n1+2n2+1，即n=n1+2n2+1，在这2n个链域中，使用了的有：n1+2n2 = n—1个，所以剩余的链域有2n-(n-1) = n+1个）
先来看二叉树的线索化，线索化，就是在遍历的过程中修改空域的指针，使其成为指向前驱和后继的线索。
以中序遍历线索化为例子。
void InThreading (BiThrTree p){//p--指向以p为根的树
if (p){
InThreading (p->lchild);//先找到最左边的节点。
if (!p->lchild) {//前驱线索
p->LTag = Thread;
p->lchild = pre;
}
if (!pre->rchild){//后继线索
pre->RTag = Thread;
pre->rchild = p;
}
pre = p;
InThreading (p->rchild)
}
}
//中序遍历二叉树T，并将其中序线索化，Thrt指向头结点。
Status InOrderThreading (BiThrTree &Thrt; BiThrTree T){
if (!(Thrt = (BiThrTree) malloc (sizeof (BiThrNode)))) exit(OVERFLOW);
Thrt->LTag = Link;
Thrt->RTag = Thread;
Thrt->rchild = Thrt; //右指针回指。
if (!T) Thrt->lchild = Thrt;
else {
Thrt->lchild = T;
pre = Thrt;
InThreading (T); //线索化空链域，pre指向刚刚访问过的节点
pre->RTag = Thread;//线索化最后一个节点
pre->rchild = Thrt;
Thrt->rchild = pre;
}
return OK;
}
以上是二叉树中序线索化的过程算法。下面来看如何遍历中序线索二叉树。
//T指向头节点，头节点的左链lchild指向根节点
Status InOrderTraverse_Thr (BiThrTree T, void (*Visit) (TElemType e)){
BiThrTree p = T->lchild;
while (p != T){//空树或者遍历结束时，p==T
while (p->LTag == Link) p = p->lchild; //找到最左边的节点
Visit (p->data);
while (p->RTag == Thread && p->rchild != T){
p = p->rchild;
Visit (p->data);
}
p = p->rchild;
}
return OK;
}
最后给出二叉线索树的数据结构表示:
typedef enum PointTag {Link, Thread};
typedef struct BiThrNode{
TElemType data;
struct BiThrNode *lchild;
struct BiThrNode *rchild;
PointTag LTag;
PointTag RTag;
}BiThrNode, *BiThrTree;
相关推荐
利用二叉树法，实现汉诺塔的非递归，根据盘子数和第几步，快速得到每一步移动的操作，速度快，省内存。已经经过调试运行，算法思想参见http://wenku.baidu.com/view/81a05a80e53a580216fcfeba.html，本人源码是根据...
递归的应用有很多，常见的包括：阶乘运算、斐波那契数列、汉诺塔、数的遍历，还有大名鼎鼎的快排等等。理论上，递归问题都可以由多层循环来实现。递归的每次调用都会消耗一定的栈空间，效率要稍低于循环实现，但递归...
汉诺塔非递归算法 用栈作为辅助存储结构 和数据结构中中序遍历二叉树的方法类似
汉诺塔的非递归实现，以及用二叉树实现
数据结构用栈实现汉诺塔，用递归给你讲吧，先想这个棵树Tn，先把最下面的n要搬走，就得把上面的n－1个先搬走，这个n－1个也形成一个树T(n－1),然后又把这n－1个搬到n上面又形成一个T(n－1)的树，这个你就可以画出来...
7.3.1 栈的应用—递归算法（汉诺塔）演示 7.3.2 双链表创建演示 7.3.3 冒泡排序演示 7.3.4 基数排序演示 7.3.5 二分查找演示 7.3.6 二叉树遍历演示 案例八 进程调度 案例九 存储管理分区分配算法 案例十 通讯录 案例...
用c#gdi演绎汉诺塔递归实现过程，可由程序自动演绎，也可由用户手动拖动来实现。
07-008习题课：广义表的存储、递归算法、汉诺塔问题、二叉树的基本操作 07-009习题课：图的简单路径、深度优先遍历图的非递归算法等 09-001顺序表的查找、有序表的查找、二分查找 09-002顺序表的查找与有序表的查找...
汉诺塔的非递归 回朔法一例 几道有趣的算法题 阶梯问题的递归解法 精确迭代法 矩阵求逆的快速算法 快 速 排 序 马踏棋盘问题 冒 泡 法 排序算法 五例 排序算法一览 穷举密码算法 如何实现DES算法 入栈与出栈的所有...
汉诺塔的非递归 回朔法一例 几道有趣的算法题 阶梯问题的递归解法 精确迭代法 矩阵求逆的快速算法 快 速 排 序 马踏棋盘问题 冒 泡 法 排序算法 五例 排序算法一览 穷举密码算法 如何实现DES算法 入栈与出栈的所有...
8.5.2 汉诺塔 8.5.3 列车车厢重排 8.5.4 开关盒布线 8.5.5 离线等价类问题 8.5.6 迷宫老鼠 8.6 参考及推荐读物 第9章 队列 9.1 定义和应用 9.2 抽象数据类型 9.3 数组描述 9.3.1 描述 9.3.2 类arrayQueue 9.4 链表...
7.2.3 汉诺塔 7.2.4 帕斯卡三角形（杨辉三角） 8 二叉树 8.1 基本概念 8.2 代码实现 8.3 说明 8.4 应用 9 二叉搜索树 9.1 基本概念 9.2 代码实现 9.3 说明 10 AVL树 10.1 基本概念 10.1.1 AVL树是什么...
7.2.3 汉诺塔 7.2.4 帕斯卡三角形（杨辉三角） 8 二叉树 8.1 基本概念 8.2 代码实现 8.3 说明 8.4 应用 9 二叉搜索树 9.1 基本概念 9.2 代码实现 9.3 说明 10 AVL树 10.1 基本概念 10.1.1 AVL树...
6 队列 6.1 基本概念 6.2 代码实现 6.3 应用 7 递归 7.1 基本概念 7.2 应用 7.2.1 阶乘 7.2.2 斐波那契数列 7.2.3 汉诺塔 7.2.4 帕斯卡三角形（杨辉三角） 8 二叉树 8.1 基本概念 8.2 代码实现 8.3 说明 8.4 应用 9 ...
3、（选做题）采用递归和非递归方法求解汉诺塔问题，问题描述如下： 有三根柱子A、B、C，在柱子A上从下向上有n个从大到小的圆盘，在柱子B和C上没有圆盘，现需将柱子A上的所有圆盘移到柱子C上，可以借助柱子B，要求...
算法演示屏由显示顺序表或链表的图示、算法文本及变量等三个窗口组成。在演示算法之前，需先在弹出的小窗口中输入线性表的数据元素及算法参数 i（插入或删除的位置）和 b（被插的数据元素）的值。顺序表的图示窗口...
汉诺(Hanoi)塔问题 归并排序 消除递归 一些有趣的递归应用 小结 问题 实验 编程作业 第7章 高级排序 希尔排序 划分 快速排序 基数排序 小结 问题 实验 编程作业 第8章 二叉树 为什么使用二叉树? ...
汉诺塔2.txt 灯塔问题.txt 猴子和桃.txt 百鸡百钱.txt 矩阵乘法动态规划.txt 矩阵转换.txt 硬币分法.txt 神经元模型.txt 穷举搜索法.txt 符号图形.txt 简单数据库.txt 简单计算器.txt 简单逆阵.txt ...
汉诺(Hanoi)塔问题 归并排序 消除递归 一些有趣的递归应用 小结 问题 实验 编程作业 第7章 高级排序 希尔排序 划分 快速排序 基数排序 小结 问题 实验 编程作业 第8章 二叉树 为什么使用二叉树？ 树的术语 一个...
用非递归解决汉诺塔问题 采用二叉树查找的方法 made by a___9