数据结构B树3.ppt

文档介绍：树和森林
一、双亲表示法(顺序存储)
//-----------树的双亲表存储表示----------//
#define MAX_TREE_SIZE 100
typedef struct PTNode {
TElemType data;
int parent; //双亲位置域
}PTNode;
typedef struct{
PTNode nodes[MAX_TREE_SIZE];
int n; //结点数
}PTree;
双亲表示法举例
R
A
D
E
F
C
B
G
K
H
R -1
A 0
B 0
C 0
D 1
E 1
F 3
G 6
H 6
K 6
0
1
2
3
4
5
6
7
8
9
数组下标:
* 便于涉及双亲的操作;
* 求结点的孩子时需要遍历整棵树。
二、孩子表示法(顺序存储)
#define MAX_TREE_SIZE 100
typedef struct PTNode {
TElemType data;
int child1; //第1个孩子位置域
int child2; //第2个孩子位置域
......
int childd; //第d个孩子位置域
}PTNode;
typedef struct{
PTNode nodes[MAX_TREE_SIZE];
int n; //结点数
}PTree;
孩子表示法举例
R
A
D
E
F
C
B
G
K
H
0
1
2
3
4
5
6
7
8
9
数组下标:
* 便于涉及孩子的操作;求双亲不方便;
* 采用同构的结点,空间浪费。
R 1
A 4
B 0
C 6
D 0
E 0
F 7
G 0
H 0
K 0
2 3
5 0
0 0
0 0
0 0
0 0
8 9
0 0
0 0
0 0
孩子链表存储表示(链式存储)
typedef struct CTNode{ //孩子结点
int child;
struct CTNode *next;
} *ChildPtr;
typedef struct {
TElemType data;
ChildPtr firstchild; //孩子链表头指针
}CTBox;
typedef struct {
CTBox nodes[MAX_TREE_SIZE];
int n, r; //结点数和根的位置
}CTree;
孩子链表存储表示举例
R
A
D
E
F
C
B
G
K
H
0
1
2
3
4
5
6
7
8
9
数组下标:
* 便于涉及孩子的操作;
* 求结点的双亲时不方便。
R
A
B /
C
D /
E /
F
G /
H /
K /
1
2
3 /
4
5 /
6 /
7
8
9 /
[ ]; =10; = 0;
例1: 设树T以孩子链表为存储结构,寻找值为x的双亲结点的算法如下:
Status parent(Ctree T, TElemType x)
{// 当值为x的结点不存在时返回-2;
// 当值为x的结点为根结点时返回-1,
// 否则返回x结点的双亲结点的下标值.
if([].data == x) return –1;
//值为x的结点为根结点;
for(i=0;i<;i++)
{ p=[i].firstchild;
while(p && [p->child].data != x)
p = p->next;
if(p) return (i); // 找到x的双亲结点
}
return –2; // 值为x的结点不存在
}
例2: 删除值为x的结点的第i棵子树的算法delete如下:
void deletej(Ctree &T, int j)
{// 删除树T的第j号结点及其子树
if(![j].firstchild){ // 删除叶结点
for(i=j; i<-1; i++) { // j号结点后的结点全部前移一位
[i].data = [i+1].data;
[i].firstchild = [i+1].firstchild;
}
--;
}else{
while(s=[j].firstchild){
[j].firstchild = s->n