Re: [理工] [DS] Subtree
※ 引述《r596twy (湯姆熊)》之銘言：
: [T or F]
: A是B的subtree 且 B是C的subtree
: 所以A是C的subtree
: 答案是False
: 為什麼阿
: subtree的定義不是只要能從這棵樹中找到one-to-one mapping function
: 就算是subtree嗎??
: 還是說有其他限制條件??
: 還是我整個定義都搞錯了...
這裡有從wiki以及他相關連出去的地方找到的定義:
(General)A subtree of a tree T is a tree consisting of a node in T and all of its
descendants in T. (This is different from the formal definition of subtree
used in graph theory.[2]) The subtree corresponding to the root node is the
entire tree; the subtree corresponding to any other node is called a proper
subtree (in analogy to the term proper subset).
(Graph theory)A tree G' whose graph vertices and graph edges form subsets of
the graph vertices and graph edges of a given tree G .
按照各位的意思 應該是以Root的兒子為Root而產生subtree
可是看這兩個定義 感覺不出有這種意思呢...
比較像是G=(V,E)中 E' = E交集(V'xV')
也就是induced subgraph by V'
怎會這樣呢...還是我誤解這兩段定義的意思??
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 114.36.12.20
推
01/12 16:34, , 1F
01/12 16:34, 1F
→
01/12 16:35, , 2F
01/12 16:35, 2F
討論串 (同標題文章)