【非递归实现树的遍历代码】
#include <iostream>
#include <stack>
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<Tree> s;
while (curr != NULL || !s.empty()) {
if (curr != NULL) {
cout<<curr->key;
s.push(curr);
curr = curr->lchild;
}
else {
curr = s.top();
s.pop();
curr = curr->rchild;
}
}
/*
while (curr != NULL) {
cout<<curr->key;
s.push(curr);
curr = curr->lchild;
}
while(!s.empty()) {
curr = s.top();
s.pop();
tmp = curr->rchild;
while(tmp != NULL) {
cout<<tmp->key;
s.push(tmp);
tmp = tmp->lchild;
}
}
*/
}
void InOrder(Tree T) //中序遍历
{
if (T == NULL)
return;
TNode *curr = T;
//TNode *tmp;
stack<Tree> s;
while ((curr != NULL) || !s.empty()) {
if (curr != NULL) {
s.push(curr);
curr = curr->lchild;
}
else {
curr = s.top();
cout<<curr->key;
s.pop();
curr = curr->rchild;
}
}
}
void PostOrder(Tree T) //后序遍历
{
if (T == NULL)
return ;
TNode *curr = T, *pre = NULL;
stack<Tree> 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<<curr->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<<endl;
PreOrder(T);
cout<<endl;
PostOrder(T);
cout<<endl;
freeTree(T);
return 0;
}