数据结构树的概念和二叉树PPT学习教案

1、数据结构树的概念和二叉树数据结构树的概念和二叉树第1页/共87页第2页/共87页AECDBIHGF第3页/共87页第4页/共87页第5页/共87页第6页/共87页第7页/共87页第8页/共87页第9页/共87页第10页/共87页第11页/共87页第12页/共87页A (a) (b) (c) (d) (e)ACBACBCBACBACB 含有3个结点的不同二叉树第13页/共87页第14页/共87页第15页/共87页第16页/共87页第17页/共87页156437298101311121415第18页/共87页第19页/共87页56437298101第20页/共87页第21页/共87页第22页/共8

2、7页第23页/共87页第24页/共87页31 23 12 66 94 17 5 70 62 49 1712523627049316694第25页/共87页CB A 25731a1a2a3a4a5A B a6 a7 C第26页/共87页leftright data第27页/共87页ADCBEFGACBEFDGroot第28页/共87页第29页/共87页leftdataparentright第30页/共87页遍历方式先根遍历： DLR中根遍历： LDR后根遍历： LRDDRL第31页/共87页ABDFCE第32页/共87页第33页/共87页ABDFCE第34页/共87页第35页/共87页ABDFC

3、E第36页/共87页第37页/共87页第38页/共87页第39页/共87页第40页/共87页第41页/共87页 结点 结点状态 i第42页/共87页第43页/共87页第44页/共87页第45页/共87页ABDFCE第46页/共87页ABDFCE第47页/共87页第48页/共87页第49页/共87页AB CKDEHFABEDCKFHABDCKEHF第50页/共87页ACBEDFGHABCDEFGHABCGDEHF第51页/共87页第52页/共87页第53页/共87页第54页/共87页第55页/共87页ABECD第56页/共87页第57页/共87页第58页/共87页第59页/共87页第60页/共8

4、7页第61页/共87页第62页/共87页第63页/共87页第64页/共87页第65页/共87页第66页/共87页c liini1第67页/共87页第68页/共87页第69页/共87页外通路长度为 3 3 2 3 4 4 3 3=25内通路长度为 2 1 0 2 3 12=11.第70页/共87页其中，n表示外结点的个数，wi和Li分别表示外结点ki的权值和根到ki之间的路径长度。 第71页/共87页第72页/共87页第73页/共87页第74页/共87页第75页/共87页 例: F=7,5,2,4 2475116187524752647524116第76页/共87页第77页/共87页第78页/共87页第79页/共87页编码 A (0) T (10) C (110) S (111)754261118总编码长度：1*7+2*5+3*2+3*4=35第80页/共87页第81页/共87页LLINKIN