[理工] 二元樹前序 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

有點難用說的基本概念就是inorder postorder的追蹤順序不一樣一個是先左中右一個是左右中

作者: eduzone (eduzone) 2018-08-12 11:55:00

感謝詳解!

繼續閱讀