资料-树的孩子兄弟表示法及相关操作(2)

CSTree p; 163

if(T) 164

{ 165

p=Point(T,e); 166

167 if(p) //p若有值，则证明存在且找到值为e的结点。 168

{ 169

p->data=value; 170

return OK; 171

} 172

} 173

174 return Nil; //不存在或树空。 175

} 176

177

TElemType Parent(CSTree T,TElemType e) 178

{ 179

CSTree p,t; 180

LinkQueue q; 181

InitQueue(q); 182

if(T) 183

{ 184

if(Value(T)==e) 185

186 return Nil; //根结点值为e，返回空。 187

EnQueue(q,T); 188

while(!QueueEmpty(q)) 189

190 {//遍历长子。 191

DeQueue(q,p); 192

193 if(p->firstchild) //有长子。 194

{ 195

if(p->firstchild->data==e) 196

return Value(p); 197

198 t=p; //双亲指针赋给t。 199

p=p->firstchild; 200

201 EnQueue(q,p); //长子指针入队。 202

while(p->nextsibling) 203

{ //长子有兄弟。遍历兄弟，查找是否有值为e的结点。 205

p=p->nextsibling; 206

if(Value(p)==e) 207

return Value(t); 208

EnQueue(q,p); 209

} 210

} 211

} 212

} 213

214 return Nil; //树空或者没找到。 215

} 216

217

TElemType LeftChild(CSTree T,TElemType e) 218

219 { //返回树T中结点值为e的长子。 220

CSTree f; 221

f=Point(T,e); 222

if(f&&f->firstchild) 223

return f->firstchild->data; 224

else 225

226 return Nil; //找不到或为叶结点。 227

} 228

229

TElemType RightSibling(CSTree T,TElemType e) 230

231 { //返回树T中结点值为e的右兄弟。 232

CSTree f; 233

f=Point(T,e); 234

if(f&&f->nextsibling) 235

return f->nextsibling->data; 236

else 237

return Nil; 238

} 239

240

Status InsertChild(CSTree &T,CSTree p,int i,CSTree c) 241

242 { // 初始条件: 树T存在,p指向T中某个结点,1≤i≤p所指结点的度243

244 +1,非空树c与T不相交 245

246 // 操作结果: 插入c为T中p结点的第i棵子树 247

// 因为p所指结点的地址不会改变，故p不需是引用类型 249

int j; 250

if(T) 251

{ 252

253 if(i==1) //c插入为p的长子。 254

{ 255

c->nextsibling=p->firstchild; 256

257 p->firstchild=c; //c成为p的长子，原长子成为c的兄258

259 弟。

} 260

else 261

{ 262

p=p->firstchild; 263

264 j=2; //插入标记，j==i时插入。 265

while(p&&j<i) 266

267 { //遍历p的兄弟。 268

p=p->nextsibling; 269

j++; 270

} 271

if(j==i) 272

273 {//找到了，插入。 274

c->nextsibling=p->nextsibling; 275

p->nextsibling=c; 276

} 277

else 278

279 return ERROR; //j！=i，说明p孩子树<i-1。 280

} 281

return OK; 282

} 283

284 else //树空。 285

return ERROR; 286

} 287

288

Status DeleteChild(CSTree &T,CSTree p,int i) 289

290 { // 初始条件: 树T存在,p指向T中某个结点,1≤i≤p所指结点的度 291

// 操作结果: 删除T中p所指结点的第i棵子树 293

294 // 因为p所指结点的地址不会改变，故p不需是引用类型 295

CSTree t; 296

int j; 297

if(T) 298

{ 299

if(i==1) 300

{ 301

t=p->firstchild; 302

p->firstchild=t->nextsibling; 303

t->nextsibling=NULL; 304

DestroyTree(t); 305

} 306

307 else //与插入算法类似。 308

{ 309

p=p->firstchild; 310

j=2; 311

while(p&&j<i) 312

{ 313

p=p->nextsibling; 314

j++; 315

} 316

if(j==i) 317

{ 318

t=p->nextsibling; 319

p->nextsibling=t->nextsibling; 320

t->nextsibling=NULL; 321

DestroyTree(t); 322

} 323

else 324

return ERROR; 325

} 326

return OK; 327

} 328

else 329

return ERROR; 330

}

void PreOrderTraverse(CSTree T,void(*Visit)(TElemType)) { //先根遍历树T。

if(T)

{

Visit(Value(T));

PreOrderTraverse(T->firstchild,Visit);

PreOrderTraverse(T->nextsibling,Visit);

}

}

void PostOrderTraverse(CSTree

T,void(*Visit)(TElemType))

{ //后根遍历树T。

CSTree p;

if(T)

{

if(T->firstchild)

{

PostOrderTraverse(T->firstchild,Visit);//先后根遍历长子子树。

p=T->firstchild->nextsibling;

while(p)

{ //再后根遍历所有兄弟子树。

PostOrderTraverse(p,Visit);

p=p->nextsibling;

}

}

Visit(Value(T)); //最后访问根结点。

}

}

void LevelOrderTraverse(CSTree

T,void(*Visit)(TElemType))

{ //层序遍历树T。

CSTree p;

LinkQueue q;

InitQueue(q);

if(T)

{

Visit(Value(T)); //先访问根结点。

EnQueue(q,T);

while(!QueueEmpty(q))

{ //访问

DeQueue(q,p);

if(p->firstchild)

{ //访问当前结点的长子。。

p=p->firstchild;

Visit(Value(p));

EnQueue(q,p);//长子入队。

while(p->nextsibling)

{//遍历该长子所有的兄弟。

p=p->nextsibling;

Visit(Value(p));

EnQueue(q,p); //所有兄弟入队。

}

}

}

}

}

[Copy to clipboard]View Code CPP

1 // Chileren-Sibling-Tree-Main-Test.cpp 树的孩子兄弟存储表2

3 示的相关检验。

4

5 #include"basic.h"

6 typedef char TElemType;

7 TElemType Nil=' ';

8 #include"Children-Sibling-Tree-define.h"

9 #include"Children-Sibling-Tree-operations.h"

1

0 void vi(TElemType c)

1{

1 printf("%c ",c);

1}

2

1int main()

3 {

1 int i;

4 CSTree T,p,q;

1 TElemType e,e1;

5 InitTree(T);

1 printf("构造空树后，树空否？%d …… 此处隐藏：2901字，全部文档内容请下载后查看。喜欢就下载吧 ……