二叉树先序遍历递归算法和非递归算法本质区别?
#include // malloc()等
#include // 标准输入输出头文件,包括EOF(=^Z或F6),NULL等
#include // atoi(),exit()
#include // 数学函数头文件,包括floor(),ceil(),abs()等
#define ClearBiTree DestroyBiTree // 清空二叉树和销毁二叉树的操作一样
typedef struct BiTNode
{
int data; // 结点的值
BiTNode *lchild,*rchild; // 左右孩子指针
}BiTNode,*BiTree;
int Nil=0; // 设整型以0为空
void visit(int e)
{ printf("%d ",e); // 以整型格式输出
}
void InitBiTree(BiTree &T)
{ // 操作结果:构造空二叉树T
T=NULL;
}
void CreateBiTree(BiTree &T)
{ // 算法6.4:按先序次序输入二叉树中结点的值(可为字符型或整型,在主程中定义),
// 构造二叉链表表示的二叉树T。变量Nil表示空(子)树。修改
int number;
scanf("%d",&number); // 输入结点的值
if(number==Nil) // 结点的值为空
T=NULL;
else // 结点的值不为空
{ T=(BiTree)malloc(sizeof(BiTNode)); // 生成根结点
if(!T)
exit(OVERFLOW);
T->data=number; // 将值赋给T所指结点
CreateBiTree(T->lchild); // 递归构造左子树
CreateBiTree(T->rchild); // 递归构造右子树
}
}
void DestroyBiTree(BiTree &T)
{ // 初始条件:二叉树T存在。操作结果:销毁二叉树T
if(T) // 非空树
{ DestroyBiTree(T->lchild); // 递归销毁左子树,如无左子树,则不执行任何操作
DestroyBiTree(T->rchild); // 递归销毁右子树,如无右子树,则不执行任何操作
free(T); // 释放根结点
T=NULL; // 空指针赋0
}
}
void PreOrderTraverse(BiTree T,void(*Visit)(int))
{ // 初始条件:二叉树T存在,Visit是对结点操作的应用函数。修改算法6.1
// 操作结果:先序递归遍历T,对每个结点调用函数Visit一次且仅一次
if(T) // T不空
{ Visit(T->data); // 先访问根结点
PreOrderTraverse(T->lchild,Visit); // 再先序遍历左子树
PreOrderTraverse(T->rchild,Visit); // 最后先序遍历右子树
}
}
void InOrderTraverse(BiTree T,void(*Visit)(int))
{ // 初始条件:二叉树T存在,Visit是对结点操作的应用函数
// 操作结果:中序递归遍历T,对每个结点调用函数Visit一次且仅一次
if(T)
{ InOrderTraverse(T->lchild,Visit); // 先中序遍历左子树
Visit(T->data); // 再访问根结点
InOrderTraverse(T->rchild,Visit); // 最后中序遍历右子树
}
}
void PostOrderTraverse(BiTree T,void(*Visit)(int))
{ // 初始条件:二叉树T存在,Visit是对结点操作的应用函数
// 操作结果:后序递归遍历T,对每个结点调用函数Visit一次且仅一次
if(T) // T不空
{ PostOrderTraverse(T->lchild,Visit); // 先后序遍历左子树
PostOrderTraverse(T->rchild,Visit); // 再后序遍历右子树
Visit(T->data); // 最后访问根结点
}
}
void main()
{
BiTree T;
InitBiTree(T); // 初始化二叉树T
printf("按先序次序输入二叉树中结点的值,输入0表示节点为空,输入范例:1 2 0 0 3 0 0
");
CreateBiTree(T); // 建立二叉树T
printf("先序递归遍历二叉树:
");
PreOrderTraverse(T,visit); // 先序递归遍历二叉树T
printf("
中序递归遍历二叉树:
");
InOrderTraverse(T,visit); // 中序递归遍历二叉树T
printf("
后序递归遍历二叉树:
");
PostOrderTraverse(T,visit); // 后序递归遍历二叉树T
}
我们的数据结构实验也是这题,需要我把我的实验报告给你参考下么!
我这里就只发这部分的代码。
Status PreOrderTraverse(BiTree T)
{
//先序遍历二叉树T的递归算法
if (T)
{
printf("%d ",T->data);
if(T->lchild) PreOrderTraverse(T->lchild);
if(T->rchild) PreOrderTraverse(T->rchild);
return FALSE;
}
elsereturn OK;
}
Status PreOrder(BiTree T)
{
//先序遍历二叉树T的非递归算法
while(!(T==NULL&&top==NULL))
{
if(T)
{
printf("%d ",T->data);
push(T);
T=T->lchild;
}
else
{
T=(BiTree)pop();
T=T->rchild;
}
}
}
Status InOrderTraverse(BiTree T)
{
//中序遍历二叉树T的递归算法
if (T)
{
if (T->lchild) InOrderTraverse(T->lchild);
printf("%d ",T->data);
if (T->rchild) InOrderTraverse(T->rchild);
return FALSE;
}
else return OK;
}
Status InOrder(BiTree T)
{
//中序遍历二叉树T的非递归算法
while(!(T==NULL&&top==NULL))
{
while(T)
{
push(T);
T=T->lchild;
}
T=(BiTree)pop();
printf("%d ",T->data);
T=T->rchild;
}
}
Status PostOrderTraverse(BiTree T)
{
//后序遍历二叉树T的递归算法
if (T)
{
if (T->lchild) PostOrderTraverse(T->lchild);
if (T->rchild) PostOrderTraverse(T->rchild);
printf("%d ",T->data);
return FALSE;
}
else return OK;
}
Status PostOrder(BiTree T)
{
//后序遍历二叉树T的递归算法
unsigned sign;//记录结点从栈中弹出的次数
while(!(T==NULL&&top==NULL))
{
if(T)
{
push(T);//第一次遇到结点T时压入其指针
push(1);//置标志为1
T=T->lchild;
}
else
{
while(top)
{
sign=pop();
T=(BiTree)pop();
if(1==sign)//表示走过T的左子树
{
push(T);
push(2);
T=T->rchild;
break;
}
else
{
if(2==sign)//表示T的左右子树都已走过
{
printf("%d ",T->data);
T=NULL;
}
}
}
}
}
}
在先序遍历中,对节点的访问工作是在它的左右儿子被访问之前进行的。换言之,先序遍历访问节点的顺序是根节点-左儿子-右儿子。由于树可以通过递归来定义,所以树的常见操作用递归实现常常是方便清晰的。递归实现的代码如下:
void PreOrderTraversal(BinTree BT)
{
if( BT )
{
printf(“%d\n”, BT->Data); //对节点做些访问比如打印
PreOrderTraversal(BT->Left); //访问左儿子
PreOrderTraversal(BT->Right); //访问右儿子
}
}
由递归代码可以看出,该递归为尾递归(尾递归即递归形式在函数末尾或者说在函数即将返回前)。尾递归的递归调用需要用栈存储调用的信息,当数据规模较大时容易越出栈空间。虽然现在大部分的编译器能够自动去除尾递归,但是即使如此,我们不妨自己去除。非递归先序遍历算法基本思路:使用堆栈
a. 遇到一个节点,访问它,然后把它压栈,并去遍历它的左子树;
b. 当左子树遍历结束后,从栈顶弹出该节点并将其指向右儿子,继续a步骤;
c. 当所有节点访问完即最后访问的树节点为空且栈空时,停止。
实现代码如下:
void PreOrderTraversal(BinTree BT)
{
BinTree T = BT;
Stack S = CreatStack(MAX_SIZE); //创建并初始化堆栈S
while(T || !IsEmpty(S))
{
while(T) //一直向左并将沿途节点访问(打印)后压入堆栈
{
printf("%d\n", T->Data);
Push(S, T);
T = T->Left;
}
if (!IsEmpty(S))
{
T = Pop(S); //节点弹出堆栈
T = T->Right; //转向右子树
}
}
}
由以上例子可以看出,递归与非递归的本质区别就是递归是不断循环调用同一过程,非递归是循环执行同一个动作,并且非递归有入栈与出栈的过程,因此更节省存储空间。个人浅见,欢迎指正。
在前面一文,说过二叉树的递归遍历算法(二叉树先根(先序)遍历的改进),此文主要讲二叉树的非递归算法,采用栈结构
总结先根遍历得到的非递归算法思想如下:
1)入栈,主要是先头结点入栈,然后visit此结点
2)while,循环遍历当前结点,直至左孩子没有结点
3)if结点的右孩子为真,转入1)继续遍历,否则退出当前结点转入父母结点遍历转入1)
先看符合此思想的算法:
[cpp] view plain copy print?
int PreOrderTraverseNonRecursiveEx(const BiTree &T, int (*VisitNode)(TElemType data))
{
if (T == NULL)
{
return -1;
}
BiTNode *pBiNode = T;
SqStack S;
InitStack(&S);
Push(&S, (SElemType)T);
while (!IsStackEmpty(S))
{
while (pBiNode)
{
VisitNode(pBiNode->data);
if (pBiNode != T)
{
Push(&S, (SElemType)pBiNode);
}
pBiNode = pBiNode->lchild;
}
if(pBiNode == NULL)
{
Pop(&S, (SElemType*)&pBiNode);
}
if ( pBiNode->rchild == NULL)
{
Pop(&S, (SElemType*)&pBiNode); //如果此时栈已空,就有问题
}
pBiNode = pBiNode->rchild;
}
return 0;
}
1+二叉树先序、中序、后序遍历的递归算法的最坏和最好空间复杂度分别为...
先序遍历的递归算法的最坏和最好空间复杂度均为O(n),其中n是二叉树中节点的数量。无论二叉树的形状如何,递归调用栈的深度都将达到n,因此空间复杂度为O(n)。即使二叉树是完全平衡的,也无法降低空间复杂度,因为递归调用栈的深度仍然是n。中序遍历的递归算法的最坏和最好空间复杂度也是O(n)...
干货|二叉树的前序遍历、中序遍历、后序遍历。(递归和非递归)
二叉树的遍历方式包括前序、中序和后序三种。这三种遍历方法在数据结构中起着至关重要的作用。对于树的遍历,递归和非递归是两种常见的实现方式。前序遍历按照“根结点-左孩子-右孩子”的顺序访问节点。在递归实现中,首先访问根节点,然后分别递归地访问左子树和右子树。对于非递归实现,我们使用栈来模...
怎么用递归算法遍历二叉树的前序序列?
先序列号为这个,那么在编辑的时候,可以先进行用顺序的方式,然后再进行。后序序列是CBA。根据前序,可以确定A为根,A在中序中的位置,可以确定CB为A的左子树上的结点,没有右子树。确定A之后,再看中序第二值为B,查看B在中序中的位置,C在B左边,确定C为B的左子树。
用递归算法先序中序后序遍历二叉树
1、先序 void PreOrderTraversal(BinTree BT){ if( BT ){ printf(“%d\\n”, BT->Data); \/\/对节点做些访问比如打印 PreOrderTraversal(BT->Left); \/\/访问左儿子 PreOrderTraversal(BT->Right); \/\/访问右儿子 } } 2、中序 void InOrderTraversal(BinTree BT){ if(BT){ InOrde...
先序遍历二叉树的递归算法怎样理解?
于是对二叉树的遍历问题就被抽象成三个基本步骤:1、访问根结点。2、访问该点的所有左子树。3、访问该点的所有右子树。先序遍历的策略是按123的步骤执行,中序是按213来,后序则是231,它们之间的不同只是“访问根结点”在这三个步骤中的位置。看着你刚画好的那个BitTree跟着我的思路走。在先序遍...
二叉树先序遍历递归算法和非递归算法本质区别?
1. 先序遍历 在先序遍历中,对节点的访问工作是在它的左右儿子被访问之前进行的。换言之,先序遍历访问节点的顺序是根节点-左儿子-右儿子。由于树可以通过递归来定义,所以树的常见操作用递归实现常常是方便清晰的。递归实现的代码如下:void PreOrderTraversal(BinTree BT){ if( BT ){ printf(“%d...
先序遍历和后序遍历是什么
前序遍历。二、后序遍历 1、后序遍历是二叉树遍历的一种,有递归算法和非递归算法两种。在二叉树中,先左后右再根;2、后序遍历首先遍历左子树,然后遍历右子树,最后访问根结点,在遍历左、右子树时,仍然先遍历左子树,然后遍历右子树,最后遍历根结点;3、也称做后根遍历、后序周游。
先序遍历二叉树的递归算法怎样理解???(严蔚敏主编)
更要注意的是,先序调用的递归函数还没执行完,在先序调用的最里层,要执行这个函数的最后一个语句,即先序访问右子树。在了解递归函数时,要注意函数是一层一层执行的,把没有调用的函数看作哦是第一层,第一次调用的时候,,势必会第二次遇到调用函数,变成第二层,,,...
求C语言版数据结构二叉树的先序遍历递归算法,不要伪码,要求能实现能运...
K&R中的一个实现,可以读取数字,插入二叉树,并且统计出现次数。最后输出,这里假设只读取正数,自己可以改getword函数 include<stdio.h>#include<stdlib.h>#include<string.h>#include<ctype.h> #define MAXLINE 100 struct num { int number; int count; struct num *left; struct ...
如何判断二叉树的先序遍历、中序遍历和后序遍历?
1、先根遍历一般是先序遍历(Pre-order),按照根左右的顺序沿一定路径经过路径上所有的结点。在二叉树中,先根后左再右。巧记:根左右。首先访问根结点然后遍历左子树,最后遍历右子树。在遍历左、右子树时,仍然先访问根结点,然后遍历左子树,最后遍历右子树,如果二叉树为空则返回。例如,下图所示...
唐佩安奇: 在前面一文,说过二叉树的递归遍历算法(二叉树先根(先序)遍历的改进),此文主要讲二叉树的非递归算法,采用栈结构 总结先根遍历得到的非递归算法思想如下: 1)入栈,主要是先头结点入栈,然后visit此结点 2)while,循环遍历当前结...
伊吾县18522803878: 二叉树遍历程序 - ?
唐佩安奇: 二叉树的遍历有3种方式: a/ \/ \b e/ \ \/ \ \c d f(先序)先根遍历:(根左右)先访问根,再访问左子树,最后访问右子树,则可得如下的序列:abcdef(中序)中根遍历:(左根右)先访问左子树,再访问根,最后访问右子树,则可得...
伊吾县18522803878: 二叉树的非递归遍历?要有讲解 不要纯程序~!! - ?
唐佩安奇: 我尽量写得详细一点,你再回去自己举个例子应该就容易明白了,这个遍历采用的是中序遍历. struct node{int data;struct node *lchild;struct node *rchild;}/*定义结点,lchild和rchild分别为左右孩子*/ void inorder(struct node *T) {struct node ...
伊吾县18522803878: 用JAVA语言实现二叉树的层次遍历的非递归算法及查找算法. - ?
唐佩安奇: 先序非递归算法 【思路】 假设:T是要遍历树的根指针,若T != NULL 对于非递归算法,引入栈模拟递归工作栈,初始时栈为空. 问题:如何用栈来保存信息,使得在先序遍历过左子树后,能利用栈顶信息获取T的右子树的根指针? 方法1:访...
伊吾县18522803878: 非递归的二叉树前序遍历算法有什么用途 - ?
唐佩安奇: 1. 递归和非递归只是解决问题的方法的不同,本质还是一样的. 2. 递归算法相对于非递归算法来说效率通常都会更低 2.1 递归算法会有更多的资源需要压栈和出栈操作(不仅仅是参数,还有函数地址等) 2.2 由于编译器对附加的一些栈保护机制会导致递归执行的更加低效 3. 使用循环代替递归算法,通常可以获得更好的执行效率和空间效率,在二叉树层次较深的情况下,采用非递归方式遍历能够有效的提升遍历的性能.
伊吾县18522803878: 求二叉树的遍历算法 - ?
唐佩安奇: 这里有一份以前从网上找到的C语言代码,自己测试过,没有问题,写的很好,分享给你,供参考: #include<stdio.h> #include<stdlib.h> #define STACKINITSIZE 100 #define STACKINCREASESIZE 20 typedef char ElemType; //树结构 typedef ...
伊吾县18522803878: 求一个二叉树的前序,中序,后序的算法.分别用递归和非递归的方法来实现.一共六个算法,求IT届的大神! - ?
唐佩安奇: 二叉树的遍历是指按照一定次序访问二叉树中的所有节点,且每个节点仅被访问一次的过程.是最基本的运算,是其他运算的基础. 二叉树有两种存储结构:顺序存储和链式存储 顺序存储: (对完全二叉树来说,可以充分利用存储空间,但对...
伊吾县18522803878: 先序遍历二叉树非递归算法如何理解?? - ?
唐佩安奇: 先序遍历是中->左->右 进行遍历,每次 读入中后,下一步是读入左,读入左的下一步是读入右,但是左可能也是一颗树,那么 右就应该被压栈,保存.等左读完了,取出右再读入.对子树进行同样的操作.也就是 除了叶子节点,所有的右子节点都要压一次栈. 递归的是调用的系统栈,非递归的是用 堆中的数组来模拟系统栈.最直观的概念是 如果你有一个大任务,可以分成几个小任务,为了知道做完一个小任务后怎么办,你应当把其他小任务记下来,记到本子上.
伊吾县18522803878: 先序遍历二叉树的非递归算法 - ?
唐佩安奇: InitStack(S);//初始化栈 p=T;//取栈顶 while(P||!StackEmpty(S)){ //P存在或者栈非空 if(p) { //p非空,即左子树或者右子树存在 Push(S,p); //将左子树入栈 p=p->lchild; //取下一个左子树 } else{ Pop(S,p); //出栈,相当于先序遍历了,因为左子树都TMD入栈了,现在反向输出 p=p->rchild; //弹出一个左子树,就同时取其右子树右子树,然后又跳到这个if的最开头那里,p存在的那个分支.接下来再取右子树的左子树 } }//其实,用递归也许你更能理解一些.但是,递归本质上也是压栈,只不过是程序压栈,还不如这个效率高
伊吾县18522803878: 建立一棵二叉树,要求分别用递归和非递归方法实现二叉树的先序、中序和后序遍历. - ?
唐佩安奇: 我们的数据结构实验也是这题,需要我把我的实验报告给你参考下么! 我这里就只发这部分的代码.Status PreOrderTraverse(BiTree T) { //先序遍历二叉树T的递归算法 if (T) { printf("%d ",T->data); if(T->lchild) PreOrderTraverse(T->lchild); if(T->...