用代码实现前序、中序、后序，第一种方法就是使用递归，另一种是使用栈。将分别讲述。
目录
1. 递归实现
main函数（C语言版本）
2. 利用栈实现
mystack.h
mystack.cpp
main函数
3.补充：求树高度的函数
1. 递归实现
main函数（C语言版本）
#include <stdio.h>
#if 0 //如下图示意图的树
a1
b2 c3
d4 e5 f6
前中后序如下
preOrder : 1 2 4 5 3 6 中左右
midOrder : 4 2 5 1 3 6 左中右
postOrder: 4 5 2 6 3 1 左右中;
#endif
//先中后，三种遍历的方式，本质是压栈顺序是没有什么不同的，
//所谓先中后，无非是访问根节点的时机不同而已。
typedef struct _TreeNode //二叉树的结构体
{
int _data;
struct _TreeNode *_left;
struct _TreeNode *_right;
}TreeNode;
void preOrderTraverse(TreeNode* r) //先序遍历
{
if(r)
{
printf("%d ",r->_data); //根左右
preOrderTraverse(r->_left); //递归,每个节点,都是独立的树,需要再次先序遍历,代码较少,但是思考是需要些时间的
preOrderTraverse(r->_right);
}
}
void middleOrderTraverse(TreeNode* r) //中序遍历
{
if(r)
{
middleOrderTraverse(r->_left); //左根右
printf("%d ",r->_data);
middleOrderTraverse(r->_right);
}
}
void postOrderTraverse(TreeNode* r) //后序遍历
{
if(r)
{
postOrderTraverse(r->_left); //左右根
postOrderTraverse(r->_right);
printf("%d ",r->_data);
}
}
int main()
{
TreeNode a,b,c,d,e,f; //画树
TreeNode * root = &a;
a._data=1;b._data=2;c._data=3;
d._data=4;e._data=5;f._data=6;
a._left=&b;a._right=&c;
b._left=&d;b._right=&e;
c._left=NULL; c._right=&f;
d._left=d._right=e._left=e._right=f._left=f._right=NULL;
preOrderTraverse(root);
putchar(10);
middleOrderTraverse(root);
putchar(10);
postOrderTraverse(root);
return 0;
}
2. 利用栈实现
这里需要栈的定义和函数
mystack.h
#include<stdio.h>
#include<stdlib.h>
typedef struct _TreeNode
{
int _data;
struct _TreeNode *_left;
struct _TreeNode *_right;
}TreeNode;
typedef struct _Node
{
TreeNode* data; //变量改成TreeNode*
struct _Node* next;
}Node;
typedef struct _Stack
{
Node* top;
}Stack;
void initStack(Stack *s); //先初始化
int isStackEmpty(Stack *s);//判断是否为空
void push(Stack *s, TreeNode *ch); //往里压
TreeNode* pop(Stack *s); //往外弹
void resetStack(Stack*s); //复位
void destroyStack(Stack*s); //销毁
mystack.cpp
#include"mystack.h"
void initStack(Stack *s) //初始化
{
s->top=(Node*)malloc(sizeof(Node));
s->top->next=NULL;
}
int isStackEmpty(Stack *s)//判断是否为空
{
return s->top->next==NULL;
}
void push(Stack *s, TreeNode* ch) //往里压
{
Node *cur=(Node*)malloc(sizeof(Node));
cur->data=ch;
cur->next=s->top->next; //链表的头插法
s->top->next=cur;
}
TreeNode * pop(Stack *s) //往外弹
{
Node*t=s->top->next; //找一个替身
s->top->next=t->next; //把头节点后面的首节点拿下来，实现先进后出，后进先出
TreeNode * ch;
ch=t->data; //因为要释放 t ,而且需要返回char，所以创建个变量记录下
free(t);
return ch;
}
void resetStack(Stack*s) //复位
{
while(!isStackEmpty( s))//一直弹出就行，pop函数里已经有释放
pop(s);
}
void destroyStack(Stack*s) //销毁
{
resetStack(s);
free(s->top);
}
main函数
#include <stdio.h>
#include"mystack.h"
#if 0
a1
b2 c3
d4 e5 f6
前中后序如下
preOrder : 1 2 4 5 3 6 中左右
midOrder : 4 2 5 1 3 6 左中右
postOrder: 4 5 2 6 3 1 左右中;
#endif
//非递归形式，迭代循环，使用栈
void preOrderIterator(TreeNode * r) //先序
{
if(r)
{
Stack s;
initStack(&s);
while (r || !isStackEmpty(&s)) // r 不为空即或者栈内不为空
{
while (r) //若 r 不为空，则一直指向左节点，给左节点压栈，直到左节点为空
{
printf("%d ",r->_data);
push(&s,r);
r=r->_left;
//压栈
}
r=pop(&s); //左节点为空，则弹出，判断是否存在右节点，若有则继续判断左节点
r=r->_right;
//出栈
}
}
}
void midOrderIterator(TreeNode * r) //中序
{
if(r)
{
Stack s;
initStack(&s);
while (r || !isStackEmpty(&s))
{
while (r)
{
push(&s,r);
r=r->_left;
//压栈
}
r=pop(&s);
printf("%d ",r->_data); //实际就是改变打印输出顺序
r=r->_right;
//出栈
}
}
}
void postdOrderIterator(TreeNode * r) //后序，逻辑较复杂
{
if(r)
{
Stack s;
initStack(&s);
TreeNode *cur; //当前结点
TreeNode *pre=NULL; //前一次访问的结点
push(&s,r);
while(!isStackEmpty(&s))
{
cur = pop(&s);
push(&s,cur); //这一步实际上就是在拿取栈顶的节点，来判断此节点的左右是否有子节点。
if((cur->_left==NULL&&cur->_right==NULL)||
(pre!=NULL&&(pre==cur->_left||pre==cur->_right)))
{
//如果当前结点没有子结点或者子节点都已被访问过
printf("%d ",cur->_data);
pop(&s);
pre=cur;
}
else
{
if(cur->_right != NULL)
push(&s,cur->_right);
if(cur->_left != NULL)
push(&s,cur->_left);
}
}
}
}
int main()
{
TreeNode a,b,c,d,e,f; //画树
TreeNode * root = &a;
a._data=1;b._data=2;c._data=3;
d._data=4;e._data=5;f._data=6;
a._left=&b;a._right=&c;
b._left=&d;b._right=&e;
c._left=NULL; c._right=&f;
d._left=d._right=e._left=e._right=f._left=f._right=NULL;
preOrderIterator(root);
putchar(10);
midOrderIterator(root);
putchar(10);
postdOrderIterator(root);
return 0;
}
3.补充：求树高度的函数
int getHeightByPostOrder(TreeNode * t)
{
int lH, rH, maxH;
if(t)
{
lH = getHeightByPostOrder(t->_left); //求左右高度，然后取出最大的
rH = getHeightByPostOrder(t->_right);
maxH = (lH>rH)?lH:rH;
return maxH +1;
}
else
return 0;
}
