[理工] 二元树前序 eduzone PTT批踢踢实业坊

楼主: eduzone (eduzone) 2018-08-11 22:52:38

中序：AIBHCGDFE
后序：ABICHDGEF
求前序追踪?
由后序追踪可知中节点为F
得到中序追踪的左右节点
(左 AIBHCGD) F (E 右)
请问该怎么回推出前序呢? F...

作者: seika555 (kakkoii) 2018-08-11 22:59:00

最基本的想法就是把二元树还原，在把它做preorder变成FGHIABCDE吧

作者: eggy1018 (ç¾…å¯†æèˆ‡è±¬éŽå¤œ) 2018-08-11 23:34:00

要先化成2元树在用前序追踪注意 post order 最后才是rootPreorder的第一个才是root

作者: jasoncph (Ben) 2018-08-12 00:00:00

先还原成BT再Preorder一次

楼主: eduzone (eduzone) 2018-08-12 00:01:00

请问由后序G可知,左子为C右子为D剩下的AIBH如何追踪

作者: seika555 (kakkoii) 2018-08-12 00:51:00

https://imgur.com/TDmXZcN.jpg有点难用说的基本概念就是inorder postorder的追踪顺序不一样一个是先左中右一个是左右中

楼主: eduzone (eduzone) 2018-08-12 11:55:00

感谢详解!

继续阅读