10.4-5 给定一个n结点的二叉树，写出一个$O(n)$时间的非递归过程，将该树的每一个结点的关键字输出。要求除该树本身的存储空间外只能使用固定量的额外存储空间，且中过程中不得修改该树，即使是暂时的修改也不允许。
要完成$O(1))$的空间内遍历该树，需要每个结点需要能访问其父节点进行回溯。
1
2
3
4
5
6
7
| struct Tree
{
Tree *parent;
Tree *left;
Tree *right;
int key;
};
|
中序遍历：
- 访问左孩子
- 访问右孩子
- 从左孩子返回，访问根节点，进入右孩子访问
- 从右孩子返回，整棵树访问完成，回溯直到为根节点或该结点是父节点的左孩子
下面是测试代码：
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
| #include<iostream>
#include<stack>
using namespace std;
#define NIL -1
struct Tree
{
Tree* left;
Tree* right;
Tree* parent;
int key;
Tree():left(nullptr),right(nullptr),parent(nullptr){}
};
void print(const Tree* t)
{
cout << t->key << " ";
}
void createTree(Tree *&t)
{
int key;
cin >> key;
if(key==NIL){
t=nullptr;
return;
}
t=new Tree();
t->key=key;
createTree(t->left);
createTree(t->right);
if(t->left)
t->left->parent=t;
if(t->right)
t->right->parent=t;
}
void inorder_travel(Tree *h)
{
if(h)
{
inorder_travel(h->left);
print(h);
norder_travel(h->right);
}
}
void inorder_byStack(Tree*h)
{
stack<Tree*> sta;
Tree *p=h;
while(p || !sta.empty())
{
while(p)
{
sta.push(p);
p=p->left;
}
p=sta.top();sta.pop();
print(p);
p=p->right;
}
}
void inorder_noStack(Tree* h)
{
if(!h)return;
Tree* pre=nullptr;
while(true)
{
if(pre!=h->left)
{
while(h->left)
h=h->left;
}
print(h);
if(h->right){
h=h->right;
continue;
}
do{
pre=h;
h=h->parent;
if(h==nullptr)
return;
}while(pre==h->right);
}
}
int main()
{
Tree* head;
createTree(head);
inorder_travel(head);
cout << endl;
inorder_byStack(head);
cout << endl;
inorder_noStack(head);
}
|
测试数据:
1 2 4 7 -1 -1 -1 5 8 -1 -1 -1 3 6 -1 9 -1 -1 -1
树的形状是：
中序遍历结果：
7 4 2 8 5 1 6 9 3
