一.简述
二叉树的遍历主要是先序、中序、后序及对应的递归和非递归算法，共3x2=6种，其中后序非递归在实现上稍复杂一些。二叉树的遍历是理解和学习递归及体会栈的工作原理的绝佳工具！
此外，非递归所用的栈及相关操作是第三章实现的，但数据类型做了更改。
二.头文件
//3_1.h
/**
author:zhaoyu
email:zhaoyu1995.com@gmail.com
date:2016-6-7
note:realize my textbook <<数据结构（C语言版）>>
*/
//Page 46
#ifndef _3_1_FOR_CHAPTER6_H_
#define _3_1_FOR_CHAPTER6_H_
#include <cstdio>
#include <cstdlib>
#include "head.h"
/**
My Code
*/
#define SElemType BiTree
//----栈的顺序存储表示----
#define STACK_INIT_SIZE 100//存储空间的初始分配值
#define STACKINCREMENT 10//存储空间分配增量
typedef struct{
SElemType *base;//在栈构造之前和销毁之后，base 值为 NULL
SElemType *top;//栈顶指针
int stacksize;//当前已分配的存储空间，以元素为单位
}SqStack;
//----基本操作的函数原型说明及部分实现----
Status InitStack(SqStack &S)
{
//构造一个空栈 S
S.base = (SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType));
if (!S.base)
{
exit(OVERFLOW);
}
S.top = S.base;
S.stacksize = STACK_INIT_SIZE;
return OK;
}//InitStack Status StackEmpty(SqStack S)
{
//若 S 为空栈， 则返回 TRUE， 否则返回 FALSE
if (S.base == S.top)
{
return TRUE;
}
else
{
return FALSE;
}
} Status GetTop(SqStack S, SElemType &e)
{
//若栈不空，则用 e 返回 S 的栈顶元素，并返回 OK；
//否则返回ERROR
if (S.top == S.base)
{
return ERROR;
}
e = *(S.top - );
return OK;
}//GetTop
Status Push(SqStack &S, SElemType e)
{
//插入元素 e 为新的栈顶元素
if (S.top - S.base >= S.stacksize)
{//栈满，追加存储空间
S.base = (SElemType *)realloc(S.base,
(S.stacksize+STACKINCREMENT)*sizeof(SElemType));
if (!S.base)
{
exit(OVERFLOW);
}
S.top = S.base + S.stacksize;
S.stacksize += STACKINCREMENT;
}
*S.top++ = e;
return OK;
}//Push
Status Pop(SqStack &S, SElemType &e)
{
//若栈不空，则删除 S 的栈顶元素，用 e 返回其
//值，并返回OK；否则返回ERROR
if (S.top == S.base)
{
return ERROR;
}
e = *--S.top;
return OK;
}//Pop
#endif
3_1_for_chapter6.h
//6_3_part1.h
/**
author：zhaoyu
date:2016-6-18
*/
#include "head.h"
#define TElemType char
//----二叉树的二叉链表表示----
typedef struct BiTNode{
TElemType data;
struct BiTNode *lchild, *rchild;
}*BiTree;
/**
algorithm 6.4
*/
Status CreateBiTree(BiTree &T)
{//按先序次序输入二叉树中结点的值（一个字符）,空格字符表示空树
//构造二叉链表表示的二叉树
char ch;
scanf("%c", &ch);
if (' ' == ch)
{
T = NULL;
}
else
{
if (!(T = (BiTree)malloc(sizeof(BiTNode))))
{
exit(OVERFLOW);
}
T->data = ch;//生成根结点
CreateBiTree(T->lchild);
CreateBiTree(T->rchild);
}
return OK;
}
Status Visit(TElemType e)
{
printf("%c", e);
return OK;
}
/**
algorithm 6.1
*/
Status RecursionPreOrderTraverse(BiTree T, Status (* Visit)(TElemType e))
{//采用二叉链表存储结构，Visit是对数据元素操作的应用函数
//先序遍历二叉树 T 的递归算法
if (T)
{
if (Visit(T->data))
{
if (RecursionPreOrderTraverse(T->lchild, Visit))
{
if (RecursionPreOrderTraverse(T->rchild, Visit))
{
return OK;
}
}
}
return ERROR;//这一行由于 Visit 函数只 return OK，貌似没什么用
}
else
{
return OK;
}
} Status RecursionInOrderTraverse(BiTree T, Status (* Visit)(TElemType e))
{//采用二叉链表存储结构，Visit是对数据元素操作的应用函数
//中序遍历二叉树 T 的递归算法
if (T)
{
if (RecursionInOrderTraverse(T->lchild, Visit))
{
if (Visit(T->data))
{
if (RecursionInOrderTraverse(T->rchild, Visit))
{
return OK;
}
}
}
return ERROR;
}
else
{
return OK;//注意是 return OK;
}
}
Status RecursionPostOrderTraverse(BiTree T, Status (* Visit)(TElemType e))
{//采用二叉链表存储结构，Visit是对数据元素操作的应用函数
//后序遍历二叉树 T 的递归算法
if (T)
{
if (RecursionPostOrderTraverse(T->lchild, Visit))
{
if (RecursionPostOrderTraverse(T->rchild, Visit))
{
if (Visit(T->data))
{
return OK;
}
}
}
return ERROR;
}
else
{
return OK;
}
} #include "3_1_for_chapter6.h"
Status UnRecursionPreOrderTraverse(BiTree T, Status (* Visit)(TElemType e))
{//采用二叉链表存储结构，Visit是对数据元素操作的应用函数
//先序遍历二叉树 T 的递归算法
SqStack S;
BiTree p = T;
InitStack(S);
while (p || !StackEmpty(S))
{
if (p)
{
if (!Visit(p->data))
{
return ERROR;
}
Push(S, p);
p = p->lchild;//根指针进栈遍历做子树
}
else
{//根指针退栈，访问根结点，遍历右子树
Pop(S, p);
p = p->rchild;
}
}
return OK;
}
/**
algorithm
*/
Status UnRecursionInOrderTraverse_1(BiTree T, Status (* Visit)(TElemType e))
{//采用二叉链表存储结构，Visit是对数据元素操作的应用函数
//中序遍历二叉树 T 的递归算法
BiTree p = NULL;
SqStack S;
InitStack(S);
Push(S, T);//跟指针进栈
while (!StackEmpty(S))
{
while (GetTop(S, p) && p)
{
Push(S, p->lchild);//从左走到尽头
}
Pop(S, p);//空指针退栈
if (!StackEmpty(S))
{
Pop(S, p);
if (!Visit(p->data))
{
return ERROR;
}
Push(S, p->rchild);
}
}
return OK;
}
Status UnRecursionInOrderTraverse_2(BiTree T, Status (* Visit)(TElemType e))
{//采用二叉链表存储结构，Visit是对数据元素操作的应用函数
//中序遍历二叉树 T 的递归算法
SqStack S;
BiTree p = T;
InitStack(S);
while (p || !StackEmpty(S))
{
if (p)
{
Push(S, p);
p = p->lchild;//根指针进栈遍历做子树
}
else
{//根指针退栈，访问根结点，遍历右子树
Pop(S, p);
if (!Visit(p->data))
{
return ERROR;
}
p = p->rchild;
}
}
return OK;
}
Status UnRecursionPostOrderTraverse(BiTree T, Status (* Visit)(TElemType e))
{//采用二叉链表存储结构，Visit是对数据元素操作的应用函数
//后序遍历二叉树 T 的递归算法
//稍难一点
SqStack S;
BiTree p = T, pre = NULL;
InitStack(S);
Push(S, p);
while (!StackEmpty(S))
{
if (GetTop(S,p) && p->lchild && pre!=p->lchild && !(p->rchild && pre == p->rchild))
{
Push(S, p->lchild);
}
else if (p->rchild && pre!=p->rchild)
{
Push(S, p->rchild);
}
else
{
Pop(S, p);
if (!Visit(p->data))
{
return ERROR;
}
pre = p;
}
}
return OK;
}
6_3_part1.h
三.CPP文件
#include "6_3_part1.h"
int main(int argc, char const *argv[])
{
BiTree T = NULL;
CreateBiTree(T);
printf("RecursionPreOrderTraverse\t");
RecursionPreOrderTraverse(T, Visit);
printf("\n");
printf("\n");
printf("\n"); printf("RecursionInOrderTraverse\t");
RecursionInOrderTraverse(T, Visit);
printf("\n");
printf("\n");
printf("\n"); printf("RecursionPostOrderTraverse\t");
RecursionPostOrderTraverse(T, Visit);
printf("\n");
printf("\n");
printf("\n"); printf("UnRecursionPreOrderTraverse\t");
UnRecursionPreOrderTraverse(T, Visit);
printf("\n");
printf("\n");
printf("\n"); printf("UnRecursionInOrderTraverse_1\t");
UnRecursionInOrderTraverse_1(T, Visit);
printf("\n");
printf("\n");
printf("\n"); printf("UnRecursionInOrderTraverse_2\t");
UnRecursionInOrderTraverse_2(T, Visit);
printf("\n");
printf("\n");
printf("\n"); printf("UnRecursionPostOrderTraverse\t");
UnRecursionPostOrderTraverse(T, Visit);
printf("\n");
printf("\n");
printf("\n");
return ;
}
6_3_part1.cpp
四.测试
测试用例（书的129页图6.9）：
各种遍历表示
