铁路工程试验检测频率及技术要求表

会计学1树和二叉树副本(fùběn)第一页，共51页。2021年10月19日线性结构——一个(yīɡè)对一个(yīɡè)，如线性表、栈、队列树形结构(jiégòu)——一个对多个，如树集合——数据(shùjù)元素间除“同属于一个集合”外，无其它关系图形结构——多个对多个，如图逻辑结构第1页/共51页第二页，共51页。树是一类重要的非线性数据结构，是以分支关系定义的层次结构。树结构在客观世界中广泛存在，如人类社会的族谱(zúpǔ)和各种组织机构都可以用树来形象表示。第2页/共51页第三页，共51页。第3页/共51页第四页，共51页。族谱(zúpǔ)第4页/共51页第五页，共51页。组织(zǔzhī)机构第5页/共51页第六页，共51页。定义定义：树(tree)是n(n>=0)个结点的有限集T，在任意一棵非空树中：有且仅有一个特定的结点，称为树的根(root)当n>1时，其余结点可分为m(m>0)个互不相交的有限集T1,T2,……Tm，其中(qízhōng)每一个集合本身又是一棵树，称为根的子树(subtree)特点：树中有一个结点——根树中各子树是互不相交的集合5.1树的定义(dìngyì)和基本术语第6页/共51页第七页，共51页。A只有根结点的树ABCDEFGHIJKLM有子树的树根子树T1T2T3第7页/共51页第八页，共51页。2021年10月19日5.1树的定义和基本(jīběn)术语树是n个结点(jiédiǎn)的有限集T1T2T3有子树的树第8页/共51页第九页，共51页。和线性结构的比较线性结构              树结构第一个数据元素(无前驱(qiánqū))   根结点(无前驱(qiánqū))最后一个数据元素(无后继)  多个叶子结点(无后继)其它数据元素              树中其它结点(一个前驱(qiánqū)、一个后继)      (一个前驱(qiánqū)、多个后继)第9页/共51页第十页，共51页。2021年10月19日ADTTree{数据对象(duìxiàng)D:数据关系R:基本操作P：}ADTTree若D为空集，则称为空树；//允许n=0若D中仅含一个数据元素，则R为空集；其他情况下的R存在二元关系：①root唯一//关于(guānyú)根的说明②Dj∩Dk=Φ//关于(guānyú)子树不相交的说明③……//关于(guānyú)数据元素的说明D是具有相同特性(tèxìng)的数据元素的集合。//至少有15个树的抽象数据类型定义第10页/共51页第十一页，共51页。2021年10月19日凹入表示(biǎoshì)嵌套集合(jíhé)广义(guǎngyì)表树的其它表示方式第11页/共51页第十二页，共51页。2021年10月19日根叶子(yèzi)森林——即根结点(没有前驱(qiánqū))——即终端结点(没有后继)——指m棵不相交的树的集合(例如删除A后的子树个数)基本(jīběn)术语第12页/共51页第十三页，共51页。基本(jīběn)术语——即树的数据元素(yuánsù)——结点挂接的子树数结点结点的度结点的层次终端(zhōnɡduān)结点分支结点树的度树的深度(或高度)——从根到该结点的层数（根结点算第一层）——即度为0的结点，即叶子——即度不为0的结点（也称为内部结点）——所有结点度中的最大值——指所有结点中最大的层数层次1234第13页/共51页第十四页，共51页。——即上层(shàngcéng)的那个结点(直接前驱)——即下层结点的子树的根(直接后继)——同一双亲下的同层结点（孩子之间互称兄弟）——即双亲位于同一层的结点（但并非同一双亲）——即从根到该结点所经分支的所有结点——即该结点下层子树中的任一结点双亲孩子兄弟(xiōngdì)堂兄弟(xiōngdì)祖先子孙基本(jīběn)术语有序树：若从树中结点的各个子树看是从左到右有序的（不可互换），则称为有序树，否则为无序树。第14页/共51页第十五页，共51页。ABCDEFGHIJKLM结点(jiédiǎn)A的度：3结点(jiédiǎn)B的度：2结点(jiédiǎn)M的度：0叶子(yèzi)：K，L，F，G，M，I，J结点(jiédiǎn)A的孩子：B，C，D结点(jiédiǎn)B的孩子：E，F结点I的双亲：D结点L的双亲：E结点B，C，D为兄弟结点K，L为兄弟树的度：3结点A的层次：1结点M的层次：4树的深度：4结点F，G为堂兄弟结点A是结点F，G的祖先第15页/共51页第十六页，共51页。2021年10月19日5.2二叉树普通(pǔtōng)树（多叉树）若不转化为二叉树，则运算很难实现为何要重点研究每结点最多只有两个“叉”的树？二叉树的结构最简单，规律性最强；可以证明，所有树都能转为唯一对应(duìyìng)的二叉树，不失一般性。第16页/共51页第十七页，共51页。二叉树的定义二叉树是n(n0)个结点的有限集，它或为空树(n=0)，或由一个根结点和两棵分别称为左子树和右子树的互不相交的二叉树构成特点每个结点至多有二棵子(kēzi)树(结点的度小于等于2）有序树：二叉树的子树有左、右之分，且其次序不能任意颠倒第17页/共51页第十八页，共51页。2021年10月19日二叉树的五种不同形态第18页/共51页第十九页，共51页。2021年10月19日具有3个结点的二叉树可能有几种(jǐzhǒnɡ)不同形态？普通树呢？练习(liànxí)5种/2种第19页/共51页第二十页，共51页。2021年10月19日ADTBinaryTree{数据(shùjù)对象D:数据(shùjù)关系R:基本操作P：}ADTBinaryTree若D=Φ，则R=Φ；若D≠Φ，则R={H}；存在二元关系：①root唯一//关于根的说明②Dj∩Dk=Φ//关于子树不相交的说明③……//关于数据(shùjù)元素的说明④……//关于左子树和右子树的说明D是具有相同特性的数据(shùjù)元素的集合。//至少有20个二叉树的抽象数据类型定义第20页/共51页第二十一页，共51页。2021年10月19日性质(xìngzhì)1:在二叉树的第i层上至多有2i-1个结点二叉树的性质(xìngzhì)提问：第i层上至少(zhìshǎo)有个结点？1证明：用归纳法证明之i=1时，只有一个根结点，是对的假设对所有j(1j<i)命题成立，即第j层上至多有个结点则可以证明j=I时命题成立。由归纳法假设，第i-1层至多有　　个结点又二叉树每个结点的度至多为2第i层上最大结点数是第i-1层的2倍，即　故命题得证第21页/共51页第二十二页，共51页。2021年10月19日二叉树的性质(xìngzhì)性质(xìngzhì)2:深度为k的二叉树至多有2k-1个结点提问：深度为k时至少(zhìshǎo)有个结点？k证明：由性质1，可得深度为k的二叉树最大结点数是第22页/共51页第二十三页，共51页。2021年10月19日性质3:对于任何一棵二叉树，若2度的结点数有n2个，则叶子(yèzi)数n0必定为n2＋1（即n0=n2+1）第23页/共51页第二十四页，共51页。性质3：对任何一棵二叉树T，如果其终端(zhōnɡduān)结点数为n0，度为2的结点数为n2，则n0=n2+1证明：设n1为二叉树T中度为1的结点数因为：二叉树中所有结点的度均小于或等于2所以：其结点总数n=n0+n1+n2又二叉树中，除根(chúgēn)结点外，其余结点都只有一个分支进入，设B为分支总数，则n=B+1又：分支由度为1和度为2的结点射出，B=n1+2n2于是，n=B+1=n1+2n2+1=n0+n1+n2n0=n2+1第24页/共51页第二十五页，共51页。2021年10月19日满二叉树：一棵深度为k且有2k-1个结点的二叉树。（特点(tèdiǎn)：每层都“充满”了结点）特殊(tèshū)形态的二叉树完全二叉树：深度为k的，有n个结点的二叉树，当且仅当其每一个(yīɡè)结点都与深度为k的满二叉树中编号从1至n的结点一一对应只有最后一层叶子不满，且全部集中在左边第25页/共51页第二十六页，共51页。1231145891213671014151231145891267101234567123456满二叉树完全(wánquán)二叉树第26页/共51页第二十七页，共51页。2021年10月19日满二叉树是叶子一个也不少的树，而完全二叉树虽然前n-1层是满的，但最底层却允许(yǔnxǔ)在右边缺少连续若干个结点。满二叉树是完全二叉树的一个特例。满二叉树和完全(wánquán)二叉树的区别第27页/共51页第二十八页，共51页。2021年10月19日性质4:具有n个结点的完全(wánquán)二叉树的深度必为[log2n]＋1k层nk-1层第28页/共51页第二十九页，共51页。2021年10月19日性质5：如果(rúguǒ)对一棵有n个结点的完全二叉树的结点按层序编号，则对任一结点i(1in)，有：(1)如果(rúguǒ)i=1，则结点i是二叉树的根，无双亲；如果(rúguǒ)i>1，则其双亲是i/2(2)如果(rúguǒ)2i>n，则结点i无左孩子；如果(rúguǒ)2in，则其左孩子是2i(3)如果(rúguǒ)2i+1>n，则结点i无右孩子；如果(rúguǒ)2i+1n，则其右孩子是2i+1第29页/共51页第三十页，共51页。2021年10月19日二叉树的顺序存储实现：按满二叉树的结点层次(céngcì)编号，依次存放二叉树中的数据元素。第30页/共51页第三十一页，共51页。2021年10月19日abcde0000fg012345678910abcdefg特点：结点间关系蕴含在其存储位置中浪费(làngfèi)空间，适于存满二叉树和完全二叉树单支树二叉树的顺序存储第31页/共51页第三十二页，共51页。2021年10月19日DATAPARENTLCHILDRCHILD二叉树的链式存储(cúnchǔ)第32页/共51页第三十三页，共51页。2021年10月19日ABCDEFGABCDEFG^^^^^^^^二叉链表typedefstructBiNode{TElemTypedata;structBiNode*lchild,*rchild;//左右(zuǒyòu)孩子指针}BiNode,*BiTree;lchilddatarchild第33页/共51页第三十四页，共51页。2021年10月19日lchilddataparentrchild有时，为了便于(biànyú)找到结点的双亲，还可以在结点结构中增加一个指向其双亲结点的指针利用这种存储结构所得二叉树的存储结构叫--三叉链表typedefstructTriTNode{TelemTypedata;structTriTNode*lchild,*parent,*rchild;}TriTNode,*TriTree;第34页/共51页第三十五页，共51页。2021年10月19日三叉链表ABCDEFGABCDEFG^^^^^^^^^lchilddataparentrchild第35页/共51页第三十六页，共51页。2021年10月19日5.3遍历(biànlì)二叉树遍历定义——指按某条搜索路线遍访每个结点且不重复(chóngfù)（又称周游）。遍历用途——它是树结构插入、删除、修改、查找和排序运算的前提，是二叉树一切运算的基础和核心。第36页/共51页第三十七页，共51页。2021年10月19日DLRDLRLDRLRDDRLRDLRLD遍历(biànlì)规则先左后右第37页/共51页第三十八页，共51页。二叉树的遍历若二叉树为空，则进行(jìnxíng)空操作，否则：先序遍历：先访问根结点,然后分别先序遍历左子树、右子树中序遍历：先中序遍历左子树，然后访问根结点，最后中序遍历右子树后序遍历：先后序遍历左、右子树，然后访问根结点按层次遍历：从上到下、从左到右访问各结点第38页/共51页第三十九页，共51页。2021年10月19日DLRADLRDLR>B>>D>>CDLRADBC先序遍历(biànlì)序列：ABDC若二叉树为空，则空操作否则访问根结点(jiédiǎn)(D)前序遍历左子树(L)前序遍历右子树(R)遍历的算法(suànfǎ)实现－先(前)序遍历第39页/共51页第四十页，共51页。2021年10月19日遍历(biànlì)的算法实现－中序遍历(biànlì)若二叉树为空，则空操作否则:中序遍历左子树(L)访问(fǎngwèn)根结点(D)中序遍历右子树(R)ADBCLDRBLDRLDR>A>>D>>CLDR中序遍历(biànlì)序列：BDAC第40页/共51页第四十一页，共51页。2021年10月19日遍历的算法实现(shíxiàn)－后序遍历若二叉树为空，则空操作否则后序遍历左子树(L)后序遍历右子树(R)访问(fǎngwèn)根结点(D)ADBCLRDLRDLRDA>>D>>CLRDB后序(hòuxù)遍历序列：DBCA第41页/共51页第四十二页，共51页。2021年10月19日则三种遍历算法可写出:遍历(biànlì)的算法实现－－用递归形式格外简单！longFactorial(longn){if(n==0)return1;//基本(jīběn)项elsereturnn*Factorial(n-1);//归纳项}回忆(huíyì):第42页/共51页第四十三页，共51页。2021年10月19日StatusPreOrderTraverse(BiTreeT){if(T==NULL)returnOK;//空二叉树else{cout<<T->data;//访问(fǎngwèn)根结点PreOrderTraverse(T->lchild);//递归遍历左子树PreOrderTraverse(T->rchild);//递归遍历右子树}}先序遍历(biànlì)算法第43页/共51页第四十四页，共51页。2021年10月19日StatusPreOrderTraverse(BiTreeT){if(T==NULL)returnOK;else{cout<<T->data;PreOrderTraverse(T->lchild);PreOrderTraverse(T->rchild);}}主程序Pre(T)返回(fǎnhuí)返回(fǎnhuí)pre(TR);返回(fǎnhuí)返回pre(TR);ACBDTBprintf(B);pre(TL);BTAprintf(A);pre(TL);ATDprintf(D);pre(TL);DTCprintf(C);pre(TL);C返回T>左是空返回pre(TR);T>左是空返回T>右是空返回T>左是空返回T>右是空返回pre(TR);先序序列：ABDC第44页/共51页第四十五页，共51页。2021年10月19日StatusInOrderTraverse(BiTreeT){if(T==NULL)returnOK;//空二叉树else{InOrderTraverse(T->lchild);//递归遍历左子树cout<<T->data;//访问(fǎngwèn)根结点InOrderTraverse(T->rchild);//递归遍历右子树}}中序遍历(biànlì)算法第45页/共51页第四十六页，共51页。2021年10月19日StatusPostOrderTraverse(BiTreeT){if(T==NULL)returnOK;//空二叉树else{PostOrderTraverse(T->lchild);//递归遍历(biànlì)左子树PostOrderTraverse(T->rchild);//递归遍历(biànlì)右子树cout<<T->data;//访问根结点}}后序(hòuxù)遍历算法第46页/共51页第四十七页，共51页。2021年10月19日StatusPreOrderTraverse(BiTreeT){if(T==NULL)returnOK;else{cout<<T->data;PreOrderTraverse(T->lchild);PreOrderTraverse(T->rchild);}}StatusPostOrderTraverse(BiTreeT){if(T==NULL)returnOK;else{PostOrderTraverse(T->lchild);PostOrderTraverse(T->rchild);cout<<T->data;}}StatusInOrderTraverse(BiTreeT){if(T==NULL)returnOK;else{InOrderTraverse(T->lchild);cout<<T->data;InOrderTraverse(T->rchild);}}遍历算法(suànfǎ)的分析第47页/共51页第四十八页，共51页。2021年10月19日先序遍历(biànlì)：中序遍历(biànlì)：后序遍历(biànlì)：ABCDEABDECDBEACDEBCA口诀：DLR—先序遍历(biànlì)，即先根再左再右LDR—中序遍历(biànlì)，即先左再根再右LRD—后序遍历(biànlì)，即先左再右再根第48页/共51页第四十九页，共51页。2021年10月19日+*A*/EDCB先序遍历+**/ABCDE前缀(qiánzhuì)表示中序遍历A/B*C*D+E中缀表示后序遍历AB/C*D*E+后缀表示层序遍历+*E*D/CAB用二叉树表示(biǎoshì)算术表达式第49页/共51页第五十页，共51页。2021年10月19日AFEDCBG时间效率:O(n)//每个结点(jiédiǎn)只访问一次空间效率:O(n)//栈占用的最大辅助空间遍历(biànlì)算法的分析第50页/共51页第五十一页，共51页。