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;
相关推荐
1. **代码调整**：将汉诺塔算法和二叉树中序遍历的代码进行调整，使得二者在逻辑结构和算法步骤方面尽可能一致，以便于学生理解。 2. **虚拟指针**：使用一个虚拟指针来指向汉诺塔状态树中的当前节点，与二叉树遍历...
在这个"汉诺塔和二叉树演示"程序中，可能包含了对这两个概念的可视化展示，帮助用户更好地理解它们的运作机制。通过动态的图形界面，用户可以观察到汉诺塔的移动过程以及二叉树节点的添加、删除和搜索操作。这对于...
这些遍历方式通过动画形式呈现，可以让用户直观地看到每一步的执行顺序，加深对二叉树操作的理解。 此外，程序可能还展示了二叉树的查找过程，比如二分查找法。在有序的二叉搜索树中，查找某个特定元素的效率很高，...
在本项目中，我们探讨了几个经典的数据结构问题及其实现，包括汉诺塔问题、逆阵问题、硬币情况、二叉树的实现以及图的遍历。 1. **汉诺塔问题**：这是一个经典的递归问题，源自印度传说。目标是将一个柱子上的所有...
利用二叉树法，实现汉诺塔的非递归，根据盘子数和第几步，快速得到每一步移动的操作，速度快，省内存。已经经过调试运行，算法思想参见http://wenku.baidu.com/view/81a05a80e53a580216fcfeba.html，本人源码是根据...
这个非递归算法与中序遍历二叉树的方法有相似之处，因为它们都涉及到对元素的有序访问。在中序遍历中，我们同样使用栈来模拟左子树的深度优先搜索，然后访问根节点，最后处理右子树。在这里，我们用栈来模拟递归调用...
递归的应用有很多，常见的包括：阶乘运算、斐波那契数列、汉诺塔、数的遍历，还有大名鼎鼎的快排等等。理论上，递归问题都可以由多层循环来实现。递归的每次调用都会消耗一定的栈空间，效率要稍低于循环实现，但递归...
### 递归问题的二叉树求解方法详解 #### 引言 递归作为一种强大的编程...汉诺塔问题作为递归的典型案例，通过构建相应的二叉树模型，能够直观展现递归调用的执行流程，为深入研究和应用递归技术提供了有力的工具。
汉诺塔问题是一种经典的递归算法示例，在计算机科学领域被广泛应用于教授递归思想和技术。传统解决汉诺塔问题的方法通常采用递归算法，尽管这种方法结构清晰易懂，但由于递归过程中需要频繁地调用自身并利用系统栈来...
下面我们将详细探讨非递归实现汉诺塔的两种常见方法：基于栈的迭代和二叉树实现。 ### 基于栈的迭代实现 在这个实现中，我们创建两个栈，分别代表辅助柱子和目标柱子。主栈用于存储当前操作的状态。我们维护三个...
二叉树的遍历是计算机科学中数据结构领域的一个重要概念，主要应用于树形结构的深度优先搜索（DFS）和广度优先搜索（BFS）。在这个主题中，我们将重点讨论在二叉树中常见的三种遍历方法：前序遍历、中序遍历和后序...
本文提出了一种新的汉诺塔问题解模型，通过对满二叉树模型的应用，找到了每一个圆盘移动的具体规律，并据此设计了一个高效、占用额外存储空间为零的非递归算法。这种方法不仅简化了解决汉诺塔问题的过程，也为进一步...
递归算法的应用非常广泛，例如二叉树遍历、皇后问题、汉诺塔问题等经典非数值的求解。 函数递归算法的特征是每次调用后都必然使得原始问题规模缩小，并且子问题与原始问题相似。例如，在计算正整数m的阶乘m!时，...
不同于传统意义上的二叉树应用，该算法巧妙地利用满二叉树的概念来组织和分析Hanoi塔问题的解，从而设计出一种高效、易于理解和实现的非递归方案。 #### 四、非递归算法的设计思路 在深入分析Hanoi塔问题递归解的...
汉诺塔（Hanoi Tower）算法，又称为巴黎塔问题，是计算机科学中一个经典的递归问题。这个算法源于一个古老的印度传说，涉及到三个柱子和一堆大小不一的圆盘。目标是将所有圆盘从一个柱子移动到另一个柱子，每次只能...
本文将深入探讨C#中的数据结构，特别是排序、栈与栈的应用、树和二叉树以及递归等核心概念，并通过实例来加深理解。 首先，我们来看排序。排序是计算机科学中最基本的操作之一，它涉及到对一组数据按照特定顺序进行...
1. **汉诺塔**：这是一个经典的递归问题，目标是将一座塔上的所有圆盘从一个柱子移动到另一个柱子，遵循以下规则：每次只能移动一个圆盘，且任何时候大盘子都不能位于小盘子之上。通过递归算法，我们可以计算出最少...
数据结构用栈实现汉诺塔，用递归给你讲吧，先想这个棵树Tn，先把最下面的n要搬走，就得把上面的n－1个先搬走，这个n－1个也形成一个树T(n－1),然后又把这n－1个搬到n上面又形成一个T(n－1)的树，这个你就可以画出来...
在学习汉诺塔问题时，可以深入理解递归的思想，掌握如何设计和分析递归函数，这对于进一步学习其他复杂的算法如快速排序、二叉树遍历等至关重要。同时，它也能帮助我们锻炼逻辑思维和问题解决能力，这对任何IT从业者...