feiqDS树的递归遍历学习教案

会计学1feiqDS树的递归遍历树的递归遍历(bin l)第一页，共50页。0层1层3层2层Depth= 3ACGBDEFKLHMIJ2022-6-172第1页/共50页第二页，共50页。2022-6-17第2页/共50页第三页，共50页。LRLR2022-6-174第3页/共50页第四页，共50页。2022-6-175第4页/共50页第五页，共50页。2022-6-176第5页/共50页第六页，共50页。2022-6-177第6页/共50页第七页，共50页。2022-6-178第7页/共50页第八页，共50页。2022-6-179第8页/共50页第九页，共50页。2022-6-1710深度定义为结点深度定义为结点(ji din)的最大层数的最大层数层数由零开始计！层数由零开始计！第9页/共50页第十页，共50页。2022-6-1711深度定义深度定义(dngy)为为结点的最大层数结点的最大层数层数由零开始计！层数由零开始计！第10页/共50页第十一页，共50页。012374568 92022-6-1712第11页/共50页第十二页，共50页。00 1 2 3 4 5 6 7 8 913789456290 1 2 3 4 5 6 7 8 90125436782022-6-1713第12页/共50页第十三页，共50页。2022-6-1714leftdataright递归的终结状态第13页/共50页第十四页，共50页。2022-6-17*3+57第14页/共50页第十五页，共50页。2022-6-1716leftdataright也是递归的终结状态第15页/共50页第十六页，共50页。2022-6-17*3+57第16页/共50页第十七页，共50页。2022-6-17第17页/共50页第十八页，共50页。leftdataright第18页/共50页第十九页，共50页。2022-6-17*3+57*3+57第19页/共50页第二十页，共50页。2022-6-17*3+57第20页/共50页第二十一页，共50页。2022-6-17*3+57第21页/共50页第二十二页，共50页。2022-6-1723leftdataparentrightleftdataparentright第22页/共50页第二十三页，共50页。 AAABBBCCCDDDFFFEEErootrootroot2022-6-1724第23页/共50页第二十四页，共50页。2022-6-17第24页/共50页第二十五页，共50页。2022-6-1726第25页/共50页第二十六页，共50页。vLR2022-6-1727第26页/共50页第二十七页，共50页。vLR递归的终结条件(tiojin)：盒子是“空”！vLR2022-6-1728第27页/共50页第二十八页，共50页。vLR2022-6-1729第28页/共50页第二十九页，共50页。2022-6-1730第29页/共50页第三十页，共50页。2022-6-1731第30页/共50页第三十一页，共50页。2022-6-1732第31页/共50页第三十二页，共50页。2022-6-1733第32页/共50页第三十三页，共50页。2022-6-1734第33页/共50页第三十四页，共50页。2022-6-1735第34页/共50页第三十五页，共50页。2022-6-1736第35页/共50页第三十六页，共50页。第一次到达(dod)T时visit由左子树返回(fnhu)T时visit由右子树返回(fnhu)T时visit2022-6-1737第36页/共50页第三十七页，共50页。2022-6-1738第37页/共50页第三十八页，共50页。2022-6-1739第38页/共50页第三十九页，共50页。vLR2022-6-1740第39页/共50页第四十页，共50页。2022-6-1741第40页/共50页第四十一页，共50页。n/注意： 层次从0编号(bin ho)时，空树深度为-1!vLR2022-6-1742第41页/共50页第四十二页，共50页。2022-6-1743第42页/共50页第四十三页，共50页。HBDFEKCGAEKCGABHDFEKCGABHDF2022-6-1744第43页/共50页第四十四页，共50页。EKCGABHFDKCGEABHFDEABHFDCKG2022-6-1745第44页/共50页第四十五页，共50页。 根根左子树结点右子树结点左子树结点右子树结点k个结点个结点p1p1+1p1+k+1p2i1i1+ki1+k+1i2 中：中： 先：先：2022-6-1746第45页/共50页第四十六页，共50页。2022-6-1747第46页/共50页第四十七页，共50页。CABED2022-6-1748第47页/共50页第四十八页，共50页。2022-6-1749第48页/共50页第四十九页，共50页。n createTreeByExtendedPreorder(lst, i+1)n root.right, j2 = n createTreeByExtendedPreorder(lst, j1)nn return root, j22022-6-1750第49页/共50页第五十页，共50页。