10 65
865
9761059 95 97.6
2009-7-28
2
1
2
3
A
B
A
B
2009-7-28
3
A,B,C,···· X,Y,Z
——
2009-7-28
4
1
2
3
A
B
A
B
2009-7-28
5
2009-7-28
6
A
B C
D
E F G H
——
H
B C D
E F G
A
2009-7-28
72.5
2.5.1
A
C
G
T2
D
H I
T3
J
M
B
E
LK
T1
F
2009-7-28
8
Node
Degree
Leaf
Child
Sibling
Parent
Depth)
ForestM
A
C
G
T2
D
H I
T3
J
M
B
E
LK
T1
F
2009-7-28
9
2.5.2 Binary Tree
1
(1)
2009-7-28
10
2009-7-28
11
A i 2 i-1 i?1
(2)
4
2 3
1
6 7
8 9 10 11 12 13 14 15
5
2009-7-28
12
A i 2 i-1 i?1
B h 2h-1
(2)
4
2 3
1
6 7
8 9 10 11 12 13 14 15
5
2009-7-28
13
A i 2 i-1 i?1
B h 2h-1
C n0
n2 2 n0=n2+1
(2)
4
2 3
1
6 7
8 9 10 11 12 13 14 15
5
2009-7-28
14
3
4
2 3
1
6 7
8 9 10 11 12 13 14 15
5
2009-7-28
15
4
2 3
1
6 7
8 9 10 11 12
5
4
4
2 3
1
6 7
8 9 10 11 12
5
2009-7-28
18
5
A 10
B2
C
2009-7-28
19
2
(2)
T[16]
i2*i2*i+1
11
A
B
c
FE
D
1
2
4
8 9 10
5 6
3
7
12 13 14 15
(1)
(1)
2h-1= 24-1 = 15
0000FE000DC0BA
1514131211109876543210
0
2009-7-28
20
(2)
lchild Data rchild
A ^
D
B
^ C ^
^ E ^ ^ F ^
A
E
C
B
D
F
2009-7-28
21
Typedef struct BiTNode{
int data;
Struct BiTNode *lchild,*rchild;
} BiTNode,* BiTree;
lchild Data rchild
lchild Data rchild lchild Data rchild
2009-7-28
22
3
1
·
·
·
· 45
2009-7-28
23
I
A
B C D
E F G H
(b)
A
B C D
E G HF I
(a)
A
B
E
F
C
D
G
H
I
(d)
A
B C D
E F G H I
(c)
2009-7-28
24
2
A
DCB
E
F H I
G
J
E
F
A
D
C
B H
I
G
J
A
D
C
B
E
F
H
I
G
J
A
D
C
B
E
F
H
I
G
J
·
·
·
2009-7-28
254
1
(D L R):
(L D R):
(L R D):
2009-7-28
26
2
D L R
L D R
L R D
A
D
B C
T1
T2
T3
D L R
A
D L R
D L R
B
D
C
D L R
ABDC
BDAC
DBCA
2009-7-28
27
Void PreOderTraverse(BiTree T){
if(T! =NULL){
printf (T->data);
PreOrderTraverse(T->lchild);
PreOrderTraverser(T->rchild); }
}/**/
Pre( T )
pre(T R);
pre(T R);
A
CB
D
T B
printf(B);
pre(T L);
T A
printf(A);
pre(T L);
T D
printf(D);
pre(T L);
T C
printf(C);
pre(T L);
T
pre(T R);
T
T
T
T
pre(T R);
2009-7-28
28
void inOrderTraverse(BiTree T)
{ if(T!=NULL)
{ inOrderTraverse(T->lchild);
printf(T->data);
inOrderTraverse(T->rchild);
}
}
void PostOrderTraverse(BiTree T)
{ if(T!=NULL)
{ PostOrderTraverse(T->lchild);
PostOrderTraverse(T->rchild);
printf(T->data);
}
}
2009-7-28
293
1) (
BiTree CreatBiTree()
{ BiTree T;
scanf(&ch);
if(ch= =) T=NULL;
else{
T=(BiTNode?)malloc(sizeof((BiTNode));
T->data=ch; /**/
T->lchild= CreatBiTree( ); /**/
T->rchild= CreatBiTree(); /**/
}
return (T) ;}
A
D
B C
A B D C
A B Φ D Φ Φ C Φ Φ
2009-7-28
30
ch=A
T
T
A
creat(T L)
Λ
T= Λ,Creat(T)
creat(T R) T
ch=Φ
DΛ
||
=
creat(T R)
D
=T
ch=Φ
ΛΛ
ch=D
T
T
D
creat(T L)
=||
Φ
Φ
creat(T R)
ch=C
T
T
C
creat(T L)
– +
ch=B
T
T
B
creat(T L)
T
ch=Φ
BΛ
T
CΛ
ch=Φ
–
+
creat(T R) T
CΛ
ch=Φ
Λ
+
AT
A
BΛ
A
BΛ
D|| =
A
BΛ
Λ Λ
A
BΛ
DΛ Λ
C– +B
A
BΛ
DΛ Λ
CΛ Λ
2009-7-28
312
1
int countleaf(BiTree)
{ int n1,n2;
if (T= =NULL) return(0);
else if (T->lchild= =NULL) && (T->rchild= =NULL)
return(1);
else { n1=countleaf (T->lchild);
n2=countleaf (T->rchild);
return( n1+n2);
}
}
2009-7-28
32
void change(NODE *T)
{NODE *m;
if(T!=NULL)
{ m=T->L
T->L=T->R;
T->R=m;
change(T->L);
change(T->R);}
}
typedef struct node{
int data
struct node *L*R
}NODE
A
B C
D
A
C B
D
A
C B
D
21.
2009-7-28
33
1
2
typedef struct BiTNode{
int data;
struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
int preprn(BiTtree T)
{
if((T->lchild!=NULL)&& T->rchild!=NULL ) {
printf(T->data);
preprn(T->lchild);
preprn(T->rchild);
}
else return OK;
}
a
b
d e
c
gf
h i
a b c g
2009-7-28
34
2009-7-28
35
ai-1a1 ai anPa
b2b1Pb
ai-1a1 b1 aiC
2009-7-28
36
2009-7-28
37
2009-7-28
38
ai-1a1 ai anPa
b2b1Pb
2009-7-28
39
ai-1a1 ai anPa
b2b1Pb
b1
2009-7-28
40
b1
ai-1a1 ai anPa
b2b1Pb
2009-7-28
41
b1
ai-1a1 ai anPa
b2b1 Pb
2009-7-28
42
ai-1a1 ai anPa
b2b1Pb
a1
2009-7-28
43
ai-1a1 ai an
Pa
b2b1Pb
a1
2009-7-28
44
ai-1a1 ai an
Pa
b2b1
Pb
a1
2009-7-28
45
ai-1a1 ai an
Pa
b2b1
Pb
a1
2009-7-28
46
ai-1a1 ai an
Pa
b2b1
Pb
a1
2009-7-28
47
ai-1a1 ai an
Pa
b2b1
Pb
a1
2009-7-28
48
ai-1a1 ai an
Pa
b2b1
Pb
a1
a2
2009-7-28
49
ai-1a1 ai an
Pa
b2b1
Pb
a1
a2
2009-7-28
50
ai-1a1 ai an
Pa
b2b1
Pb
a1
a2
2009-7-28
51
ai-1a1 ai an
Pa
b2b1
Pb
a1
a2
2009-7-28
52
ai-1a1 ai an
Pa
b2b1
Pb
a1
a2
2009-7-28
53
ai-1a1 ai an
Pa
b2b1
Pb
a1
a2
b1
2009-7-28
54
ai-1a1 ai an
Pa
b2b1
Pb
a1
a2
b1
2009-7-28
55
ai-1a1 ai an
Pa
b2b1
Pb
a1
a2
b1
2009-7-28
56
2009-7-28
57
2009-7-28
58
a1
a2
b1
2009-7-28
59
a1
a2
b1
2009-7-28
60
a1
a2
b1
2009-7-28
61
a1
a2
b1
2009-7-28
62
a1
a2
b1
2009-7-28
63
2009-7-28
64
2009-7-28
65
2009-7-28
66
2009-7-28
67
2009-7-28
68
― ‖
‖
2009-7-28
69
― ‖
‖
2009-7-28
70
― ‖
‖
2009-7-28
71
― ‖
‖
2009-7-28
72
― ‖
‖
2009-7-28
73
― ‖
‖
15
2009-7-28
74
― ‖
‖
15
2009-7-28
75
― ‖
‖
15
2009-7-28
76
― ‖
‖
15
2009-7-28
77
― ‖
‖
15
2009-7-28
78
― ‖
‖
15
2009-7-28
79
― ‖
‖
15
23
2009-7-28
80
― ‖
‖
15
23
2009-7-28
81
― ‖
‖
15
23
2009-7-28
82
― ‖
‖
15
23
2009-7-28
83
― ‖
‖
15
23
2009-7-28
84
― ‖
‖
15
23
3
2009-7-28
85
― ‖
‖
15
3
23
2009-7-28
86
― ‖
‖
15
3
23
2009-7-28
87
― ‖
‖
15
3
23
2009-7-28
88
― ‖
‖
15
3
23
2009-7-28
89
― ‖
‖
15
3
23
2009-7-28
90
― ‖
‖
15
3
23
0
2009-7-28
91
― ‖
‖
15
23
0
3
2009-7-28
92
― ‖
‖
15
23
0
3
2009-7-28
93
― ‖
‖
15
23
3
2009-7-28
94
3
865
9761059 95 97.6
2009-7-28
2
1
2
3
A
B
A
B
2009-7-28
3
A,B,C,···· X,Y,Z
——
2009-7-28
4
1
2
3
A
B
A
B
2009-7-28
5
2009-7-28
6
A
B C
D
E F G H
——
H
B C D
E F G
A
2009-7-28
72.5
2.5.1
A
C
G
T2
D
H I
T3
J
M
B
E
LK
T1
F
2009-7-28
8
Node
Degree
Leaf
Child
Sibling
Parent
Depth)
ForestM
A
C
G
T2
D
H I
T3
J
M
B
E
LK
T1
F
2009-7-28
9
2.5.2 Binary Tree
1
(1)
2009-7-28
10
2009-7-28
11
A i 2 i-1 i?1
(2)
4
2 3
1
6 7
8 9 10 11 12 13 14 15
5
2009-7-28
12
A i 2 i-1 i?1
B h 2h-1
(2)
4
2 3
1
6 7
8 9 10 11 12 13 14 15
5
2009-7-28
13
A i 2 i-1 i?1
B h 2h-1
C n0
n2 2 n0=n2+1
(2)
4
2 3
1
6 7
8 9 10 11 12 13 14 15
5
2009-7-28
14
3
4
2 3
1
6 7
8 9 10 11 12 13 14 15
5
2009-7-28
15
4
2 3
1
6 7
8 9 10 11 12
5
4
4
2 3
1
6 7
8 9 10 11 12
5
2009-7-28
18
5
A 10
B2
C
2009-7-28
19
2
(2)
T[16]
i2*i2*i+1
11
A
B
c
FE
D
1
2
4
8 9 10
5 6
3
7
12 13 14 15
(1)
(1)
2h-1= 24-1 = 15
0000FE000DC0BA
1514131211109876543210
0
2009-7-28
20
(2)
lchild Data rchild
A ^
D
B
^ C ^
^ E ^ ^ F ^
A
E
C
B
D
F
2009-7-28
21
Typedef struct BiTNode{
int data;
Struct BiTNode *lchild,*rchild;
} BiTNode,* BiTree;
lchild Data rchild
lchild Data rchild lchild Data rchild
2009-7-28
22
3
1
·
·
·
· 45
2009-7-28
23
I
A
B C D
E F G H
(b)
A
B C D
E G HF I
(a)
A
B
E
F
C
D
G
H
I
(d)
A
B C D
E F G H I
(c)
2009-7-28
24
2
A
DCB
E
F H I
G
J
E
F
A
D
C
B H
I
G
J
A
D
C
B
E
F
H
I
G
J
A
D
C
B
E
F
H
I
G
J
·
·
·
2009-7-28
254
1
(D L R):
(L D R):
(L R D):
2009-7-28
26
2
D L R
L D R
L R D
A
D
B C
T1
T2
T3
D L R
A
D L R
D L R
B
D
C
D L R
ABDC
BDAC
DBCA
2009-7-28
27
Void PreOderTraverse(BiTree T){
if(T! =NULL){
printf (T->data);
PreOrderTraverse(T->lchild);
PreOrderTraverser(T->rchild); }
}/**/
Pre( T )
pre(T R);
pre(T R);
A
CB
D
T B
printf(B);
pre(T L);
T A
printf(A);
pre(T L);
T D
printf(D);
pre(T L);
T C
printf(C);
pre(T L);
T
pre(T R);
T
T
T
T
pre(T R);
2009-7-28
28
void inOrderTraverse(BiTree T)
{ if(T!=NULL)
{ inOrderTraverse(T->lchild);
printf(T->data);
inOrderTraverse(T->rchild);
}
}
void PostOrderTraverse(BiTree T)
{ if(T!=NULL)
{ PostOrderTraverse(T->lchild);
PostOrderTraverse(T->rchild);
printf(T->data);
}
}
2009-7-28
293
1) (
BiTree CreatBiTree()
{ BiTree T;
scanf(&ch);
if(ch= =) T=NULL;
else{
T=(BiTNode?)malloc(sizeof((BiTNode));
T->data=ch; /**/
T->lchild= CreatBiTree( ); /**/
T->rchild= CreatBiTree(); /**/
}
return (T) ;}
A
D
B C
A B D C
A B Φ D Φ Φ C Φ Φ
2009-7-28
30
ch=A
T
T
A
creat(T L)
Λ
T= Λ,Creat(T)
creat(T R) T
ch=Φ
DΛ
||
=
creat(T R)
D
=T
ch=Φ
ΛΛ
ch=D
T
T
D
creat(T L)
=||
Φ
Φ
creat(T R)
ch=C
T
T
C
creat(T L)
– +
ch=B
T
T
B
creat(T L)
T
ch=Φ
BΛ
T
CΛ
ch=Φ
–
+
creat(T R) T
CΛ
ch=Φ
Λ
+
AT
A
BΛ
A
BΛ
D|| =
A
BΛ
Λ Λ
A
BΛ
DΛ Λ
C– +B
A
BΛ
DΛ Λ
CΛ Λ
2009-7-28
312
1
int countleaf(BiTree)
{ int n1,n2;
if (T= =NULL) return(0);
else if (T->lchild= =NULL) && (T->rchild= =NULL)
return(1);
else { n1=countleaf (T->lchild);
n2=countleaf (T->rchild);
return( n1+n2);
}
}
2009-7-28
32
void change(NODE *T)
{NODE *m;
if(T!=NULL)
{ m=T->L
T->L=T->R;
T->R=m;
change(T->L);
change(T->R);}
}
typedef struct node{
int data
struct node *L*R
}NODE
A
B C
D
A
C B
D
A
C B
D
21.
2009-7-28
33
1
2
typedef struct BiTNode{
int data;
struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
int preprn(BiTtree T)
{
if((T->lchild!=NULL)&& T->rchild!=NULL ) {
printf(T->data);
preprn(T->lchild);
preprn(T->rchild);
}
else return OK;
}
a
b
d e
c
gf
h i
a b c g
2009-7-28
34
2009-7-28
35
ai-1a1 ai anPa
b2b1Pb
ai-1a1 b1 aiC
2009-7-28
36
2009-7-28
37
2009-7-28
38
ai-1a1 ai anPa
b2b1Pb
2009-7-28
39
ai-1a1 ai anPa
b2b1Pb
b1
2009-7-28
40
b1
ai-1a1 ai anPa
b2b1Pb
2009-7-28
41
b1
ai-1a1 ai anPa
b2b1 Pb
2009-7-28
42
ai-1a1 ai anPa
b2b1Pb
a1
2009-7-28
43
ai-1a1 ai an
Pa
b2b1Pb
a1
2009-7-28
44
ai-1a1 ai an
Pa
b2b1
Pb
a1
2009-7-28
45
ai-1a1 ai an
Pa
b2b1
Pb
a1
2009-7-28
46
ai-1a1 ai an
Pa
b2b1
Pb
a1
2009-7-28
47
ai-1a1 ai an
Pa
b2b1
Pb
a1
2009-7-28
48
ai-1a1 ai an
Pa
b2b1
Pb
a1
a2
2009-7-28
49
ai-1a1 ai an
Pa
b2b1
Pb
a1
a2
2009-7-28
50
ai-1a1 ai an
Pa
b2b1
Pb
a1
a2
2009-7-28
51
ai-1a1 ai an
Pa
b2b1
Pb
a1
a2
2009-7-28
52
ai-1a1 ai an
Pa
b2b1
Pb
a1
a2
2009-7-28
53
ai-1a1 ai an
Pa
b2b1
Pb
a1
a2
b1
2009-7-28
54
ai-1a1 ai an
Pa
b2b1
Pb
a1
a2
b1
2009-7-28
55
ai-1a1 ai an
Pa
b2b1
Pb
a1
a2
b1
2009-7-28
56
2009-7-28
57
2009-7-28
58
a1
a2
b1
2009-7-28
59
a1
a2
b1
2009-7-28
60
a1
a2
b1
2009-7-28
61
a1
a2
b1
2009-7-28
62
a1
a2
b1
2009-7-28
63
2009-7-28
64
2009-7-28
65
2009-7-28
66
2009-7-28
67
2009-7-28
68
― ‖
‖
2009-7-28
69
― ‖
‖
2009-7-28
70
― ‖
‖
2009-7-28
71
― ‖
‖
2009-7-28
72
― ‖
‖
2009-7-28
73
― ‖
‖
15
2009-7-28
74
― ‖
‖
15
2009-7-28
75
― ‖
‖
15
2009-7-28
76
― ‖
‖
15
2009-7-28
77
― ‖
‖
15
2009-7-28
78
― ‖
‖
15
2009-7-28
79
― ‖
‖
15
23
2009-7-28
80
― ‖
‖
15
23
2009-7-28
81
― ‖
‖
15
23
2009-7-28
82
― ‖
‖
15
23
2009-7-28
83
― ‖
‖
15
23
2009-7-28
84
― ‖
‖
15
23
3
2009-7-28
85
― ‖
‖
15
3
23
2009-7-28
86
― ‖
‖
15
3
23
2009-7-28
87
― ‖
‖
15
3
23
2009-7-28
88
― ‖
‖
15
3
23
2009-7-28
89
― ‖
‖
15
3
23
2009-7-28
90
― ‖
‖
15
3
23
0
2009-7-28
91
― ‖
‖
15
23
0
3
2009-7-28
92
― ‖
‖
15
23
0
3
2009-7-28
93
― ‖
‖
15
23
3
2009-7-28
94
3
