前面一篇介绍了二叉树的递归遍历操作http://blog.itpub.net/29876893/viewspace-1841619/，下面介绍二叉树的非递归遍历操作。
运用递归操作，很容易进行二叉树的遍历，结合上篇文章的介绍，在递归的时候都是找到当前结点，压入”栈“中，然后再通过当前结点找到左（右）孩子，递归函数每次返回时，当前结点都会出”栈“。在非递归遍历时，那就构造一个栈，用来存取每个结点的指针，通过该结点找到（左）右孩子，思路是有了。
下面结合下图简单的说明一下：

前序遍历：
首先A,B,C依次入栈，然后由于C->lchild为空，所以返回到结点C,遍历其右孩子C->rchild,但是也为空，此时C出栈，遍历B结点的右孩子，为空，B出栈，返回到A,A出栈，遍历A结点的右孩子，打印D的数据域，D进栈，遍历D的左孩子，为空，D出栈，遍历D的右孩子，为空，此时栈也空，该循环结束。
中序遍历：
首先A,B,C依次入栈，然后由于C->lchild为空，所以返回到C,打印C结点的数据域，然后遍历C->rchild,由于为空，C出栈，返回到B,打印结点B的数据域，然后遍历B->rchild,由于为空，B出栈，返回到A,A出栈，打印结点A的数据域，然后遍历A->rchild,不为空，然后遍历D->lchild，为空，返回到D,D出栈，打印D结点的数据域，然后遍历D->rchild,由于为空，此时栈为空，循环结束。
后序遍历：
A,B,C依次入栈，第一次遍历这些结点时，设置了标记，都为0.然后遍历C->lchild,为空，此时返回C,设置标记为1，然后访问C->rchild,由于为空，此时C出栈，打印了C结点的数据域。下面也是这样分析，由于过程复杂，读者可以自己分析，这里不作赘述。
下面给出上述的实现代码：

点击(此处)折叠或打开

#include<iostream>
#define MAX_SIZE 20
using namespace std;
typedef struct TreeNote {
char ch;
struct TreeNote *lchild, *rchild;
}*BiTree;
typedef struct Stack {
BiTree data[MAX_SIZE];
int top;
};
void createBiTree(BiTree &bt) {
char chh;
cin >> chh;
if (chh == '#')
bt = NULL;
else {
bt = new TreeNote;
bt->ch = chh;
createBiTree(bt->lchild);
createBiTree(bt->rchild);
}
}
void initStack(Stack *&st) {
st = new Stack;
st->top = -1;
}
bool emptyStack(Stack *st) {
return st->top == -1;
}
bool fullStack(Stack *st) {
return st->top == MAX_SIZE - 1;
}
void pushStack(Stack *st, BiTree bt) {
if (!fullStack(st))
st->data[++st->top] = bt;
else
cout << "栈已满!" << endl;
// exit(-1);
}
BiTree pop(Stack *st) {
if (!emptyStack(st)) {
return st->data[st->top--];
}
else
return NULL;
}
BiTree getpop(Stack *st) {
if (!emptyStack(st)) {
return st->data[st->top];
}
else
return NULL;
}
void preOrderTree(BiTree bt) {
Stack *st;
initStack(st);
BiTree p;
p = bt;
while (p != NULL || !emptyStack(st))
{
while (p != NULL)
{
cout << p->ch << " ";
pushStack(st, p);
p = p->lchild;
}
if (!emptyStack(st))
{
p = pop(st);
p = p->rchild;
}
}
}
void InOrderTree(BiTree bt) {
Stack *st;
initStack(st);
BiTree p;
p = bt;
while (p != NULL || !emptyStack(st)) {
while (p != NULL) {
pushStack(st, p);
p = p->lchild;
}
if (!emptyStack(st)) {
p = pop(st);
cout << p->ch << " ";
p = p->rchild;
}
}
}
void postOrderTree(BiTree bt)
{
BiTree p;
Stack *st;
initStack(st);
p = bt;
int flag[20];
while (p != NULL || !emptyStack(st))
{
while (p != NULL)
{
pushStack(st, p);
flag[st->top] = 0;
p = p->lchild;
}
while (!emptyStack(st) && flag[st->top] == 1)
{
p = pop(st);
cout << p->ch << " ";
}
if (!emptyStack(st))
{
flag[st->top] = 1;
p = getpop(st);
p = p->rchild;
}
else break;
}
}
int main() {
TreeNote *bt;
cout << "please input some values:" << endl;
createBiTree(bt);
cout << "preOrderTree:" << endl;
preOrderTree(bt);
cout << endl;
cout << "InOrderTree:" << endl;
InOrderTree(bt);
cout << endl;
cout << "postOrderTree:" << endl;
postOrderTree(bt);
cout << endl;
}

运行结果：

ITPub博客

二叉树的非递归遍历

最新文章