非遞歸實現樹的遍歷

【非遞歸實現樹的遍歷代碼】

#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;
}

C語言實現二叉樹的遞歸遍歷與非遞歸遍歷 http://www.linuxidc.com/Linux/2013-11/92544.htm

二叉樹遞歸實現與二重指針 http://www.linuxidc.com/Linux/2013-07/87373.htm