【非递归实现树的遍历代码】

#include
#include
using namespace std;

typedef struct Node{
char key;
struct Node *lchild, *rchild;
}*Tree, TNode;

void PreOrder(Tree T) //先序遍历
{
if (T == NULL)
return;
TNode *curr = T;
//TNode *tmp;
stack s;
while (curr != NULL || !s.empty()) {
if (curr != NULL) {
cout<key;
s.push(curr);
curr = curr->lchild;
}
else {
curr = s.top();
s.pop();
curr = curr->rchild;
}
}
/*
while (curr != NULL) {
cout<key;
s.push(curr);
curr = curr->lchild;
}
while(!s.empty()) {
curr = s.top();
s.pop();
tmp = curr->rchild;
while(tmp != NULL) {
cout<key;
s.push(tmp);
tmp = tmp->lchild;
}
}
*/
}

void InOrder(Tree T) //中序遍历
{
if (T == NULL)
return;
TNode *curr = T;
//TNode *tmp;
stack s;
while ((curr != NULL) || !s.empty()) {
if (curr != NULL) {
s.push(curr);
curr = curr->lchild;
}
else {
curr = s.top();
cout<key;
s.pop();
curr = curr->rchild;
}
}

}

void PostOrder(Tree T) //后序遍历
{
if (T == NULL)
return ;
TNode *curr = T, *pre = NULL;
stack s;
while (curr != NULL || !s.empty()) {
if (curr != NULL) {
s.push(curr);
curr = curr->lchild;
}
else {
curr = s.top();
s.pop();
if (curr->rchild != NULL && curr->rchild != pre) {
s.push(curr);
curr = curr->rchild;
}
else {
cout<key;
pre = curr;
curr = NULL;
}
}
}
}

Tree createTree(char *s, int n, int i) //建树
{
if (i >= n)
return NULL;
TNode *curr;
curr = (TNode *)malloc(sizeof(TNode));
curr->key = s[i];

curr->lchild = createTree(s, n, 2*(i+1)-1);
curr->rchild = createTree(s, n, 2*(i+1));
return curr;
}

void freeTree(Tree T) //释放
{
if (T != NULL){
freeTree(T->lchild);
freeTree(T->rchild);
delete T;
}
}

int main(void)
{
char s[] = "ABCDEFG";
Tree T;
T = createTree(s, 7, 0);
InOrder(T);
cout< PreOrder(T);
cout< PostOrder(T);
cout< freeTree(T);
return 0;
}