今天上机，写了个二叉树的遍历。虽然代码比较烂，但是用非递归写出来还是比较满意的！贴出来吧..............呵呵！！！

#include "stdafx.h"
#include <malloc.h>
using namespace std;

typedef struct Node
{
   char var;
   struct Node * Lnode;
   struct Node * Rnode;
   struct Node * pNext;
}*PNODE ,NODE;

//栈
typedef struct Stack
{
   PNODE pTop; //定义pTop节点
   PNODE pBottom;//定义pBottom节点（此节点始终不指向任何的节点，它的pNext为空）

}STACK,* PSTACK;

PNODE CreateBtr();
void initStack(PSTACK pS);
bool push(PSTACK pS,PNODE pt);
char pop(PSTACK pS);

void Midtraverse(PNODE pt);
void Pretraverse(PNODE pt);
void Lasttraverse(PNODE pt);

int _tmain(int argc, _TCHAR* argv[])
{
   PNODE p;
   p = CreateBtr();
   printf("二叉树创建完成！\n");
  
   printf("中序遍历：\n");
   Midtraverse(p);
  
   printf("前序遍历：\n");
   Pretraverse(p);

   printf("后序遍历：\n");
   Lasttraverse(p);
   printf("\n");
   getchar();
   return 0;
}
PNODE CreateBtr()
{
PNODE p = NULL;
char x;
cin>>x;
if(x == '#')
{
    p = NULL;
}
else
{
    p = (PNODE)malloc(sizeof(NODE));
p->var = x;
p->Lnode = CreateBtr();
p->Rnode = CreateBtr();
}
return p;
}
//中序遍历
void Midtraverse(PNODE pt)
{
   STACK stack;
   initStack(&stack);
   while((pt != NULL) || (stack.pTop != stack.pBottom))
   {
     if(pt != NULL)
{
   push(&stack,pt);
   pt = pt->Lnode;
}
else
{
   pt = stack.pTop->Rnode;
   printf("%c   ",pop(&stack));
}
   }
   printf("\n");

}
//前序遍历
void Pretraverse(PNODE pt)
{
   STACK stack;
   initStack(&stack);
   while((pt != NULL) || (stack.pTop != stack.pBottom))
   {
     if(pt != NULL)
{
   printf("%c   ",pt->var);

   if(pt->Rnode != NULL)
   {
    push(&stack,pt->Rnode);
   }

   pt = pt->Lnode;
}
else
{
   PNODE p = stack.pTop->Rnode;
   pt = stack.pTop->Lnode;
   printf("%c   ",pop(&stack));
   if(p != NULL)
   {
     push(&stack,p);
   }
}
   }
      printf("\n");
}
//后序遍历【这个用的是递归】
void Lasttraverse(PNODE pt)
{
if(pt != NULL)
   {
    Lasttraverse(pt->Lnode);
    Lasttraverse(pt->Rnode);
    printf("%c   ",pt->var);
   }
}
//初始化一个栈
void initStack(PSTACK pS)
{
   //将栈元素pTop， pBottom（PNODE类 型）都指向了一个动态生成的节点 ，此节点的pNext为空（既不指向任何节点）
   pS->pTop = (PNODE)malloc(sizeof(NODE));
   //判断节点是否创建成功，即顶部节点指针变量的地址是否为空
   if(pS->pTop == NULL)
   {
   printf("内存分配失败");
      exit(-1);
   }
   else
   {
//不为空的话， 将底部节点指针也指向这个节点
     pS->pBottom = pS->pTop;
//将这个节点的pNext（指针域设为空）
     pS->pBottom->pNext = NULL;
   }
}

//入栈操作
bool push(PSTACK pS,PNODE pt)
{
   //新建一个指针
   PNODE pOld;
   //将指向顶部节点的指针的值赋给了pOld
   pOld = pS->pTop;
   //重新创建了一个节点 将其地址赋给了 pS->pTop
   pS->pTop = (PNODE)malloc(sizeof(NODE));
   pS->pTop->var = pt->var;
   pS->pTop->Lnode = pt->Lnode;
   pS->pTop->Rnode = pt->Rnode;
   //新的顶部节点指向了旧的顶部节点
   pS->pTop->pNext = pOld;
   //printf("进栈成功！\n");
   return true;
}

//出栈操作
char pop(PSTACK pS)
{
PNODE p = pS->pTop;
char var = pS->pTop->var;
pS->pTop = pS->pTop->pNext;
free(p);
return var;
}