存档

文章标签 ‘code’

实验十  二叉树的基本操作

2008年5月28日 没有评论 596 views

Test10.cpp

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
#include
#include
#include
typedef char ElemType;
struct BTreeNode{
ElemType data;
BTreeNode* left;
BTreeNode* right;
};
#include “test9_stack.h”
#include “test10.h”
void main()
{
BTreeNode* bt;
InitBTree(bt);
char b[50];
cout<<"输入二叉树用广义表表示的字符串:"<
cin.getline(b,sizeof(b));
CreateBTree(bt,b);
PrintBTree(bt);
cout<
cout<<"前序:";
PreOrder(bt);
cout<
cout<<"中序:";
InOrder(bt);
cout<
cout<<"中序(非递归算法):";
InOrder_fdg(bt);
cout<
cout<<"后序:";
PostOrder(bt);
cout<
cout<<"按层:";
LevelOrder(bt);
cout<
ElemType x;
cout<<"输入一个待查字符:"<
cin>>x;
if(FindBTree(bt,x))
cout<<"查找字符"<<<"成功!"<
else
cout<<"查找字符"<<<"失败!"<
cout<<"深度:";
cout<<
if(ChangeBTree(bt)){
printf(“将二叉树中的所有结点的左右子树进行交换后: \n”);
PrintBTree(bt);
cout<
}
printf(“二叉树中的结点总数: %d \n”,CountBTree(bt));
BTreeNode* newbt;
newbt=CopyBTree(bt);
printf(“复制二叉树得新二叉树:\n”);
PrintBTree(newbt);
ClearBTree(bt);
ClearBTree(newbt);
}

Test10.h

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
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
void PreOrder(BTreeNode* BT)
{
if(BT!=NULL){
cout<data<<' ';
PreOrder(BT->left);
PreOrder(BT->right);
}
}
 
void InOrder(BTreeNode* BT)
{
if(BT!=NULL){
InOrder(BT->left);
cout<data<<' ';
InOrder(BT->right);
}
}
 
void PostOrder(BTreeNode* BT)
{
if(BT!=NULL){
PostOrder(BT->left);
PostOrder(BT->right);
cout<data<<' ';
}
}
 
void InitBTree(BTreeNode*& BT)
{
BT=NULL;
}
 
void CreateBTree(BTreeNode*& BT,char *a)
{
const int MaxSize=10;
BTreeNode*s[MaxSize];
int top=-1;
BT=NULL;
BTreeNode *p;
int k;
int i=0;
while(a[i])
{
switch(a[i]){
case ' ':
break;
case '(':
if(top==MaxSize-1){
cout<<"stack space needs increase!"<
exit(1);
}
top++;
s[top]=p;
k=1;
break;
case ')':
if(top==-1){
cout<<"二叉树广义表字符串错!"<
exit(1);
}
top–;
break;
case ',':
k=2;
break;
default:
p=new BTreeNode;
p->data=a[i];
p->left=p->right=NULL;
if(BT==NULL)
BT=p;
else{
if(k==1)
s[top]->left=p;
else
s[top]->right=p;
}
}
i++;
}
}
 
bool EmptyBTree(BTreeNode *BT)
{
return BT==NULL;
}
 
int DepthBTree(BTreeNode *BT)
{
if(BT==NULL)
return 0;
else{
int dep1=DepthBTree(BT->left);
int dep2=DepthBTree(BT->right);
if(dep1>dep2)
return dep1+1;
else
return dep2+1;
}
}
 
bool FindBTree(BTreeNode *BT,ElemType &x)
{
if(BT==NULL)
return false;
else{
if(BT->data==x){
x=BT->data;
return true;
}
else{
if(FindBTree(BT->left,x))
return true;
if(FindBTree(BT->right,x))
return true;
return false;
}
}
}
 
void PrintBTree(BTreeNode *BT)
{
if(BT!=NULL){
cout<data;
if(BT->left!=NULL||BT->right!=NULL){
cout<<'(';
PrintBTree(BT->left);
if(BT->right!=NULL)
cout<<',';
PrintBTree(BT->right);
cout<<')';
}
}
}
 
void ClearBTree(BTreeNode *&BT)
{
if(BT!=NULL){
ClearBTree(BT->left);
ClearBTree(BT->right);
delete BT;
BT=NULL;
}
}
 
void LevelOrder(BTreeNode* BT)
{
const int MaxSize=30;
BTreeNode* q[MaxSize];
int front=0,rear=0;
BTreeNode* p;
if(BT!=NULL){
rear=(rear+1)%MaxSize;
q[rear]=BT;
}
while(front!=rear){
front=(front+1)%MaxSize;
p=q[front];
cout< data<<' ';
if(p->left!=NULL){
rear=(rear+1)%MaxSize;
q[rear]=p->left;
}
if(p->right!=NULL){
rear=(rear+1)%MaxSize;
q[rear]=p->right;
}
}
}
 
void InOrder_fdg(BTreeNode* T)
{
Stack S;
BTreeNode* p=T;
InitStack(S);
while(p!=NULL||!EmptyStack(S)){
if(p!=NULL){
Push(S,p);
p=p->left;
}
else{
p=Pop(S);
cout< data<<' ';
p=p->right;
}
}
ClearStack(S);
}
 
int ChangeBTree(BTreeNode *BT)
{
BTreeNode* t;
if(BT==NULL||(BT->left==NULL && BT->right==NULL))
return 0;
t=BT->left;
BT->left=BT->right;
BT->right=t;
ChangeBTree(BT->left);
ChangeBTree(BT->right);
return 1;
}
 
int CountBTree(BTreeNode *BT)
{
int static count;
if(BT!=NULL){
count++;
CountBTree(BT->left);
CountBTree(BT->right);
}
return count;
}
 
BTreeNode * CopyBTree(BTreeNode *BT)
{
 
if(BT==NULL) return NULL;
else {
BTreeNode* pt=new BTreeNode;
pt->data=BT->data;
pt->left=CopyBTree(BT->left);
pt->right=CopyBTree(BT->right);
return pt;
}
}

Test9_stack.h

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
struct Stack{
BTreeNode* *stack; // 存栈元素
int top; // 栈顶指示器
int MaxSize; // 栈的最大长度
};
void InitStack (Stack &S) //构造一个空栈 S
{
S.MaxSize=10;
S.stack=new BTreeNode*[S.MaxSize];
if(!S.stack){
cerr<<"fail"<
exit(1);
}
S.top=-1;
}
 
int EmptyStack (Stack S) //若栈S为空栈返回1,否则返回0
{
return S.top==-1;
}
 
void Push(Stack &S, BTreeNode* item) //元素 item进栈
{
if(S.top==S.MaxSize-1){
int k=sizeof(BTreeNode*);
S.stack=(BTreeNode**)realloc(S.stack,2*S.MaxSize*k);
S.MaxSize=2*S.MaxSize;
}
S.top++;
S.stack[S.top]=item;
}
 
BTreeNode* Pop(Stack &S) //栈S的栈顶元素出栈并返回
{
if(S.top==-1){
cerr<<"Stack is empty!"<
exit(1);
}
S.top;
return S.stack[S.top+1];
}
 
BTreeNode* Peek(Stack S) //取栈S的当前栈顶元素并返回
{
if(S.top==-1){
cerr<<"Stack is empty!"<
exit(1);
}
return S.stack[S.top];
}
 
void ClearStack (Stack &S) //清除栈s,使成为空栈
{
if(S.stack){
delete []S.stack;
S.stack=0;
}
S.top=-1;
S.MaxSize=0;
}
分类: IT 标签: , ,