王道数据结构课本学习--第五章 树与二叉树--以下代码由C语言实现
知识框架
树的基本概念
树的定义
树是n (n≥0)个节点的有限集。当n=0时，称为空树。在任意一棵非空树中应满足:
1）有且仅有一个特定的称为根的结点。
2)当n>1时，其余节点可分为m (m>0)个互不相交的有限集T,T2…,Tm，其中每个集合本身又是一棵树，并且称为根的子树。
显然，树的定义是递归的，即在树的定义中又用到了其自身，树是一种递归的数据结构。树作为一种逻辑结构，同时也是一种分层结构，具有以下两个特点:
1）树的根结点没有前驱，除根结点外的所有结点有且只有一个前驱。
2）树中所有结点可以有零个或多个后继。
树适合于表示具有层次结构的数据。树中的某个结点（除根结点外）最多只和上一层的一个结点(即其父结点)有直接关系，根结点没有直接上层结点，因此在n个结点的树中有n-1条边。而树中每个结点与其下一层的零个或多个结点（即其子女结点）有直接关系。
基本术语
1）考虑结点K。根A到结点K的唯一路径上的任意结点，称为结点K的祖先。如结点B是结点K的祖先，而结点K是结点B的子孙。路径上最接近结点K的结点E称为K的双亲，而K为结点E的孩子。根A是树中唯一没有双亲的结点。有相同双亲的结点称为兄弟，如结点K和结点L有相同的双亲E,即K和L为兄弟。
2）树中一个结点的孩子个数称为该结点的度，树中结点的最大度数称为树的度。如结点B的度为2，结点D的度为3，树的度为3。
3）度大于0的结点称为分支结点(又称非终端结点);度为0(没有子女结点）的结点称为叶子结点(又称终端结点)。在分支结点中，每个结点的分支数就是该结点的度。
4)结点的深度、高度和层次。结点的层次从树根开始定义，根结点为第1层，它的子结点为第2层，以此类推。双亲在同一层的结点互为堂兄弟，图5.1中结点G与E,F,H,I,J互为堂兄弟。
结点的深度是从根结点开始自顶向下逐层累加的。
结点的高度是从叶结点开始自底向上逐层累加的。
树的高度或深度）是树中结点的最大层数。图5.1中树的高度为4。
5）有序树和无序树。树中结点的各子树从左到右是有次序的，不能互换，称该树为有序树，否则称为无序树。假设图5.1为有序树，若将子结点位置互换，则变成一棵不同的树。
6）路径和路径长度。树中两个结点之间的路径是由这两个结点之间所经过的结点序列构成的，而路径长度是路径上所经过的边的个数。
注意:由于树中的分支是有向的，即从双亲指向孩子，所以树中的路径是从上向下的，同一双亲的两个孩子之间不存在路径。
7）森林。森林是m(m≥0）棵互不相交的树的集合。森林的概念与树的概念十分相近因为只要把树的根结点删去就成了森林。反之，只要给m棵独立的树加上一个结点，并把这m棵树作为该结点的子树，则森林就变成了树。
树的性质
二叉树的概念
二叉树的定义及其主要特性
二叉树与度为2的有序树的区别：
①度为2的树至少有3个结点，而二叉树可以为空。
②度为2的有序树的孩子的左右次序是相对于另一孩子而言的，若某个结点只有一个孩子，则这个孩子就无须区分其左右次序，而二叉树无论其孩子数是否为2.均需确定其左右次序，即二叉树的结点次序不是相对于另一结点而言，而是确定的。)
特殊的二叉树
二叉树的性质
二叉树的存储结构
顺序存储
//二叉树--顺序存储--适合完全二叉树
#include <stdio.h>
#define MAXSIZE 100
struct TreeNode{
//结点中的数据元素
int value;
//判断结点是否为空 0为空 1不为空
int isEmpty;
};
typedef struct TreeNode TreeNode;
/*
初始化tree
*/
void initTree(TreeNode *tree){
int i=1;
for(;i<=MAXSIZE-1;i++){
tree[i].isEmpty=0;
}
}
/*
输出初始化的结果
*/
void printfInitTree(TreeNode tree[]){
int i=1;
for(;i<=MAXSIZE-1;i++){
printf("%%d,",tree[i].isEmpty);
}
}
int main(){
TreeNode tree[MAXSIZE];
initTree(tree);
printfInitTree(tree);
tree[1].value=1;
tree[1].isEmpty=1;
tree[2].value=2;
tree[2].isEmpty=1;
tree[3].value=3;
tree[3].isEmpty=1;
tree[4].value=4;
tree[4].isEmpty=1;
tree[5].value=5;
tree[5].isEmpty=1;
tree[6].value=6;
tree[6].isEmpty=1;
tree[7].value=7;
tree[7].isEmpty=1;
tree[8].value=8;
tree[8].isEmpty=1;
tree[9].value=9;
tree[9].isEmpty=1;
tree[10].value=10;
tree[10].isEmpty=1;
tree[11].value=11;
tree[11].isEmpty=1;
tree[12].value=12;
tree[12].isEmpty=1;
return 0;
}
- 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
链式存储
二叉树先、中、后遍历
层次遍历
遍历序列构造二叉树
代码阶段性总结
以下代码所用的二叉树如下图
//二叉树--链式存储
#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 100
struct BiTNode{
//数据域
int value;
//左孩子
struct BiTNode *lChild;
//右孩子
struct BiTNode *rChild;
};
typedef struct BiTNode BiTNode;
typedef struct BiTNode* BiTree;
struct LinkNode{
BiTNode* data;
struct LinkNode *next;
};
typedef struct LinkNode LinkNode;
struct LinkQueue{
LinkNode *front;
LinkNode *rear;
};
typedef struct LinkQueue LinkQueue;
/*
初始化tree
*/
BiTNode* initTree(BiTree root){
root=NULL;
return root;
}
/*
构造树
*/
BiTNode* constructTree(BiTree root){
BiTNode *p11=(BiTNode *)malloc(sizeof(BiTNode));
(*p11).value=11;
(*p11).lChild=NULL;
(*p11).rChild=NULL;
BiTNode *p12=(BiTNode *)malloc(sizeof(BiTNode));
(*p12).value=12;
(*p12).lChild=NULL;
(*p12).rChild=NULL;
BiTNode *p5=(BiTNode *)malloc(sizeof(BiTNode));
(*p5).value=5;
(*p5).lChild=NULL;
(*p5).rChild=p11;
BiTNode *p6=(BiTNode *)malloc(sizeof(BiTNode));
(*p6).value=6;
(*p6).lChild=p12;
(*p6).rChild=NULL;
BiTNode *p7=(BiTNode *)malloc(sizeof(BiTNode));
(*p7).value=7;
(*p7).lChild=NULL;
(*p7).rChild=NULL;
BiTNode *p2=(BiTNode *)malloc(sizeof(BiTNode));
(*p2).value=2;
(*p2).lChild=NULL;
(*p2).rChild=p5;
BiTNode *p3=(BiTNode *)malloc(sizeof(BiTNode));
(*p3).value=3;
(*p3).lChild=p6;
(*p3).rChild=p7;
BiTNode *p1=(BiTNode *)malloc(sizeof(BiTNode));
(*p1).value=1;
(*p1).lChild=p2;
(*p1).rChild=p3;
root=p1;
return root;
}
/*
先序遍历--根左右
*/
void preOrder(BiTree biTree){
if(biTree!=NULL){
printf("%%d ",(*biTree).value);
preOrder((*biTree).lChild);
preOrder((*biTree).rChild);
}
}
/*
中序遍历--左根右
*/
void inOrder(BiTree biTree){
if(biTree!=NULL){
inOrder((*biTree).lChild);
printf("%%d ",(*biTree).value);
inOrder((*biTree).rChild);
}
}
/*
后序遍历--左右根
*/
void postOrder(BiTree biTree){
if(biTree!=NULL){
postOrder((*biTree).lChild);
postOrder((*biTree).rChild);
printf("%%d ",(*biTree).value);
}
}
/*
树的深度
*/
int treeDepth(BiTree root){
if(root==NULL){
return 0;
}else{
int l=treeDepth((*root).lChild);
int r=treeDepth((*root).rChild);
return l>r?l+1:r+1;
}
}
/*
初始化队列
返回值
0--失败
1--成功
*/
int initQueue(LinkQueue *queue){
LinkNode *newNode=(LinkNode *)malloc(sizeof(LinkNode));
if(newNode==NULL){
return 0;
}
(*newNode).next=NULL;
(*queue).front=newNode;
(*queue).rear=newNode;
}
/*
入队操作
返回值
0--失败
1--成功
*/
int enQueue(LinkQueue *queue,BiTNode* data){
LinkNode *newNode=(LinkNode *)malloc(sizeof(LinkNode));
if(newNode==NULL){
return 0;
}
(*newNode).data=data;
(*newNode).next=NULL;
(*queue).rear->next=newNode;
(*queue).rear=newNode;
return 1;
}
/*
出队操作
*/
BiTNode* deQueue(LinkQueue *queue){
LinkNode *front=(*queue).front;
LinkNode *rear=(*queue).rear;
//被出队的结点--头结点的下一个结点
LinkNode *tmpNode=(*front).next;
BiTNode* result=(*tmpNode).data;
(*front).next=(*tmpNode).next;
if((*tmpNode).next==NULL){
(*queue).rear=front;
}
free(tmpNode);
return result;
}
/*
判断队列是否为空
1--为空
0--不为空
*/
int queueEmpty(LinkQueue queue){
if(queue.front==queue.rear){
return 1;
}else{
return 0;
}
}
/*
层次遍历
*/
void levelOrder(BiTree root){
if(root==NULL){
return ;
}
LinkQueue linkQueue;
initQueue(&linkQueue);
enQueue(&linkQueue,root);
BiTNode* p;
while(queueEmpty(linkQueue)==0){
p=deQueue(&linkQueue);
printf("%%d ",(*p).value);
if((*p).lChild!=NULL){
enQueue(&linkQueue,(*p).lChild);
}
if((*p).rChild!=NULL){
enQueue(&linkQueue,(*p).rChild);
}
}
}
BiTNode *tmpResult=NULL;
/*
利用先序遍历，找到某一节点，并赋值给tmpResult
*/
void preOrderTwo(BiTree biTree){
if(biTree!=NULL){
if((*biTree).value==5){
tmpResult=biTree;
}
preOrderTwo((*biTree).lChild);
preOrderTwo((*biTree).rChild);
}
}
/*
中序前驱
q-->当前被访问的结点
pre-->上一个被访问的结点
target-->求target结点的前驱
只要target==q，pre就是target的前驱结点
最后将pre赋值给tmpResult
*/
void inPreBiTNode(BiTree biTree,BiTNode *q,BiTNode *target){
BiTNode *pre=NULL;
if(biTree!=NULL){
inPreBiTNode((*biTree).lChild,q,target);
pre=q;
q=biTree;
if(q==target){
tmpResult=pre;
}
inPreBiTNode((*biTree).rChild,q,target);
}
}
/*
中序后继
q-->当前被访问的结点
pre-->上一个被访问的结点
target-->求target结点的前驱
只要target==pre，q就是target的后继结点
最后将q赋值给tmpResult
*/
void inNextBiTNode(BiTree biTree,BiTNode *q,BiTNode *target){
BiTNode *pre=NULL;
if(biTree!=NULL){
inNextBiTNode((*biTree).lChild,q,target);
pre=q;
q=biTree;
if(pre==target){
tmpResult=q;
}
inNextBiTNode((*biTree).rChild,q,target);
}
}
/*
先序前驱
*/
void prePreBiTNode(BiTree biTree,BiTNode *q,BiTNode *target){
BiTNode *pre=NULL;
if(biTree!=NULL){
pre=q;
q=biTree;
if(q==target){
tmpResult=pre;
}
prePreBiTNode((*biTree).lChild,q,target);
prePreBiTNode((*biTree).rChild,q,target);
}
}
/*
先序后继
*/
void preNextBiTNode(BiTree biTree,BiTNode *q,BiTNode *target){
BiTNode *pre=NULL;
if(biTree!=NULL){
pre=q;
q=biTree;
if(pre==target){
tmpResult=q;
}
preNextBiTNode((*biTree).lChild,q,target);
preNextBiTNode((*biTree).rChild,q,target);
}
}
/*
后序前驱
*/
void postPreBiTNode(BiTree biTree,BiTNode *q,BiTNode *target){
BiTNode *pre=NULL;
if(biTree!=NULL){
postPreBiTNode((*biTree).lChild,q,target);
postPreBiTNode((*biTree).rChild,q,target);
pre=q;
q=biTree;
if(q==target){
tmpResult=pre;
}
}
}
/*
后序后继
*/
void postNextBiTNode(BiTree biTree,BiTNode *q,BiTNode *target){
BiTNode *pre=NULL;
if(biTree!=NULL){
postNextBiTNode((*biTree).lChild,q,target);
postNextBiTNode((*biTree).rChild,q,target);
pre=q;
q=biTree;
if(pre==target){
tmpResult=q;
}
}
}
int main(){
BiTNode *q=NULL;
BiTree root;
root=initTree(root);
root=constructTree(root);
preOrder(root);
printf("
");
inOrder(root);
printf("
");
postOrder(root);
printf("
");
printf("%%d",treeDepth(root));
printf("
");
levelOrder(root);
printf("
");
preOrderTwo(root);
printf("
");
inPreBiTNode(root,q,tmpResult);
printf("结点5的中序前驱是：%%d",(*tmpResult).value);
printf("
");
preOrderTwo(root);
printf("
");
inNextBiTNode(root,q,tmpResult);
printf("结点5的中序后继是：%%d",(*tmpResult).value);
printf("
");
return 0;
}
- 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
- 226
- 227
- 228
- 229
- 230
- 231
- 232
- 233
- 234
- 235
- 236
- 237
- 238
- 239
- 240
- 241
- 242
- 243
- 244
- 245
- 246
- 247
- 248
- 249
- 250
- 251
- 252
- 253
- 254
- 255
- 256
- 257
- 258
- 259
- 260
- 261
- 262
- 263
- 264
- 265
- 266
- 267
- 268
- 269
- 270
- 271
- 272
- 273
- 274
- 275
- 276
- 277
- 278
- 279
- 280
- 281
- 282
- 283
- 284
- 285
- 286
- 287
- 288
- 289
- 290
- 291
- 292
- 293
- 294
- 295
- 296
- 297
- 298
- 299
- 300
- 301
- 302
- 303
- 304
- 305
- 306
- 307
- 308
- 309
- 310
- 311
- 312
- 313
- 314
- 315
- 316
- 317
- 318
- 319
- 320
- 321
- 322
- 323
- 324
- 325
- 326
- 327
- 328
- 329
- 330
- 331
- 332
- 333
- 334
- 335
- 336
- 337
- 338
- 339
- 340
- 341
- 342
- 343
- 344
- 345
- 346
- 347
- 348
- 349
- 350
- 351
- 352
- 353
- 354
- 355
- 356
- 357
- 358
- 359
- 360
- 361
- 362
- 363
- 364
- 365
- 366
- 367
- 368
- 369
- 370
- 371
- 372
- 373
- 374
- 375
- 376
- 377
- 378
- 379
- 380
- 381
- 382
- 383
- 384
- 385
- 386
- 387
- 388
- 389
- 390
- 391
- 392
- 393
- 394
- 395
- 396
- 397
- 398
- 399
- 400
- 401
- 402
- 403
- 404
- 405
- 406
- 407
- 408
- 409
- 410
- 411
- 412
- 413
- 414
- 415
- 416
- 417
- 418
- 419
- 420
- 421
- 422
- 423
- 424
- 425
- 426
- 427
- 428
- 429
- 430
- 431
- 432
- 433
- 434
- 435
- 436
- 437
- 438
- 439
- 440
- 441
- 442
- 443
线索二叉树
线索二叉树的概念
线索二叉树的构造
右指针存放的是后继，后继的确定是上一个结点pre确定，上一个结点早就遍历完了，所以不会出现循环现象
左指针存放的是前驱，先序的左是第二个遍历，如果左指针存放了根，接下来遍历左子树，就会造成循环；而中序和后序是先遍历左，所以不会造成循环
找前驱/后继
代码
中序线索二叉树
//二叉树--链式存储
#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 100
struct ThreadNode{
//数据域
int value;
//左孩子
struct ThreadNode *lChild;
//右孩子
struct ThreadNode *rChild;
//1--前驱结点 0--左孩子
int ltag;
//1--后继结点 0--右孩子
int rtag;
};
typedef struct ThreadNode ThreadNode;
typedef struct ThreadNode* ThreadTree;
/*
初始化tree
*/
ThreadTree* initTree(ThreadTree root){
root=NULL;
return root;
}
/*
构造树
*/
ThreadTree* constructTree(ThreadTree root){
ThreadNode *p11=(ThreadNode *)malloc(sizeof(ThreadNode));
(*p11).ltag=0;
(*p11).rtag=0;
(*p11).value=11;
(*p11).lChild=NULL;
(*p11).rChild=NULL;
ThreadNode *p12=(ThreadNode *)malloc(sizeof(ThreadNode));
(*p12).ltag=0;
(*p12).rtag=0;
(*p12).value=12;
(*p12).lChild=NULL;
(*p12).rChild=NULL;
ThreadNode *p5=(ThreadNode *)malloc(sizeof(ThreadNode));
(*p5).ltag=0;
(*p5).rtag=0;
(*p5).value=5;
(*p5).lChild=NULL;
(*p5).rChild=p11;
ThreadNode *p6=(ThreadNode *)malloc(sizeof(ThreadNode));
(*p6).ltag=0;
(*p6).rtag=0;
(*p6).value=6;
(*p6).lChild=p12;
(*p6).rChild=NULL;
ThreadNode *p7=(ThreadNode *)malloc(sizeof(ThreadNode));
(*p7).ltag=0;
(*p7).rtag=0;
(*p7).value=7;
(*p7).lChild=NULL;
(*p7).rChild=NULL;
ThreadNode *p2=(ThreadNode *)malloc(sizeof(ThreadNode));
(*p2).ltag=0;
(*p2).rtag=0;
(*p2).value=2;
(*p2).lChild=NULL;
(*p2).rChild=p5;
ThreadNode *p3=(ThreadNode *)malloc(sizeof(ThreadNode));
(*p3).ltag=0;
(*p3).rtag=0;
(*p3).value=3;
(*p3).lChild=p6;
(*p3).rChild=p7;
ThreadNode *p1=(ThreadNode *)malloc(sizeof(ThreadNode));
(*p1).ltag=0;
(*p1).rtag=0;
(*p1).value=1;
(*p1).lChild=p2;
(*p1).rChild=p3;
root=p1;
return root;
}
//指向当前被访问的结点
ThreadNode *q=NULL;
/*
创建中序线索二叉树
*/
void createInThread(ThreadTree root){
if(root!=NULL){
inThread(root);
if((*q).rChild==NULL){
(*q).rtag=1;
}
}
}
/*
中序线索二叉树
*/
void inThread(ThreadTree root){
ThreadNode *pre=NULL;
if(root!=NULL){
inThread((*root).lChild);
pre=q;
q=root;
if((*q).lChild==NULL){
(*q).lChild=pre;
(*q).ltag=1;
}
if(pre!=NULL&&(*pre).rChild==NULL){
(*pre).rChild=q;
(*pre).rtag=1;
}
inThread((*root).rChild);
}
}
/*
找到以p为根的子树中，第一个被中序遍历的结点
*/
ThreadNode* inFirstNode(ThreadNode *p){
//循环找到最左下结点（不一定是叶子结点）
while((*p).ltag==0){
p=(*p).lChild;
}
return p;
}
/*
中序线索二叉树中找到结点p的后继结点
*/
ThreadNode* inNextNode(ThreadNode *p){
//右子树中最左下结点
if((*p).rtag==0){
return inFirstNode((*p).rChild);
}else{
return (*p).rChild;
}
}
/*
对中序线索二叉树进行中序遍历（利用线索实现的非递归算法）
*/
void inOrder(ThreadTree root){
ThreadNode *p=inFirstNode(root);
for(;p!=NULL;p=inNextNode(p)){
printf("%%d ",(*p).value);
}
}
/*
找到以p为根的子树中，最后一个被中序遍历的结点
*/
ThreadNode* inLastNode(ThreadNode *p){
//循环找到最右下结点（不一定是叶子结点）
while((*p).rtag==0){
p=(*p).rChild;
}
return p;
}
/*
中序线索二叉树中找到结点p的前驱结点
*/
ThreadNode* inPreNode(ThreadNode *p){
//左子树中最右下结点
if((*p).ltag==0){
return inLastNode((*p).lChild);
}else{
return (*p).lChild;
}
}
/*
对中序线索二叉树进行逆中序遍历
*/
void revInOrder(ThreadTree root){
ThreadNode *p=inLastNode(root);
for(;p!=NULL;p=inPreNode(p)){
printf("%%d ",(*p).value);
}
}
int main(){
ThreadTree root;
root=initTree(root);
root=constructTree(root);
createInThread(root);
inOrder(root);
printf("
");
revInOrder(root);
return 0;
}
- 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
- 226
- 227
- 228
- 229
- 230
- 231
- 232
先序线索二叉树
//二叉树--链式存储
#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 100
struct ThreadNode{
//数据域
int value;
//左孩子
struct ThreadNode *lChild;
//右孩子
struct ThreadNode *rChild;
//1--前驱结点 0--左孩子
int ltag;
//1--后继结点 0--右孩子
int rtag;
};
typedef struct ThreadNode ThreadNode;
typedef struct ThreadNode* ThreadTree;
/*
初始化tree
*/
ThreadTree* initTree(ThreadTree root){
root=NULL;
return root;
}
/*
构造树
*/
ThreadTree* constructTree(ThreadTree root){
ThreadNode *p11=(ThreadNode *)malloc(sizeof(ThreadNode));
(*p11).ltag=0;
(*p11).rtag=0;
(*p11).value=11;
(*p11).lChild=NULL;
(*p11).rChild=NULL;
ThreadNode *p12=(ThreadNode *)malloc(sizeof(ThreadNode));
(*p12).ltag=0;
(*p12).rtag=0;
(*p12).value=12;
(*p12).lChild=NULL;
(*p12).rChild=NULL;
ThreadNode *p5=(ThreadNode *)malloc(sizeof(ThreadNode));
(*p5).ltag=0;
(*p5).rtag=0;
(*p5).value=5;
(*p5).lChild=NULL;
(*p5).rChild=p11;
ThreadNode *p6=(ThreadNode *)malloc(sizeof(ThreadNode));
(*p6).ltag=0;
(*p6).rtag=0;
(*p6).value=6;
(*p6).lChild=p12;
(*p6).rChild=NULL;
ThreadNode *p7=(ThreadNode *)malloc(sizeof(ThreadNode));
(*p7).ltag=0;
(*p7).rtag=0;
(*p7).value=7;
(*p7).lChild=NULL;
(*p7).rChild=NULL;
ThreadNode *p2=(ThreadNode *)malloc(sizeof(ThreadNode));
(*p2).ltag=0;
(*p2).rtag=0;
(*p2).value=2;
(*p2).lChild=NULL;
(*p2).rChild=p5;
ThreadNode *p3=(ThreadNode *)malloc(sizeof(ThreadNode));
(*p3).ltag=0;
(*p3).rtag=0;
(*p3).value=3;
(*p3).lChild=p6;
(*p3).rChild=p7;
ThreadNode *p1=(ThreadNode *)malloc(sizeof(ThreadNode));
(*p1).ltag=0;
(*p1).rtag=0;
(*p1).value=1;
(*p1).lChild=p2;
(*p1).rChild=p3;
root=p1;
return root;
}
//指向当前被访问的结点
ThreadNode *q1=NULL;
/*
创建先序线索二叉树
*/
void createPreThread(ThreadTree root){
if(root!=NULL){
preThread(root);
if((*q1).rChild==NULL){
(*q1).rtag=1;
}
}
}
/*
先序线索二叉树
*/
void preThread(ThreadTree root){
ThreadNode *pre=NULL;
if(root!=NULL){
pre=q1;
q1=root;
if((*q1).lChild==NULL){
(*q1).lChild=pre;
(*q1).ltag=1;
}
if(pre!=NULL&&(*pre).rChild==NULL){
(*pre).rChild=q1;
(*pre).rtag=1;
}
if((*root).ltag==0){
preThread((*root).lChild);
}
preThread((*root).rChild);
}
}
/*
找到以p为根的子树中，第一个被先序遍历的结点
*/
ThreadNode* preFirstNode(ThreadNode *p){
if(p!=NULL){
return p;
}
return NULL;
}
/*
先序线索二叉树中找到结点p的后继结点
*/
ThreadNode* preNextNode(ThreadNode *p){
//右指针存放的是后继，直接返回
if((*p).rtag==1){
return (*p).rChild;
}else{
//右指针存放的不是后继
//判断有没有左孩子，有直接返回，否则返回右孩子
if((*p).ltag==0){
return (*p).lChild;
}else{
return (*p).rChild;
}
}
}
int main(){
return 0;
}
- 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
后序线索二叉树
//二叉树--链式存储
#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 100
struct ThreadNode{
//数据域
int value;
//左孩子
struct ThreadNode *lChild;
//右孩子
struct ThreadNode *rChild;
//1--前驱结点 0--左孩子
int ltag;
//1--后继结点 0--右孩子
int rtag;
};
typedef struct ThreadNode ThreadNode;
typedef struct ThreadNode* ThreadTree;
/*
初始化tree
*/
ThreadTree* initTree(ThreadTree root){
root=NULL;
return root;
}
/*
构造树
*/
ThreadTree* constructTree(ThreadTree root){
ThreadNode *p11=(ThreadNode *)malloc(sizeof(ThreadNode));
(*p11).ltag=0;
(*p11).rtag=0;
(*p11).value=11;
(*p11).lChild=NULL;
(*p11).rChild=NULL;
ThreadNode *p12=(ThreadNode *)malloc(sizeof(ThreadNode));
(*p12).ltag=0;
(*p12).rtag=0;
(*p12).value=12;
(*p12).lChild=NULL;
(*p12).rChild=NULL;
ThreadNode *p5=(ThreadNode *)malloc(sizeof(ThreadNode));
(*p5).ltag=0;
(*p5).rtag=0;
(*p5).value=5;
(*p5).lChild=NULL;
(*p5).rChild=p11;
ThreadNode *p6=(ThreadNode *)malloc(sizeof(ThreadNode));
(*p6).ltag=0;
(*p6).rtag=0;
(*p6).value=6;
(*p6).lChild=p12;
(*p6).rChild=NULL;
ThreadNode *p7=(ThreadNode *)malloc(sizeof(ThreadNode));
(*p7).ltag=0;
(*p7).rtag=0;
(*p7).value=7;
(*p7).lChild=NULL;
(*p7).rChild=NULL;
ThreadNode *p2=(ThreadNode *)malloc(sizeof(ThreadNode));
(*p2).ltag=0;
(*p2).rtag=0;
(*p2).value=2;
(*p2).lChild=NULL;
(*p2).rChild=p5;
ThreadNode *p3=(ThreadNode *)malloc(sizeof(ThreadNode));
(*p3).ltag=0;
(*p3).rtag=0;
(*p3).value=3;
(*p3).lChild=p6;
(*p3).rChild=p7;
ThreadNode *p1=(ThreadNode *)malloc(sizeof(ThreadNode));
(*p1).ltag=0;
(*p1).rtag=0;
(*p1).value=1;
(*p1).lChild=p2;
(*p1).rChild=p3;
root=p1;
return root;
}
//指向当前被访问的结点
ThreadNode *q3=NULL;
/*
创建后序线索二叉树
*/
void createPostThread(ThreadTree root){
if(root!=NULL){
postThread(root);
if((*q3).rChild==NULL){
(*q3).rtag=1;
}
}
}
/*
后序线索二叉树
*/
void postThread(ThreadTree root){
ThreadNode *pre=NULL;
if(root!=NULL){
postThread((*root).lChild);
postThread((*root).rChild);
pre=q3;
q3=root;
if((*q3).lChild==NULL){
(*q3).lChild=pre;
(*q3).ltag=1;
}
if(pre!=NULL&&(*pre).rChild==NULL){
(*pre).rChild=q3;
(*pre).rtag=1;
}
}
}
/*
后序线索二叉树中找到结点p的前驱结点
*/
ThreadNode* postPreNode(ThreadNode *p){
//左指针存放的是前驱，直接返回
if((*p).ltag==1){
return (*p).ltag;
}else{
//左指针存放的不是前驱
//判断有没有右孩子，有直接返回，否则返回左孩子
if((*p).rtag==0){
return (*p).rtag;
}else{
return (*p).lChild;
}
}
}
int main(){
return 0;
}
- 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
树的存储结构
推荐阅读