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
2