Re: [問題] 關於binary tree如何畫
前序 JCBADEFIGH
中序 ABCEDFJGIH
前序的順序就是root、左子樹、右子樹
中序的順序就是左子樹、root、右子樹
從前序給的順序,你就可以先推斷J是此樹的root
而將J為root代入中序來看,ABCEDF就是左樹、GIH是右樹
再看前序第二個是C,表示C為ABCEDF左樹的root。
再切成AB左樹和EDF右樹…(略)
以此類推可推出C的左樹。
就變成
J
/
C
/
B
/
A
那繼續往推C的右樹EDF,前序的下一個是D,將EDF切成左樹E和右樹F。
而J的左樹就完成了!!
即變成
J
/
C
/ \
B D
/ / \
A E F
相信聰明的你以舉一反三的方式,就可以完成這棵樹嘍!!
解為:
J
/ \
C I
/ \ / \
B D G H
/ / \
A E F
再補充一下,這類型的題目解完之後可以驗算一下。
也就是自己以圖形跑一次前序和中序看看是否為題目的樣子嘍!!
※ 引述《francis79458 (FC)》之銘言:
: 想請教 如果一個樹的題目 給了我 前序 跟 中序
: 那要如何去研究怎麼畫出這個樹的樣子?
: 像是給前序JCBADEFIGH 中序ABCEDFJGIH
: 要如何下手呢?
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 122.118.165.186
※ 編輯: castin 來自: 122.118.165.186 (07/19 16:06)
推
08/02 18:42, , 1F
08/02 18:42, 1F
推
10/20 05:46, , 2F
10/20 05:46, 2F
推
11/15 01:02, , 3F
11/15 01:02, 3F
討論串 (同標題文章)
本文引述了以下文章的的內容:
完整討論串 (本文為第 2 之 2 篇):