先序遍历二叉树的非递归算法栈是怎么工作的？

数据结构 二叉树的非递归遍历（用栈实现）~

这是最近写过的
#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;
}

---

许昌县19498384952： 二叉树先序遍历的非递归算法(用栈实现) - ？
隗蔡朗宁： 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->...