zz http://blog.csdn.net/fuzhufang/archive/2009/03/08/3969375.aspx
先来看下面这棵二叉树。如图 1 。现在我们要对它进行先序遍历。递归思想：就是把这个大树拆分成 N 棵小树，每棵小树都进行一次先序遍历。再把这些遍历连合起来就是这棵树的先序遍历了。同理中序遍历和后序遍历也是一样的方法。下面举例说明先序递归算法：
令先序遍历的结果等于 S ；
图 1
对于图 2 这棵小树的先序遍历是： 1 2 3
S = 1 2 3
图 2
但以 2 为根节点又有一棵小树，这棵小树的先序遍历是： 2 4 5
S = 1 2 4 5 3
图 3
以 3 为根节点又有一棵小树，这棵小树的先序遍历是： 3 6 7
S = 1 2 4 5 3 6 7
图 4
以 6 为根节点又有一棵小树，这个小树的先序遍历是： 6 7
S =1 2 4 5 3 6 8 7
图 5
以 7 为跟节点又有一棵小树，这棵小树的先序遍历是： 7 9
S = 1 2 4 5 3 6 8 7 9
图 6
这样就得出了这棵大树的最终先序遍历结果了：
S = 1 2 4 5 3 6 8 7 9 。
再来看看这个变化过程：
S = 1 2 3
S = 1 2 4 5 3
S = 1 2 4 5 3 6 7
S =1 2 4 5 3 6 8 7
S = 1 2 4 5 3 6 8 7 9
对于二叉树的非递归算法，则是需要应用一种重要的数据结构 — 栈。用栈来存放准备需要访问的节点。例如先序遍历的非递归算法则是：
指针 p 指向根节点；
while （ p 不为 NULL 或栈不空）｛
反复访问当前节点 *p ，
指针 p 进栈、再将指针左移，直至最左下节点；
当栈不空时，出栈，
取出栈顶指针且右移（返回上面操作，去遍历右子树）；
｝
下面是二叉树递归与非递归算法的 C 语言实现实例：
//tree.h
#ifndef __TREE_H__
#define __TREE_H__
typedef struct _node {
struct _node * left_child ;
struct _node * right_child ;
ctype_t data ;
} node , * tree ; // 二叉树节点结构
// 一种简单创建树的办法，供测试使用
void create_tree ( tree * root , const ctype_t elems [], csize_t * current_index , const csize_t max_size );
// 不考虑二叉树的销毁了
// 二叉树先序遍历递归算法
void preorder_recursion ( tree root );
// 二叉树先序遍历递非归算法
void preorder_nonrecursive ( tree root );
// 二叉树中序遍历递归算法
void inorder_recursion ( tree root );
// 二叉树中序遍历递非归算法
void inorder_nonrecursive ( tree root );
// 二叉树后序遍历递归算法
void postorder_recursion ( tree root );
// 二叉树后序遍历递非归算法
void postorder_nonrecursive ( tree root );
#endif //__TREE_H__
//tree.c
#include "tree.h"
void create_tree ( tree * root , const ctype_t elems [], csize_t * current_index , const csize_t max_size )
{
if (* current_index < max_size )
{
const ctype_t t = elems [(* current_index )++];
if ( 0 == t )
{
* root = NULL ;
return ;
}
else
{
* root = ( node *) malloc ( sizeof ( node )); // 假设 malloc 总是成功
(* root )-> data = t ;
create_tree (&(* root )-> left_child , elems , current_index , max_size );
create_tree (&(* root )-> right_child , elems , current_index , max_size );
}
}
}
void preorder_recursion ( tree root )
{
if ( NULL != root )
{
printf ( "%d/t" , root -> data ); // 根
preorder_recursion ( root -> left_child ); // 左子树
preorder_recursion ( root -> right_child ); // 右子树
}
}
void preorder_nonrecursive ( tree root )
{
tree stack [ 100 ];
int top = 0 ;
tree p = root ;
while ( NULL != p || top > 0 )
{
while ( NULL != p )
{
printf ( "%d/t" , p -> data );
stack [ top ++] = p ;
p = p -> left_child ;
}
p = stack [-- top ];
p = p -> right_child ;
}
}
void inorder_recursion ( tree root )
{
if ( NULL != root )
{
inorder_recursion ( root -> left_child ); // 左子树
printf ( "%d/t" , root -> data ); // 根
inorder_recursion ( root -> right_child ); // 右子树
}
}
void inorder_nonrecursive ( tree root )
{
tree stack [ 100 ];
int top = 0 ;
tree p = root ;
while ( NULL != p || top > 0 )
{
while ( NULL != p )
{
stack [ top ++] = p ;
p = p -> left_child ;
}
p = stack [-- top ];
printf ( "%d/t" , p -> data );
p = p -> right_child ;
}
}
void postorder_recursion ( tree root )
{
if ( NULL != root )
{
postorder_recursion ( root -> left_child );
postorder_recursion ( root -> right_child );
printf ( "%d/t" , root -> data );
}
}
void postorder_nonrecursive ( tree root )
{
tree stack [ 100 ];
int top = 0 ;
tree p = root ;
tree lastvist = NULL ;
while ( NULL != p || top > 0 )
{
while ( NULL != p )
{
stack [ top ++] = p ;
p = p -> left_child ;
}
p = stack [ top - 1 ];
if ( NULL == p -> right_child || lastvist == p -> right_child )
{
printf ( "%d/t" , p -> data );
-- top ;
lastvist = p ;
p = NULL ;
}
else
{
p = p -> right_child ;
}
}
}
//main.c
#include "tree.h"
int main ()
{
ctype_t elems [] = { 1 , 2 , 4 , 0 , 0 , 5 , 0 , 0 , 3 , 6 , 8 , 0 , 0 , 0 , 7 , 0 , 9 , 0 , 0 , 0 ,};
csize_t current_index = 0 ;
tree t = NULL ;
create_tree (& t , elems , & current_index , sizeof ( elems ));
printf ( " 二叉树先序遍历递归算法 /n" );
preorder_recursion ( t );
printf ( "/n" );
printf ( " 二叉树先序遍历非递归算法 /n" );
preorder_nonrecursive ( t );
printf ( "/n/n" );
printf ( " 二叉树中序遍历递归算法 /n" );
inorder_recursion ( t );
printf ( "/n" );
printf ( " 二叉树中序遍历非递归算法 /n" );
inorder_nonrecursive ( t );
printf ( "/n/n" );
printf ( " 二叉树后序遍历递归算法 /n" );
postorder_recursion ( t );
printf ( "/n" );
printf ( " 二叉树后序遍历非递归算法 /n" );
postorder_nonrecursive ( t );
printf ( "/n" );
return 0 ;
}
输出结果：
二叉树先序遍历递归算法
1 2 4 5 3 6 8 7 9
二叉树先序遍历非递归算法
1 2 4 5 3 6 8 7 9
二叉树中序遍历递归算法
4 2 5 1 8 6 3 7 9
二叉树中序遍历非递归算法
4 2 5 1 8 6 3 7 9
二叉树后序遍历递归算法
4 5 2 8 6 9 7 3 1
二叉树后序遍历非递归算法
4 5 2 8 6 9 7 3 1
Press any key to continue
=================
zz http://blog.pfan.cn/byoneself/19799.html
PreOrder(BiTree T) //先序非递归遍历二叉树
{
InitStack(S); //创建工作栈
Push(S,T);
while(!StackEmpty(S))
{
Pop(S,p); //出栈
Visit(p); //访问
if(p->rchild)
Push(S,p->rchild); //右子树入栈
if(p->lchild)
Push(S,p->lchild); //左子树入栈
}
}
InOrder(BiTree T) //中序非递归遍历二叉树
{
InitStack(S); //创建工作栈
Push(S,<T,0>); //根入栈，且置0标志此时不能访问
while(!StackEmpty(S))
{
Pop(S,<p,flag>); //出栈
if(flag==1)
Visit(p); //访问标志为1可以访问
else
{
if(p->rchild)
Push(S,<p->rchild,0>); //右子树入栈且置访问标志0
Push(S,<p,1>); //根入栈且置访问标志1
if(p->lchild)
Push(S,<p->lchild,0>); //左子树入栈且置访问标志0
}
}
}
PostOrder(BiTree T) //后序非递归遍历二叉树
{
InitStack(S); //创建工作栈
Push(S,<T,0>); //根入栈，且置i0标志此时不能访问
while(!StackEmpty(S))
{
Pop(S,<p,flag>); //出栈
if(flag==1)
Visit(p); //访问标志为1可以访问
else
{
Push(S,<p,1>); //根入栈且置访问标志1
if(p->rchild)
Push(S,<p->rchild,0>); //右子树入栈且置访问标志0
if(p->lchild)
Push(S,<p->lchild,0>); //左子树入栈且置访问标志0
}
}
}
LayerOrder(BiTree T) //层次遍历二叉树
{
InitQueue(Q); //创建工作队列
EnQueue(Q,T); //根入队
while(!QueueEmpty(Q))
{
DeQueue(Q,p); //出队
Visit(p); //访问
if(p->lchild)
EnQueue(Q,p->lchild); //左子树入队
if(p->rchild)
EnQueue(Q,p->rchild); //右子树入队
}
}
===
其他：
1
二叉树遍历及C语言实现
2
判断整数序列是不是二元查找树的后序遍历结果