二叉树后序非递归算法
❶ c语言实现二叉树的先序,中序,后序的递归和非递归算法和层次遍历算法
#include<malloc.h> // malloc()等
#include<stdio.h> // 标准输入输出头文件，包括EOF(=^Z或F6)，NULL等
#include<stdlib.h> // atoi()，exit()
#include<math.h> // 数学函数头文件，包括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\n");
CreateBiTree(T); // 建立二叉树T
printf("先序递归遍历二叉树：\n");
PreOrderTraverse(T,visit); // 先序递归遍历二叉树T
printf("\n中序递归遍历二叉树：\n");
InOrderTraverse(T,visit); // 中序递归遍历二叉树T
printf("\n后序递归遍历二叉树：\n");
PostOrderTraverse(T,visit); // 后序递归遍历二叉树T
}
❷ 《数据结构》遍历二叉树的非递归算法的疑问。
首先敬仰一下楼主的勤奋！
我主要针对第二个算法说，我觉得上面这段话也是在讲第二个算法。其实两个算法差不太多。
1. 栈顶记录中的指针其实就是指栈顶，每次push()进去或者pop()出来的那个p。他代表的是正在访问的节点得下一个节点。比如，访问一个树t的左子树t->lchild时，栈顶就是t；访问t->lchild->lchild时，栈顶就是t->lchild。访问t->rchild时，栈顶为NULL；访问t->lchild->rchild时，栈顶为t；访问t->rchild->lchild时，栈顶也是t；访问t->rchild->rcchild时，栈顶仍为NULL。他的意义就是，在访问完了当前的子树之后，就会去访问栈顶记录的指针对应的节点的数据。
2. 关于“工作记录”那个词，我觉得还是别深究了。那段话意思是要仿照编译器把递归编译成迭代的思路来自己写迭代算法，可是实际上后面给出的算法里根本没有严格执行上述思路，写出来的算法并不是严格意义上的可以一般性替换递归的迭代算法。所以追究那个词也没意义，明白迭代遍历的算法怎么用就够了。等以后对递归有了更深刻的认识，自然就明白了。其实就是函数递归调用自身之前像中断那样保存自己的工作环境和进度。
3. （2）句并不矛盾。他说“指针为空时”和“指针指向的xxx”中间不是有句“退回上一层”么，那就表示pop()，于是原来那个在栈顶的空指针弹出去了，原来在第二位的指针现在到了栈顶。于是后面那句指的是对这个指针进行操作。
❸ 二叉树后序遍历非递归算法
#include
<stdio.h>
#include
<stdlib.h>
struct
tree
{
char
data;
struct
tree
*lchild;
struct
tree
*rchild;
};
typedef
struct
tree
*
treptr;
treptr
build(treptr
t)//先序建树
{
char
c;
c=getchar();
if(c=='#')
{
t=NULL;
}
else
{
t=(treptr)malloc(sizeof(struct
tree));
t->data=c;
t->lchild=build(t->lchild);
t->rchild=build(t->rchild);
}
return
t;
}
void
postdorder(treptr
root)//这是递归实现
{
if
(root!=NULL)
{
postdorder(root->lchild);
postdorder(root->rchild);
printf("%c",root->data);
}
}
struct
stack
{
treptr
*top,*base;
};
typedef
struct
stack
*stackptr;
void
init
(stackptr
s)//初始化栈
{
s->base=(treptr*)malloc(sizeof(treptr)*100);
s->top=s->base;
}
void
push(stackptr
s,treptr
t)//入栈
{
*(s->top++)=t;
}
treptr
pop(stackptr
s)//弹出栈顶元素
{
treptr
t;
t=*(--(s->top));
return
t;
}
treptr
gettop(stackptr
s)//取栈顶元素
{
treptr
*l=s->top-1;
return
*(l);
}
void
postorder(treptr
t)//这是非递归后序实现
{
stackptr
s=(stackptr)malloc(sizeof(struct
stack));
treptr
temp=t;
treptr
p;
treptr
lastvist=NULL;
init(s);
p=t;
while(p||s->top!=s->base)
{
while(p)
{
push(s,p);
p=p->lchild;
}
temp=gettop(s);
if(temp->rchild==NULL||temp->rchild==lastvist)
{
putchar(temp->data);
lastvist=pop(s);
}
else
p=temp->rchild;
}
}
int
main()
{
treptr
t=NULL;
t=build(t);
postdorder(t);
printf("非递归后序遍历\
");
postorder(t);
printf("\
");
return
0;
}
程序如上，可以运行。
我空间中有中序遍历的非递归实现。
不过给你写的是后序遍历的递归实现和非递归实现，它两个输出的结果是一致的。
输入
234##5#6##7##回车
就可以看到结果。
中序遍历及其对应树可以参考我空间中的文章
http://hi..com/huifeng00/blog/item/2ca470f56694f62e730eec39.html
❹ 二叉树先序遍历递归算法和非递归算法本质区别
在前面一文，说过二叉树的递归遍历算法（二叉树先根（先序）遍历的改进），此文主要讲二叉树的非递归算法，采用栈结构
总结先根遍历得到的非递归算法思想如下：
1）入栈，主要是先头结点入栈，然后visit此结点
2）while，循环遍历当前结点，直至左孩子没有结点
3）if结点的右孩子为真，转入1）继续遍历，否则退出当前结点转入父母结点遍历转入1）
先看符合此思想的算法：
[cpp] view plain print?
int (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;
}
❺ 如何用非递归算法求二叉树的高度
if（T＝＝null）
return0；
intfront＝－1，
rear＝－1；
／／front出队指针
rear入队指针intlast＝0，
level＝0；
／／last每一层的最右指针
（front＝＝last时候一层遍历结束level＋＋）BiTreeQ［Maxsize］；
／／模拟队列Q［＋＋rear］＝T；
BiTreep；
while(front<rear){
p＝Q［＋＋front］；／／开始出队
因为front要赶到lash
实现level＋＋
if(p->lchild)
Q[++rear] = p->lchild;
if(p->rchild)
Q[++rear] = p->rchild;
if（front＝＝last）｛
level＋＋；
last＝rear；／／last指向下层节点｝
｝
(5)二叉树后序非递归算法扩展阅读
非递归算法思想：
（1）设置一个栈S存放所经过的根结点（指针）信息；初始化S；
（2）第一次访问到根结点并不访问，而是入栈；
（3）中序遍历它的左子树，左子树遍历结束后，第二次遇到根结点，就将根结点（指针）退栈，并且访问根结点；然后中序遍历它的右子树。
（4）当需要退栈时，如果栈为空则结束。