当前位置:首页 >> 数学 >>

最新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
" Link" Lchild""
" Thread"

rchild
" Link" rchild""
" Thread"
""


typedef enum { Link, Thread } PointerThr; // Link==0:Thread==1:
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; //

while (p->RTag==Thread && p->rchild!=T) {

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

}

p = p->rchild;

// p

}

} // InOrderTraverse_Thr


"""" pre, prep

void InThreading(BiThrTree p) {

if (p) { // p

InThreading(p->lchild); //

if (!p->lchild) //

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

if (!pre->rchild) //

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

pre = p;

// pre p

InThreading(p->rchild); //

} // if

} // InThreading

Status InOrderThreading(BiThrTree &Thrt, BiThrTree T) { //
if (!(Thrt = (BiThrTree)malloc( sizeof( BiThrNode))))
exit (OVERFLOW); Thrt->LTag = Link; Thrt->RTag =Thread; Thrt->rchild = Thrt; //
......
return OK; } // InOrderThreading

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

ADGHI

ADGHJ

I J K ADGHK

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 ) { //
DeQueue(Q,s); GetHead(Q,s); } if (!(s->firstchild))
{ 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.


相关文章:
数据结构与算法2019尔雅答案100分.doc
数据结构与算法2019尔雅答案100分_远程、网络教育_成人教育_教育专区。。。
2019最新第九讲 典型算法 参考书:《程序设计基础》吴文....ppt
2019最新第九讲 典型算法 参考书:《程序设计基础》吴文虎编著《算法与数据结构》张乃孝主编《算法设计与分_计算机软件及应用_IT/计算机_专业资料。第九讲 典型算法...
《数据结构与算法设计》d01-2019-2-PPT课件_图文.ppt
《数据结构与算法设计d01-2019-2-PPT课件 - 2019年09月 已授课程回顾 1.1 1.2 1.3 1.4 什么是数据结构 基本概念和术语 抽象数据类型 算法算法分析 ....
2019精品国家级精品课程数据结构与算法化学_图文.ppt
2019精品国家级精品课程数据结构与算法化学 - 国家级精品课程《数据结构与算法》 第4章 字符串 张铭、赵海燕、王腾蛟、宋国杰、高军 http://www.jpk.pku.edu...
《数据结构与算法设计》d02-2019-精选文档_图文.ppt
《数据结构与算法设计d02-2019-精选文档 - 第2章 线性表 2.1 2.2 2.3 2.4 线性表的类型定义 线性表的顺序表示和实现 线性表的链式表示和实现 线性表...
《数据结构(本)(本科必修)》2019期末试题及答案.doc
《数据结构(本)(本科必修)》2019期末试题及答案 - 《数据结构(本科)》2019 期末试题及答案 一、单项选择题(每小题 2 分。共 30 分) 1.链表所具备的特点是...
数据结构第1章-答案.doc
数据结构第1章-答案_工学_高等教育_教育专区。第 ...× 03、算法的优劣与算法描述语言无关,但与所用...文档贡献者 雪纷纷 贡献于2019-04-13 1 /2 相关...
最新2019-数据结构第四章串A教学-PPT课件_图文.ppt
串的表示和实现 4.3 串的模式匹配算法 2019/5/16 数据结构 3 4.1 串类型的...《数据结构与算法》中山大学出版社 2019/5/16 数据结构 6 串的抽象数据...
《数据结构与算法设计实训》课程教学研究-2019年精选作文.doc
《数据结构与算法设计实训》课程教学研究-2019年精选作文 - 《数据结构与算法设计实训》课程教学研究 DOIDOI:10.11907/rjdk.1511204 0 引言 《数据结构》是计算机...
2019年最新-数据结构第九部分查找-精选文档_图文.ppt
2019最新-数据结构第九部分查找-精选文档 - 《 数据结构》课程 数据结构
《数据结构》教学方法探讨-2019年精选作文.doc
《数据结构》教学方法探讨-2019年精选作文_初中作文_初中教育_教育专区。《数据...同一问题不同实现算法进行比较,这既能提 高学生的分析及思维能力,又能形成一...
《数据结构》重修考试大纲(2019年4月).doc
《数据结构》重修考试大纲 2018-2019 学年(2)一、...中序和后序的遍历算法,线索二叉树的作用和实现原 ...题后给出的供选择的答案中选择合适的答案,补足这些...
2019年最新-数据结构---串-精选文档_图文.ppt
2019最新-数据结构---串-精选文档_计算机软件及应用_IT/计算机_专业资料。...这类串操作实现算法为:先为新生成的串分配一个存储空间, 然后进行串值的...
宁波大学2019年《916数据结构与算法》考研专业课考试大纲.pdf
宁波大学2019年《916数据结构与算法》考研专业课考试大纲 - 2019 :
《数据结构与算法设计》d03-2019-精品文档_图文.ppt
《数据结构与算法设计d03-2019-精品文档 - 3.1 栈 3.1.1 栈
程序设计大赛对《数据结构与算法》课程教学的意义-2019....doc
程序设计大赛对《数据结构与算法》课程教学的意义-2019年文档 - 程序设计大赛对《数据结构与算法》课程教学的意义 DOI:10.19694/jki.issn2095-2457.2018.14...
《数据结构》课程教学思想和方法-2019年作文.doc
《数据结构》课程教学思想和方法-2019年作文 - 《数据结构》课程教学思想和方法 高职《数据结构》课程既是重要的专业基础课程,又是一门 锻炼程序设计能力的实践课程...
《数据结构》教学中存在的问题及解决措施-2019年精选作文.doc
《数据结构》教学中存在的问题及解决措施-2019年精选作文 - 《数据结构》教学
数据结构概论-精选文档_图文.ppt
2019年4月第1版 (配题集) 参考书: [1] 高一凡,《数据结构》算法实现及解析(第二版),西电出版社,2019年10月 [2] 李春葆,数据结构(C语言篇)-习题与解析(...
高职高专数据结构教学研究与探讨-2019年教育文档.doc
高职高专数据结构教学研究探讨-2019年教育文档...《数据结构》中基本概念、算法较多, 彼此间具有连贯...小论文或总结报告, 使学生时刻 跟踪本课程的最新...