您好,欢迎来到爱玩科技网。
搜索
您的当前位置:首页先根,中根,后根遍历

先根,中根,后根遍历

来源:爱玩科技网
先序遍历(先根)是先访问当前节点,然后再遍历左子树,最后是右子树。
中序遍历(中根)是先遍历左子树,再访问当前节点,最后是右子树。
后序遍历(后根)是先遍历左子树,再遍历右子树,最后访问当前节点。
 
例如:
一棵二叉树的先根遍历为ABCDEFG,中根遍历为CBDEAGF,则其后根遍历为多少?
 
方法:(层层解剖,集合从大到小,递归分析)
(无论如何必须先分析先根,确定父节点,再往下推)
 
第一步:
分析ABCDEFG,由于A在先序遍历(ABCDEFG)中处在前面,先确定A为父节点,
再根据中序遍历(CBDEAGF),可以分成3个集合:
(CBDE) A (GF)
 
第二步:
分析CBDE,由于B在先序遍历(ABCDEFG)中处在前面,先确定B为父节点:
再次根据中序遍历(CBDE),可以分成3个集合:
(C)B (DE)
再分析DE,由于D在先序序列中在E前面,确定D为父节点:
再根据中序遍历(DE),可以确定E为右节点
 
第三部:
分析GF,由于F在先序遍历(ABCDEFG)中处在前面,先确定F为父节点:
再根据中序遍历(GF),可以确定G为左节点
 
到此已经可以确定这颗二叉树了:
 
所以后根遍历为:
 
CEDBGFA

转载于:https://www.cnblogs.com/huangliang-hb/p/9156241.html

因篇幅问题不能全部显示,请点此查看更多更全内容

Copyright © 2019- aiwanbo.com 版权所有 赣ICP备2024042808号-3

违法及侵权请联系:TEL:199 18 7713 E-MAIL:2724546146@qq.com

本站由北京市万商天勤律师事务所王兴未律师提供法律服务