先序遍历二叉树的非递归算法栈是怎么工作的?
这是最近写过的
#include
#include
#include
#define NULL 0
#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define OVERFLOW -1
typedef int Status;
typedef char TElemType;
typedef struct BiTNode{
TElemType data;
struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree,*SElemType;
typedef struct{
SElemType *base;
SElemType *top;
int stacksize;
}SqStack;
Status InitStack (SqStack &S)
{//构造空栈并初始化
S.base=(SElemType * )malloc(STACK_INIT_SIZE * sizeof(SElemType));
if(!S.base) exit(OVERFLOW);//存储分配失败
S.top=S.base;
S.stacksize=STACK_INIT_SIZE;
return OK;
}
Status StackEmpty(SqStack S)
{//判断是否为空栈,是返回TRUE,不是返回FALSE
if(S.base==S.top)
return TRUE;
else
return FALSE;
}
Status Push(SqStack &S,BiTree e)
{//将元素e压入栈顶
if(S.top-S.base>=S.stacksize)
{//栈满,追加存储空间
S.base=(SElemType *)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof (SElemType));
if(!S.base)exit(OVERFLOW);//存储分配失败
S.top=S.base+S.stacksize;
S.stacksize +=STACKINCREMENT;
}
*S.top++=e;
return OK;
}
Status Pop(SqStack &S,SElemType &e)
{//删除栈顶元素,用e返回其值,并返回OK,否则返回ERROR
if(S.top==S.base) return ERROR;//空栈情况
e=*--S.top;
return OK;
}
Status InitBiTree(BiTree &T)
{//构造空二叉树T
T=NULL;
return OK;
}
BiTree CreateBiTree(BiTree &T)
{//按先序次序输入二叉树中结点的值,空格字符表示空树
//构造二叉链表表示的二叉树T
char ch;
scanf("%c",&ch);
if (ch=='.') T=NULL;
else{
if(!(T=(BiTNode *)malloc(sizeof(BiTNode)))) exit(OVERFLOW);
T->data=ch;
CreateBiTree(T->lchild);
CreateBiTree(T->rchild);
}
return T;
}
Status PrintElement(TElemType e)
{//输出元素e的值
printf("%c",e);
return OK;
}
Status InOrderTraverse2(BiTree T, Status (*Visit)(TElemType)) {
// 采用二叉链表存储结构,Visit是对数据元素操作的应用函数。
// 中序遍历二叉树T的非递归算法,对每个数据元素调用函数Visit。
SqStack S;
BiTree p;
InitStack(S); p = T;
while (p || !StackEmpty(S)) { //P或stack不为空
if (p) {
Push(S, p);
p = p->lchild;
} // 非空指针进栈,继续左进
else { // 上层指针退栈,访问其所指结点,再向右进
Pop(S, p); //弹栈,将p指向被弹结点
if (!Visit(p->data)) //所访问结点不存在
return ERROR;
p = p->rchild;
}
}
return OK;
} // InOrderTraverse
void main()
{
BiTree T;
InitBiTree(T);
printf("创建二叉树T,空树用.代替:
");
CreateBiTree(T);
printf("
非递归算法中序遍历二叉树:");
InOrderTraverse2(T,PrintElement);
printf("
");
}
后序遍历是说,先访问左节点,再访问右节点,最后访问根节点。所以先左子树,后右子树。
首先先序遍历二叉树 ,你要搞清楚访问先后顺序是:根节点->左子树->右子树;然后的话,栈就是把结点一个个压入栈中,碰到左子树中最左下角的结点的时候,从栈中取出一个结点(你可以理解为是往上一层,回到它的父节点那里去),然后检查有无右子树,有的话,继续压栈,依此类推。。。。。。。
如果有做孩子就压栈,一直到没有左孩子弹出,再弹出孩子的父节点,再压栈右孩子
采用任务书的办法
把这段程序看看懂了就差不多了
typedef struct elemtype
{
Treeptr ptr;
int task;
}elemtype;
当task=1时遍历task=0时访问
int fdg_fro_visitTree(Treeptr T) //非递归先序遍历
{
linkstock s;
elemtype e;
Treeptr p;
initlinkstock(s);
e.ptr=T;e.task=1;
if(T)push(s,e);
while(s)
{
pop(s,e);
if(e.task==0)kankan(e.ptr);//kankan()是访问节点的函数
else
{
p=e.ptr;
e.task=1;
e.ptr=p->rchild;
if(e.ptr)push(s,e);
e.task=1;
e.ptr=p->lchild;
if(e.ptr)push(s,e);
e.ptr=p;
e.task=0;push(s,e);
}
}//while
return 1;
}
数据结构之二叉树的前序遍历、中序遍历、后序遍历(C语言实现非递归)
1、非递归前序遍历 口诀:根左右。前序遍历首先访问根结点,然后遍历左子树,最后遍历右子树。在遍历左、右子树时,仍然先访问根节点,然后遍历左子树,最后遍历右子树。1.1 具体流程 1.2 具体代码 2、非递归中序遍历 中序遍历是“左根右",即先遍历左子树节点,再遍历根节点,再遍历右子树节点 ...
干货|二叉树的前序遍历、中序遍历、后序遍历。(递归和非递归)
二叉树的遍历方式包括前序、中序和后序三种。这三种遍历方法在数据结构中起着至关重要的作用。对于树的遍历,递归和非递归是两种常见的实现方式。前序遍历按照“根结点-左孩子-右孩子”的顺序访问节点。在递归实现中,首先访问根节点,然后分别递归地访问左子树和右子树。对于非递归实现,我们使用栈来...
二叉树的后序遍历是如何进行的?
中序遍历:首先遍历左子树,然后访问根结点,最后遍历右子树;前序遍历:首先访问根结点,然后遍历左子树,最后遍历右子树;后序遍历:首先遍历左子树,然后遍历右子树,最后访问根结点。因此,后序遍历的结果为DEBFCA。后序遍历有递归算法和非递归算法两种。在二叉树中,先左后右再根,即首先遍历左子树...
二叉树先序非递归遍历C语言算法
\/*---递归---先序建立二叉树---*\/void CreateBiTree(bitree **T) { \/\/按先序次序输入二叉树中的结点的值(一个字符),空格字符表示空树, \/\/构造二叉链表表示二叉树 char ch; scanf("%c",&ch); if(ch=='#') *T=NULL; else{ *T=(bitree * )malloc(sizeof(bitree)); if(!*T) exit(1)...
...编写一个对二叉树进行前序遍历的递归和非递归程序
int ltag,rtag;\/\/树结点的左右线索 struct btree *left,*right;\/\/树结点的左右指针,ltag,rtag=1时指向前驱和后继,否则指向左右孩子 }node;node *SearchNode(node *q,node *r){\/\/在根结点地址为q的中序线索二叉树中查找结点r将要插入的结点 node *p;p=q;while(1){ while(r->datadata&&...
二叉树的非递归遍历
\/\/二叉树T存在,Visit是对结点操作的应用函数,中序递归遍历T,对每个结点调用函数Visit一次且仅一次 { if(T){ InOrderTraverse(T->lchild,Visit); \/\/ 先中序遍历左子树 Visit(T->data); \/\/ 再访问根结点 InOrderTraverse(T->rchild,Visit); \/\/ 最后中序遍历右子树 } } void PostOrder...
二叉树的遍历非递归算法中应注意哪些问题
先序非递归算法 【思路】假设:T是要遍历树的根指针,若T != NULL 对于非递归算法,引入栈模拟递归工作栈,初始时栈为空。问题:如何用栈来保存信息,使得在先序遍历过左子树后,能利用栈顶信息获取T的右子树的根指针?方法1:访问T->data后,将T入栈,遍历左子树;遍历完左子树返回时,栈顶...
二叉树中序遍历的非递归算法
\/\/二叉树进行中序非递归遍历 void NRInorder(BiTree t){ BiTree s;\/\/s-指向当前节点 BiTree stack[MAXNODE];\/\/定义栈 int top=-1;\/\/初始化栈顶指针 if(t==NULL)return;stack[++top]=t;\/\/根指针入栈 s=t->lchild; \/\/s指向左子树 while(s!=NULL||top!=-1)\/\/当存在节点(...
二叉树后序遍历(非递归)
一,大循环中的第一个循环,当前节点一直往左走一直走到头,并且把走过的节点压栈,这个循环遍历完成后,栈里面都是左边走过但是右边还没有走过的节点 二,从最左边那个没有更左的那个节点,它位于栈顶,因为这时栈顶不是一个右节点,第二个循环跳过,然后把栈顶结点的右节点标记为r并以此作为根节点...
二叉树先序遍历递归算法和非递归算法本质区别?
1. 先序遍历 在先序遍历中,对节点的访问工作是在它的左右儿子被访问之前进行的。换言之,先序遍历访问节点的顺序是根节点-左儿子-右儿子。由于树可以通过递归来定义,所以树的常见操作用递归实现常常是方便清晰的。递归实现的代码如下:void PreOrderTraversal(BinTree BT){ if( BT ){ printf(“%d...
隗蔡朗宁: typedef char DataType; typedef struct node{ DataType data; struct node *lchild,*rchild; }BinTNode; typedef BinTNode *BinTree; int count; void CreateBinTree(BinTree *T); void PreorderN(BinTree T); #define StackSize 10 /*假定预分配的栈空间最多...
许昌县19498384952: 先序遍历二叉树的非递归算法栈是怎么工作的? - ?
隗蔡朗宁: 如果有做孩子就压栈,一直到没有左孩子弹出,再弹出孩子的父节点,再压栈右孩子
许昌县19498384952: 先序遍历二叉树的非递归算法 - ?
隗蔡朗宁: 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存在的那个分支.接下来再取右子树的左子树 } }//其实,用递归也许你更能理解一些.但是,递归本质上也是压栈,只不过是程序压栈,还不如这个效率高
许昌县19498384952: 先序遍历二叉树非递归算法如何理解?? - ?
隗蔡朗宁: 先序遍历是中->左->右 进行遍历,每次 读入中后,下一步是读入左,读入左的下一步是读入右,但是左可能也是一颗树,那么 右就应该被压栈,保存.等左读完了,取出右再读入.对子树进行同样的操作.也就是 除了叶子节点,所有的右子节点都要压一次栈. 递归的是调用的系统栈,非递归的是用 堆中的数组来模拟系统栈.最直观的概念是 如果你有一个大任务,可以分成几个小任务,为了知道做完一个小任务后怎么办,你应当把其他小任务记下来,记到本子上.
许昌县19498384952: 二叉树层次和中序遍历算法 - ?
隗蔡朗宁: 先序非递归算法 【思路】 假设:T是要遍历树的根指针,若T != NULL 对于非递归算法,引入栈模拟递归工作栈,初始时栈为空. 问题:如何用栈来保存信息,使得在先序遍历过左子树后,能利用栈顶信息获取T的右子树的根指针? 方法1:访...
许昌县19498384952: 先序便利二叉树非递归算法如何理解? - ?
隗蔡朗宁: 递归方式:先访问根,再访问左子树(递归),再访问右子树(递归) 非递归:当前节点=ROOT; 循环(当前节点不为空) 访问当前节点.--先根,而且处理完后不在需要 如果有右子树,push (右子树)-- 表明在左子树全部处理完后再处理 如果有左子树,当前节点为左子树,continue - 表明优先处理左子树 如果没有子树,当前节点=pop(),continue - 表明一颗子树已经处理完了,需要从堆栈里面把以前记得需要处理的再拿出来.总的来说,非递归算法是利用堆栈,将不是马上要处理的东西放到堆栈里面,当需要处理的东西不能直接索引的时候.从堆栈中一个再挖出来处理.
许昌县19498384952: 二叉树先序遍历递归算法和非递归算法本质区别? - ?
隗蔡朗宁: 在前面一文,说过二叉树的递归遍历算法(二叉树先根(先序)遍历的改进),此文主要讲二叉树的非递归算法,采用栈结构 总结先根遍历得到的非递归算法思想如下: 1)入栈,主要是先头结点入栈,然后visit此结点 2)while,循环遍历当前结...
许昌县19498384952: 利用栈的基本操作写出先序遍历的非递归形式的算法. - ?
隗蔡朗宁: 我有现成的做好了的程序,调试成功.这个程序的难点就在于这种很别扭的输入形式,所以我为它设计了一个结构体形式存放输入内容,再将它转化成了线性结构.#include <iostream.h>#include <stdlib.h> struct inform /*建立输入信息结构体...
许昌县19498384952: 创一个二叉树;借助栈,实现二叉树的先序、中序遍历中的一种非递归算法;借助队列,实现按层次遍历算法. - ?
隗蔡朗宁: 我们的数据结构实验也是这题,需要我把我的实验报告给你参考下么! 我这里就只发这部分的代码. Status PreOrderTraverse(BiTree T) { //先序遍历二叉树T的递归算法 if (T) { printf("%d ",T->data); if(T->lchild) PreOrderTraverse(T->lchild); if(T->...
许昌县19498384952: 请利用栈的基本操作写出复制二叉树的非递归算法 - ?
隗蔡朗宁: //非递归方法 pbinary_tree_node copy_binary_tree(pbinary_tree_node bt) {//先序遍历输出一颗树的全部结点值1,2,3 stackstack_left,stack_right; pbinary_tree_node newbt; if (bt!=NULL) { //new root newbt=new binary_tree_node; newbt->data=bt->...