[理工] 二元樹前序

看板Grad-ProbAsk作者 (eduzone)時間7年前 (2018/08/11 22:52), 編輯推噓5(5推 0噓 7→)
留言12則, 4人參與, 7年前最新討論串1/1
中序：AIBHCGDFE 後序：ABICHDGEF 求前序追蹤? 由後序追蹤可知中節點為F 得到中序追蹤的左右節點 (左 AIBHCGD) F (E 右) 請問該怎麼回推出前序呢? F... -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.27.105.157 ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1533999160.A.58C.html
推
08/11 22:59, 7年前 , 1F
最基本的想法就是把二元樹還原，在把它做preorder變成FG
08/11 22:59, 1F
→
08/11 23:00, 7年前 , 2F
HIABCDE吧
08/11 23:00, 2F
推
08/11 23:34, 7年前 , 3F
要先化成2元樹 在用前序追蹤
08/11 23:34, 3F
→
08/11 23:35, 7年前 , 4F
注意 post order 最後才是root
08/11 23:35, 4F
→
08/11 23:35, 7年前 , 5F
Preorder的第一個才是root
08/11 23:35, 5F
推
08/12 00:00, 7年前 , 6F
先還原成BT再Preorder一次
08/12 00:00, 6F
→
08/12 00:01, 7年前 , 7F
請問由後序G可知,左子為C右子為D
08/12 00:01, 7F
→
08/12 00:02, 7年前 , 8F
剩下的AIBH如何追蹤
08/12 00:02, 8F
推
08/12 00:51, 7年前 , 9F
08/12 00:51, 9F
推
08/12 00:54, 7年前 , 10F
有點難用說的 基本概念就是inorder postorder的追蹤順
08/12 00:54, 10F
→
08/12 00:54, 7年前 , 11F
序不一樣 一個是先左中右 一個是左右中
08/12 00:54, 11F
→
08/12 11:55, 7年前 , 12F
感謝詳解!
08/12 11:55, 12F
‣ 更多 eduzone 的文章
文章代碼(AID): #1RRlWuMC (Grad-ProbAsk)