用栈和递归写的就不用贴过来了，那个我已经知道了，现在我只要不用栈实现的的！

Question

类似于这样的：void preorder(BiTree T)//先序遍历{BiTree s[100];int top=0;while(T||top){while(T){s[++top]=T;putchar(s[top]->data);T=T->lchild;}if(top){T=s[top--]->rchild;}}}

Answer 1

以下是我写的二叉树的头文件,有你想要的(不失一般性,我用的是模板).里面有非递归后序遍历 .栈和队列的头文件也在.用main()举了一个例子,自己看吧. 

//****************BiTree.h 

#ifndef B_I_T_R_E_E 

#define B_I_T_R_E_E 

#include <iostream> 

//#include <conio.h> 

#include "stack.h" 

#include "Lqueue.h" 

using namespace std; 

template <class TElemType> 

struct BiTNode{ 

TElemType data; 

BiTNode<TElemType> *lchild,*rchild; 

}; 

template <class TElemType> 

class BiTree 

{ 

public: 

void CreateBiTree(BiTNode<TElemType> *&T); 

void PreOrderTraverse(BiTNode<TElemType> *T); 

void InOrderTraverse(BiTNode<TElemType> *T); 

void PostOrderTraverse(BiTNode<TElemType> *T); 

void LevelOrderTraverse(BiTNode<TElemType> *T); 

}; 

template <class TElemType> 

void BiTree<TElemType>::CreateBiTree(BiTNode<TElemType> *&T) 

{ 

TElemType ch; 

cout << "请输入数据(-1表示空(非字符型)):" << endl; 

cin >> ch; 

if(ch == -1) T = NULL; 

else 

{ 

if(!(T = (BiTNode<TElemType> *)malloc(sizeof(BiTNode<TElemType>)))) exit(0); 

T->data = ch; 

CreateBiTree(T->lchild); 

CreateBiTree(T->rchild); 

} 

} 

template <class TElemType> 

//递归先序遍历 

void BiTree<TElemType>::PreOrderTraverse(BiTNode<TElemType> *T) 

{ 

if(T) 

{ 

cout << T->data << endl; 

PreOrderTraverse(T->lchild); 

PreOrderTraverse(T->rchild); 

} 

} //PreOrderTraverse 

/*非递归先序遍历 

void BiTree<TElemType>::PreOrderTraverse(BiTNode<TElemType> *T) 

{ 

BiTNode<TElemType> * p = T; 

stack<BiTNode<TElemType> *> S; 

S.InitStack(); 

while(p || !S.StackEmpty()) 

{ 

if(p) 

{ 

S.Push(p); 

cout << p->data << endl; 

p = p->lchild; 

} 

else 

{ 

S.Pop(p); 

p = p->rchild; 

} 

} 

S.DestroyStack(); 

} */ 

//递归中序遍历 

template <class TElemType> 

void BiTree<TElemType>::InOrderTraverse(BiTNode<TElemType> *T) 

{ 

if(T) 

{ 

InOrderTraverse(T->lchild); 

cout << T->data << endl; 

InOrderTraverse(T->rchild); 

} 

} 

//非递归中序遍历 

/*void BiTree<TElemType>::InOrderTraverse(BiTNode<TElemType> *T) 

{ 

BiTNode<TElemType> * p = T; 

stack<BiTNode<TElemType> *> S; 

S.InitStack(); 

while(p || !S.StackEmpty()) 

{ 

if(p) 

{ 

S.Push(p); 

p = p->lchild; 

} 

else 

{ 

S.Pop(p); 

cout << p->data << endl; 

p = p->rchild; 

} 

} 

S.DestroyStack(); 

} */ 

//递归后序遍历 

template <class TElemType> 

void BiTree<TElemType>::PostOrderTraverse(BiTNode<TElemType> *T) 

{ 

if(T) 

{ 

PostOrderTraverse(T->lchild); 

PostOrderTraverse(T->rchild); 

cout << T->data << endl; 

} 

} 

//非递归后序遍历 

/*void BiTree<TElemType>::PostOrderTraverse(BiTNode<TElemType> *T) 

{ 

BiTNode<TElemType> * p = T; 

BiTNode<TElemType> * q = NULL; 

stack<BiTNode<TElemType> *> S; 

S.InitStack(); 

S.Push(p); 

p = p->lchild; 

while(!S.StackEmpty()) 

{ 

if(p) 

{S.Push(p);p = p->lchild;} 

else 

{ 

S.GetTop(p); 

p = p->rchild; 

if(!p) 

{ 

S.Pop(p); 

cout << p->data << endl; 

S.GetTop(q); 

while(q && p == q->rchild) 

{ 

S.Pop(p); 

cout << p->data << endl; 

S.GetTop(q); 

//if(q == NULL) break; 

} 

if(q) 

{ 

S.GetTop(q); 

p = q->rchild; 

} 

} 

} 

} 

S.DestroyStack(); 

} */ 

//非递归层次遍历 

template <class TElemType> 

void BiTree<TElemType>::LevelOrderTraverse(BiTNode<TElemType> *T) 

{ 

Lqueue<BiTNode<TElemType> *> que; 

que.InitQueue(); 

if(T) que.EnQueue(T); 

while(!que.QueueEmpty()) 

{ 

que.GetHead(T); 

if(T->lchild) que.EnQueue(T->lchild); 

if(T->rchild) que.EnQueue(T->rchild); 

que.DeQueue(T); 

cout << T->data << endl; 

} 

que.DestroyQueue(); 

} 

#endif 

//**************BiTree.h 

//****Lqueue.h 

#ifndef _LQUEUE_H 

#define _LQUEUE_H 

#define MAXQSIZE 100 

typedef int Status; 

template <class QElemType> 

class Lqueue 

{ 

public: 

void InitQueue(); 

void DestroyQueue(); 

void ClearQueue(); 

Status QueueEmpty(); 

Status QueueLength(); 

void GetHead(QElemType & e); 

void EnQueue(QElemType e); 

void DeQueue(QElemType & e); 

private: 

struct SqQueue 

{ 

QElemType * base; 

int front; 

int rear; 

}; 

SqQueue Q; 

}; 

//********Lqueue.cpp******** 

template <class QElemType> 

void Lqueue<QElemType>::InitQueue() 

{ 

Q.base = (QElemType *)malloc(MAXQSIZE * sizeof(QElemType)); 

if(!Q.base) exit(0); 

Q.front = Q.rear = 0; 

} 

template <class QElemType> 

void Lqueue<QElemType>::DestroyQueue() 

{ 

free(Q.base); 

} 

template <class QElemType> 

void Lqueue<QElemType>::ClearQueue() 

{ 

Q.front = Q.rear = 0; 

} 

template <class QElemType> 

Status Lqueue<QElemType>::QueueEmpty() 

{ 

if(Q.front == Q.rear) return 1; 

return 0; 

} 

template <class QElemType> 

Status Lqueue<QElemType>::QueueLength() 

{ 

return (Q.rear - Q.front + MAXQSIZE)%MAXQSIZE; 

} 

template <class QElemType> 

void Lqueue<QElemType>::GetHead(QElemType & e) 

{ 

if(Q.front == Q.rear) e = NULL; 

else 

{ 

e = Q.base[Q.front]; 

} 

} 

template <class QElemType> 

void Lqueue<QElemType>::EnQueue(QElemType e) 

{ 

if((Q.rear + 1)%MAXQSIZE == Q.front) cout << "ERROR" << endl; 

else 

{ 

Q.base[Q.rear] = e; 

Q.rear = (Q.rear + 1)%MAXQSIZE; 

} 

} 

template <class QElemType> 

void Lqueue<QElemType>::DeQueue(QElemType & e) 

{ 

if(Q.front == Q.rear) cout << "ERROR" << endl; 

else 

{ 

e = Q.base[Q.front]; 

Q.front = (Q.front + 1)%MAXQSIZE; 

} 

} 

//******************Lqueue.cpp*************** 

#endif //*****Lqueue.h******** 

//*****stack.h 

#ifndef _STACK_H 

#define _STACK_H 

#define STACK_INIT_SIZE 100 

#define STACKINCREMENT 10 

typedef int Status; 

template<class QElemType> 

class stack 

{ 

public: 

void InitStack(); 

void DestroyStack(); 

void ClearStack(); 

Status StackEmpty(); 

Status StackLength(); 

void GetTop(QElemType & e); 

void Push(QElemType e); 

void Pop(QElemType & e); 

private: 

struct SqStack{ 

QElemType *base; 

QElemType *top; 

int stacksize; 

}S; 

}; 

//******stack.cpp------ 

template<class QElemType> 

void stack<QElemType>::InitStack() 

{ 

S.base = (QElemType *)malloc(STACK_INIT_SIZE * sizeof(QElemType)); 

if(!S.base) exit(0); 

S.top = S.base; 

S.stacksize = STACK_INIT_SIZE; 

} 

template <class QElemType> 

void stack<QElemType>::DestroyStack() 

{ 

free(S.base); 

} 

template <class QElemType> 

void stack<QElemType>::ClearStack() 

{ 

S.top = S.base; 

} 

template <class QElemType> 

Status stack<QElemType>::StackEmpty() 

{ 

if(S.top == S.base) return 1; 

else return 0; 

} 

template <class QElemType> 

Status stack<QElemType>::StackLength() 

{ 

return (S.top - S.base); 

} 

template <class QElemType> 

void stack<QElemType>::GetTop(QElemType & e) 

{ 

if(S.top != S.base) 

e = *(S.top - 1); 

else e = NULL; 

} 

template <class QElemType> 

void stack<QElemType>::Push(QElemType e) 

{ 

if(S.top - S.base >= S.stacksize) 

{ 

S.base = (QElemType *)realloc(S.base,(S.stacksize + STACKINCREMENT) * sizeof(QElemType)); 

if(!S.base) exit(0); 

S.top = S.base + S.stacksize; 

S.stacksize += STACKINCREMENT; 

} 

*S.top++ = e; 

} 

template <class QElemType> 

void stack<QElemType>::Pop(QElemType & e) 

{ 

if(S.top == S.base) e = NULL; 

else 

e = * --S.top; 

} 

//**********stack.cpp 

#endif //stack.h **** 

//#include <iostream> 

#include "BiTree.h" 

//#include "stack.h" 

//#include "Lqueue.h" 

//using namespace std; 

int main() 

{ 

BiTree<int> tree; 

BiTNode<int> *T = NULL; 

tree.CreateBiTree(T); 

tree.InOrderTraverse(T); 

tree.PreOrderTraverse(T); 

tree.PostOrderTraverse(T); 

tree.LevelOrderTraverse(T); 

return 0; 

} 

新建3个头文件stack.h,Lqueue.h,BiTree.h 

分别将各个头文件的内容拷到相应的地方. 

新建C++ Source file 

将main函数的内容拷入cpp文件. 

运行时如输入1,2,4,-1,-1,5,-1,-1,3,-1,-1 

相应的遍历结果会出现.

Answer 2

非递归实现后续遍历二叉树，此程序已调试成功：
void postorder(BTree T)
{
DataType s[100],sq;
BTree p=T;
int top=-1;
while(p||top!=-1)
{
while(p)
{
top++;
sq.flag=0;
sq.node=p;
s[top]=sq;
p=p->lchild;
}
if(top!=-1)
{
sq=s[top];
p=sq.node;
top--;
if(sq.flag==0)
{
sq.flag=1;
top++;
s[top]=sq;
p=p->rchild;
}
else/*若第二次出栈，则输出该节点*/
{
printf("%c",sq.node->data);
p=NULL;
}
}
}
}