# 最新2019-《数据结构》算法实现及解析

6.1 6.2
6.3 6.4
6.5 6.6
6.7 6.8

6.1

D
D
R
D : (1) Droot (2) n>1m (m>0)
T1, T2, ..., Tm
root

Root(T) // Value(T, cur_e) // Parent(T, cur_e) // LeftChild(T, cur_e) // RightSibling(T, cur_e) // TreeEmpty(T) // TreeDepth(T) // TraverseTree( T, Visit() ) //

InitTree(&T) //
CreateTree(&T, definition) //
Assign(T, cur_e, value) //
InsertChild(&T, &p, i, c) // cpi

ClearTree(&T) // DestroyTree(&T) //
DeleteChild(&T, &p, i) // pi

:

A

B

C

D

E

F GH I J

K

L

M

A( B(E, F(K, L)), C(G), D(H, I, J(M)) )

T1

T2

T3

() ()

()
()
(
)

()
()
(
)

: +

:

:

:

D

HI J

:

M

()

A

B

C

D

E F GH I J

K L

M

: 1l
l+1

mm0

F

root

A

B

C

D

E F GH I J

KL

M

Tree = rootF
root F

6.2

A

B

E

C

F

D

G HK

N

N

N

N

L

RL

R

Root(T); Value(T, e); Parent(T, e); LeftChild(T, e); RightChild(T, e); LeftSibling(T, e); RightSibling(T, e); BiTreeEmpty(T); BiTreeDepth(T); PreOrderTraverse(T, Visit()); InOrderTraverse(T, Visit()); PostOrderTraverse(T, Visit()); LevelOrderTraverse(T, Visit());

InitBiTree(&T); Assign(T, &e, value); CreateBiTree(&T, definition); InsertChild(T, p, LR, c);

ClearBiTree(&T); DestroyBiTree(&T); DeleteChild(T, p, LR);

1
i 2i-1 (i1)

i = 1 2i-1 = 20 = 1
j1 j i
i = 2i-2 2 = 2i-1

2
k 2k-1 k1

k
20+21+ +2k-1 = 2k-1

3
n0 n2 2 n0 = n2+1

n = n0 + n1 + n2 b = n1+2n2
b = n-1 = n0 + n1 + n2 - 1 n0 = n2 + 1

1

2

3

k2k-1 4 5 6 7

8 9 10 11 12 13 14 15

a

n 1 n

b de

c fg

hi j

4
n
log2n +1

k
2k-1 n < 2k k-1 log2 n < k
k k =log2n + 1

5
n 1 n i (1) i=1
i/2
(2) 2i>n 2i (3) 2i+1>n 2i+1

6.3

#define MAX_TREE_SIZE 100 //
typedef TElemType SqBiTree[MAX_ TREE_SIZE];
// 0 SqBiTree bt;

:

0
A

1

B

4

C

2
D
6
E
13
F

0 1 2 3 4 5 6 7 8 9 10 11 12 13

AB D C E

F

1. 2

3 4

1.
root
A
B C

: lchild data rchild
D E
F

C :
typedef struct BiTNode { // TElemType data; struct BiTNode *lchild, *rchild; //
} BiTNode, *BiTree;
: lchild data rchild

2

:

root

parent lchild data rchild

A B
C

D E
F

C :
typedef struct TriTNode { // TElemType data; struct TriTNode *lchild, *rchild; // struct TriTNode *parent; //
} TriTNode, *TriTree;
: parent lchild data rchild

3
0 B2L 1 C0R 2 A -1 3 D2R 4 E 3R 5 F 4L
6

: data parent LRTag

typedef struct BPTNode { //

TElemType data; int *parent; // char LRTag; //

} BPTNode typedef struct BPTree{ //

BPTNode nodes[MAX_TREE_SIZE];

int num_node; //

int root;

//

} BPTree

6.4

""

"" ()

""
1 2
3

1 2 3

1 2 3

1 2 3

void Preorder (BiTree T,

void( *visit)(TElemType& e))

{ //

if (T) {

visit(T->data);

//

Preorder(T->lchild, visit); //

Preorder(T->rchild, visit);//

}

}

BiTNode *GoFarLeft(BiTree T, Stack *S){ if (!T ) return NULL; while (T->lchild ){ Push(S, T); T = T->lchild; } return T;
}

void Inorder_I(BiTree T, void (*visit) (TelemType& e)){
Stack *S;
t = GoFarLeft(T, S); //
while(t){ visit(t->data); if (t->rchild) t = GoFarLeft(t->rchild, S);
else if ( !StackEmpty(S )) //
t = Pop(S); else t = NULL; //
} // while }// Inorder_I

1 ()
2() 3() 4

1
:
() "" "" 1

void CountLeaf (BiTree T, int& count){ if ( T ) { if ((!T->lchild)&& (!T->rchild)) count++; // CountLeaf( T->lchild, count); CountLeaf( T->rchild, count); } // if
} // CountLeaf

2() :

1 "" 1

int Depth (BiTree T ){ // if ( !T ) depthval = 0; else { depthLeft = Depth( T->lchild ); depthRight= Depth( T->rchild ); depthval = 1 + (depthLeft > depthRight ? depthLeft : depthRight); } return depthval;
}

3 ()

T

NEWT

(item,lptr,rptr)
BiTNode *GetTreeNode(TElemType item, BiTNode *lptr , BiTNode *rptr ){
if (!(T = (BiTNode*)malloc(sizeof(BiTNode))))
exit(1); T-> data = item; T-> lchild = lptr; T-> rchild = rptr; return T; }

BiTNode *CopyTree(BiTNode *T) { if (!T ) return NULL; if (T->lchild ) newlptr = CopyTree(T->lchild);// else newlptr = NULL; if (T->rchild ) newrptr = CopyTree(T->rchild);// else newrptr = NULL; newT = GetTreeNode(T->data, newlptr, newrptr); return newT;
} // CopyTree

newT
A

^B

E^

A

B

E

C^

^F^

C

F

D

G

HK

^D^

G

^H^ ^K^

4

:

" "

"A
A

"

A

B

D A(B( ,C( , )),D( , ))

C

Status CreateBiTree(BiTree &T) {

scanf(&ch);

if (ch==' ') T = NULL;

else {

if (!(T = (BiTNode *)malloc(sizeof(BiTNode))))

exit(OVERFLOW);

T->data = ch;

//

CreateBiTree(T->lchild); //

CreateBiTree(T->rchild); //

}

return OK; } // CreateBiTree

AB C D
T
A

^B

^D^

^C^

-+ a b c / d e
(a+b)c d/e

-+ a b c / d e -

/

+

c

d

e

ab

scanf(&ch); if ( In(ch, )) ; else { ;
; ; }

:

a+b

(a+b)c

+

+

c

ab

ab

a+bc (a+b)c d/e -

+
a bc

/

+

cd e

ab

:
scanf(&ch); if (In(ch, )) { ; ; } else if (In(ch, ))
{ ; ""; ;
}

void CrtExptree(BiTree &T, char exp[] ) { InitStack(S); Push(S, #); InitStack(PTR); p = exp; ch = *p; while (!(GetTop(S)==# && ch==#)) {
if (!IN(ch, OP)) CrtNode( t, ch ); //
else { ... ... } if ( ch!= # ) { p++; ch = *p;} } // while Pop(PTR, T); } // CrtExptree

switch (ch) { case ( : Push(S, ch); break; case ) : Pop(S, c); while (c!= ( ) { CrtSubtree( t, c); // Pop(S, c) } break; defult : ......
} // switch

while(!Gettop(S, c) && ( precede(c,ch))) {
CrtSubtree( t, c); Pop(S, c); } if ( ch!= # ) Push( S, ch); break;

void CrtNode(BiTree& T,char ch) {
T=(BiTNode*)malloc(sizeof(BiTNode)); T->data = char; T->lchild = T->rchild = NULL; Push( PTR, T ); }

void CrtSubtree (Bitree& T, char c) {
T=(BiTNode*)malloc(sizeof(BiTNode)); T->data = c; Pop(PTR, rc); T->rchild = rc; Pop(PTR, lc); T->lchild = lc; Push(PTR, T); }

"abcdefg"

"cbdaegf"

: a b c d e f g
c b d a e g f

a b
^c ^ ^d ^

^e f^
^g ^

void CrtBT(BiTree& T, char pre[], char ino[],
int ps, int is, int n ) { // pre[ps..ps+n-1] // ins[is..is+n-1] // if (n==0) T=NULL;
else { k=Search(ino, pre[ps]); //
if (k== -1) T=NULL; else { ... ... }
} //
} // CrtBT

T=(BiTNode*)malloc(sizeof(BiTNode)); T->data = pre[ps]; if (k==is) T->Lchild = NULL; else CrtBT(T->Lchild, pre[], ino[],
ps+1, is, k-is ); if (k=is+n-1) T->Rchild = NULL; else CrtBT(T->Rchild, pre[], ino[],
ps+1+(k-is), k+1, n-(k-is)-1 );

6.5

:

A

:

B C
D

E ABCDEFGHK

F

:

BDCAHGKFE

G

:

HK

DCBHKGFEA

""

"A BC"DE F GH"K

"
^B

E ^ ""

C^

"

"

^D^

""

Lchild

rchild
""

typedef struct BiThrNod { TElemType data; struct BiThrNode *lchild, *rchild; // PointerThr LTag, RTag; //
} BiThrNode, *BiThrTree;

:
""""
for ( p = firstNode(T); p; p = Succ(p) ) Visit (p);

:

""

void InOrderTraverse_Thr(BiThrTree T,

void (*Visit)(TElemType e)) {

p = T->lchild; // p

while (p != T) { // p==T

while (p->LTag==Link) p = p->lchild; //

p = p->rchild; Visit(p->data); //

}

p = p->rchild;

// p

}

} // InOrderTraverse_Thr

"""" pre, prep

if (p) { // p

if (!p->lchild) //

{ p->LTag = Thread; p->lchild = pre; }

if (!pre->rchild) //

{ pre->RTag = Thread; pre->rchild = p; }

pre = p;

// pre p

} // if

Status InOrderThreading(BiThrTree &Thrt, BiThrTree T) { //
if (!(Thrt = (BiThrTree)malloc( sizeof( BiThrNode))))
......

if (!T) Thrt->lchild = Thrt; else {
Thrt->lchild = T; pre = Thrt; InThreading(T); pre->rchild = Thrt; // pre->RTag = Thread; Thrt->rchild = pre; }

6.6

(-

:

data parent

A

0 A -1 r=0

1 B 0 n=6

BC D 2C 0

EF

3D 0 4E 2

G

5F 2 6G 5

C:
#define MAX_TREE_SIZE 100
: data parent
typedef struct PTNode { Elem data; int parent; //
} PTNode;

:
typedef struct { PTNode nodes [MAX_TREE_SIZE]; int r, n; // } PTree;

:

A BC D
EF G

data firstchild
0 A --11 1 1B0 2C0 4 3 D0 4E2 6 5F2 6 G 54

23 5
r=0 n=6

C:
: child next typedef struct CTNode {
int child; struct CTNode *next; } *ChildPtr;

data firstchild
typedef struct { Elem data; ChildPtr firstchild;
// } CTBox;

:
typedef struct { CTBox nodes[MAX_TREE_SIZE]; int n, r; //
} CTree;

(-
root

A

A

BC D

B C

EF

E

D

A

F

GBC

G

E

D

F

G

C: : firstchild data nextsibling
typedef struct CSNode{ Elem data; struct CSNode *firstchild, *nextsibling;
} CSNode, *CSTree;

F = ( T1, T2, ..., Tn ); T1 = (roott11, t12, ..., t1m);
B =( LBT, Node(root), RBT );

:
F = B =
ROOT( T1 ) Node(root) (t11, t12, ..., t1m ) LBT (T2, T3,..., Tn ) RBT

B = F = Node(root) ROOT( T1 ) LBT ( t11, t12, ...t1m) RBT (T2, T3, ..., Tn)

6.7

:
():

():

:

A

ABEFCDGHIJK B C D

EF

G

EFBCIJKHGDA

ABCDEFGHIJK

H IJK

BCD

1

EF

G H IJK

2
3

1. ()

()

typedef struct CSNode{
Elem data; struct CSNode *firstchild, *nextsibling; } CSNode, *CSTree;

int TreeDepth(CSTree T) { if(!T) return 0; else {
h1 = TreeDepth( T->firstchild ); h2 = TreeDepth( T->nextsibling);
return(max(h1+1, h2));
} } // TreeDepth

:

A

BCD

ABE

EF

G

ABF AC

H

void AllPath( Bitree T, Stack& S ) {
//
if (T) { Push( S, T->data ); if (!T->Lchild && !T->Rchild ) PrintStack(S); else { AllPath( T->Lchild, S );
AllPath( T->Rchild, S );
} Pop(S); } // if(T) } // AllPath

void OutPath( Bitree T, Stack& S ) {
//
while ( !T ) { Push(S, T->data ); if ( !T->firstchild ) Printstack(s); else OutPath( T->firstchild, s ); Pop(S); T = T->nextsibling;
} // while } // OutPath

:

(FC) -

: :

A BC D
EF G

(`#', `A') (`A', `B') (`A', `C') (`A', `D') (`C', `E') (`C', `F') (`E', `G')

A
B
C
D

void CreatTree( CSTree &T ) { T = NULL; for( scanf(&fa, &ch); ch!= ; scanf(&fa, &ch);) { p = GetTreeNode(ch); // EnQueue(Q, p); // if (fa == ) T = p; // else { ... ... } // } // for
} // CreateTree

GetHead(Q,s); // () while (s->data != fa ) { //
{ s->firstchild = p; r = p; } //
else { r->nextsibling = p; r = p; } //

6.8

WPL(T) = wklk ()
n m ""

75

9

24

WPL(T)= 72+52+23+ 43+92 =60

2 4 5 79
WPL(T)= 74+94+53+ 42+21 =89

(1) () n {w1, w2, ..., wn}
n F = {T1, T2, ... , Tn}
wi

(2) F

(3) F
(4) (2) (3) F

: W={ 5, 6, 2, 9, 7 } 562 97

697

7

52

97 52

13 67

97 52

13 67

29

0

1

13 01
67 00 01

16 01

9 10

7 0

1

52

110 111

1.
2.
3.

4.

5. 1 2 6. 7.