10.4-5 O(n)非递归O(1)空间遍历二叉树树节点
转自http://blog.csdn.net/mishifangxiangdefeng/article/details/7708490
采用类似中序遍历的处理方法，对一个结点，可以分为以下几种情况
1.从父结点进入子结点进行处理
（1）如果有左孩子，就处理左孩子
（2）返回到自己
（3）访问自己
（4）如果有右孩子，就处理右孩子
（5）返回到自己的父结点
2.从左孩子返回，说明左孩子已经处理过，自己还没访问，自己的右孩子也没有处理过，就进行1-（2）
3.从右孩子返回，说明左右孩子都已经处理，自己也访问过，就返回到更上层
4.返回到根结点时，遍历结束
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128 |
#include <iostream>using
namespace std;//二叉树结点的结构体struct
node{ int
key;//值 node *left;//指向左孩子 node *right;//指向右孩子 node(){}//默认构造函数 node(int
x):key(x),left(NULL),right(NULL){}//构造函数};//树的结构体struct
tree{ node *root;//树中只有一个指向根结点的指针 tree():root(NULL){}//构造函数};/************10.4-2-递归地遍历访问二叉树***************************************///输出访问某个结点void
Node_Print(node *N){ //访问当前结点 cout<<N->key<<‘ ‘; //递归地访问其左孩子 if(N->left) Node_Print(N->left); //递归地访问其右孩子 if(N->right) Node_Print(N->right);}//遍历二叉树void
Tree_Print(tree *T){ //只孩子访问根结点，其它结点都在递归中访问了 Node_Print(T->root); cout<<endl;}/*************10.4-3-非递归地遍历二叉树*******************************************///把x结点压入栈S的顶部void
Push(node *S, node x){ S[0].key++; S[S[0].key] = x;}//弹出栈顶元素并返回node* Pop(node *S){ if(S[0].key == 0) return
NULL; node *ret = &S[S[0].key]; S[0].key--; return
ret;}//用非递归的方式遍历二叉树void
Tree_Print2(tree *T){ //这种方式要借助一个栈来实现，栈的大小为树的深度 node Stack[15] = {0};//简单的数组栈，Stack[0]存储栈顶位置 node *t = T->root; //当处理一个结点时，做如下处理 while(1) { //访问这个结点 cout<<t->key<<‘ ‘; //入栈 Push(Stack, *t); //如果有左孩子，下一步处理其左孩子 if(t->left) t = t->left; //如果没有左孩子 else { do{ //弹出栈顶元素 t = Pop(Stack); //若栈中元素已经全部弹出，那么二叉树访问结束了 if(t == NULL) { cout<<endl; return; } } //如果这个栈顶元素没有右孩子，则继续出栈，直到访问结束或找到一个有右孩子的元素 while(t->right == NULL); //如果这个栈顶元素有右孩子，则访问其右孩子 t = t->right; } }}/*input:0=NIL12 7 315 8 04 10 010 5 92 0 018 1 47 0 014 6 221 0 05 0 0*/int
main(){ //构造一棵树按照10.4-1 int
i; node A[11];//这个数组仅仅用于构造10.4-1中的树，在遍历时不使用 for(i = 1; i <= 10; i++) { int
key, left, right; cin>>key>>left>>right; A[i].key = key; if(left) A[i].left = &A[left]; else
A[i].left = NULL; if(right) A[i].right = &A[right]; else
A[i].right = NULL; } //生成一棵树 tree *T = new
tree(); T->root = &A[6]; //10.4-2，递归方式 Tree_Print(T); //10.4-3，非递归方式 Tree_Print2(T); return
0;} |
原文：http://www.cnblogs.com/rolling-stone/p/3667227.html