二叉树遍历技巧.docx

二叉树遍历技巧.docx

ID:48563201

大小:18.40 KB

页数:2页

时间:2020-02-26

二叉树遍历技巧.docx_第1页
二叉树遍历技巧.docx_第2页
资源描述:

《二叉树遍历技巧.docx》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库

1、二叉树先根序、后根序、中根序遍历的速算法(解题技巧)经过研究我找出了一种不用画图,由先(后)根序遍历和中根序遍历迅速确定遍历结果的办法。谨以此文献给智商与我同级而又不得不研究算法的朋友。抽象思维太差,用例子来说明吧。下面这个是后根遍历的算法。例1:已知某二叉树的先根序遍历为ABCDEFG,中根序遍历为CDBAFEG,则它的后根序遍历为_________解法如下:1、确定树根。由先序遍历知道,树根为A。2、分离左、右子树。由中根序遍历知,A左面的为CDB左子树结点,右面的FEG为右子树结点。把先根序遍历也分成左、右子树结点,BCD、EFG。      前根序遍历 BCD EF

2、G中根序遍历 CDB FEG3、分别把先根序遍历左、右子树结点抄过来,写的时候要从右往左写,本例中,依次写下B、C、D、,E、F、G,结果是DCBGFE。当然不是简单到这种程序。上面只是个原理。抄的过程应该是这样的:盯着前根序的,瞅着中根序的。如果要抄的先根序中的结点在中根序中是最左/右边,则直接抄过来;如果不是,则把这个结点左边的结点先放记在右根序的最左边,然后继续抄。本题的结果是DCB,FGE,A,即DCBFGEA。上面这个例子太短,看不出“猫腻”来。再举个结点多一点儿的。   例2:已知某二叉树的先根序遍历为ABCDEFGHIJK,中根序遍历为CEDFBAHKJIG,

3、则它的后根序遍历为_________   按上面的方法:      前根序遍历 BCDEF GHIJK      中根序遍历 CEDFB HKJIG依次抄得前根序的结点:F、E(E在中根序遍历中不靠边,所以先放在后根遍序历中左子树结点最左边)、D、C同理,把右子树也抄过来。因此,写下结点的过程依次是:如果还是不太懂,你可以试着做一下下面的例子:已知二叉树前序遍历ABCDEFGHIJK,中序遍历CEDFBAHGKJI,求后序遍历。解:(1)以根结点A分左、右子树结点,                BCDEFGHIJK                CEDFBHGKJI(2)

4、 写左子树,盯着前序,从右到左开始写                      DCB (在中序中,B靠右边,C靠左边,D不靠边。写一个,从中序中抹一个。)因为D在中序遍历中不靠边,所以下一个结点E先搁到最左边(注意,是“搁”,也就是说,不能把E从中序抹去。E  DCB因为B已经抹了,F靠右边。于是F仍然按照从右到左的规则,写在D的的左边。E FDCB最后把E加上,左子树OK。右子树仍然从右到写                                       G因为G不靠边,所以下一个结点H先搁在最左边H         G 然后继续              

5、             H         KJIG于是,结果是EFDCBHKJIGA  前根序遍历类似。以上的方法只适用于三层以内的二叉树(含三层)。在选择题中,三层以上二叉树也可用以上方法初步判断正确答案。

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。