作者s9e0ay917 (Meg)
看板Grad-ProbAsk
標題[理工] 資結 Child Node
時間Thu Jul 5 20:55:29 2018
https://i.imgur.com/DWfMUej.jpg
想問一段敘述
給了一張圖片，並詳細敘述了以下，
我的問題在於，明明B只有一個child，為什麼他要說B有兩個children. 難道"Empty"也算
一個node嗎?
Figure 7.2.1:
*****
Node B has two children: Its left child is the empty tree and its right child
is D. (我的問題在這裡)
*****
我的疑點是從這個網站的練習題其中一題才有的，另外附上此網站的練習題
Which statement is false? (答案是A，我的疑點在D)
(A) Every binary tree has at least one node
(B) Every non-empty binary tree has exactly one root node
(C) Every non-root node in a binary tree has exactly one parent
(D) Every node in a binary tree has exactly two children
(E) None of the above
他的解釋如下：
Look carefully at the definition for a binary tree.
It states that every binary tree is either empty, or it has a root node and tw
o binary trees as children.
So, every binary tree node has two children, but not every binary tree has a n
ode.(看不太懂這句給的結論)
來源：
https://opendsa-server.cs.vt.edu/ODSA/Books/CS3/html/BinaryTree.html#def
initions-and-properties
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 223.140.130.240
※ 文章網址: https://webptt.com/m.aspx?n=bbs/Grad-ProbAsk/M.1530795333.A.E1D.html
※ 編輯: s9e0ay917 (223.140.130.240), 07/05/2018 21:36:26
1F：→ outofyou: 空的左子樹，有問題嗎？07/05 23:45
B只有一個child node但敘述上說B有2個child node 我的問題在這裡
※ 編輯: s9e0ay917 (223.140.130.240), 07/06/2018 00:02:04
2F：→ h90243768: Binary tree 可以為空07/06 00:02
這個明白：) 所以圖片的B節點有兩個child node，這是正確的嗎？
※ 編輯: s9e0ay917 (223.140.130.240), 07/06/2018 00:03:10
3F：→ h90243768: 是 文後面有說啊 B的左子樹為空樹07/06 00:08
這樣的話，B的左子樹等於一個節點嗎？可是好像不太對><
想請問child node一定要是存在的點嗎？
如果不存在，可以說一個Leaf node有兩個child node嗎？
很抱歉想釐清一些細節觀念><很感謝你的回覆
※ 編輯: s9e0ay917 (223.140.130.240), 07/06/2018 00:17:54
※ 編輯: s9e0ay917 (223.140.130.240), 07/06/2018 00:18:19
4F：推 EXPCDR: 好怪 通常這樣不會說他有兩個子點吧，不然每個二元樹的no07/06 08:53
5F：→ EXPCDR: de degree就永遠為2了，那就跟Strict 二元樹的定義一樣了07/06 08:53
6F：推 EXPCDR: 我覺得他說B的左子點是empty tree不是在表達他有左子點， 07/06 08:57
7F：→ EXPCDR: 就只是在表達他左子點上的位置是放空樹07/06 08:57
謝謝你的解釋，我好像明白你的意思，但這網站有題練習題(我放在這裡了)，說明每個bi
nary tree上的node，都一定有兩個children><
下面的解釋說即便沒有節點，每個node都會有兩個child? 感覺這個網站解釋的有點牽強
Which statement is false? (答案是A，我的疑點在D)
(A) Every binary tree has at least one node
(B) Every non-empty binary tree has exactly one root node
(C) Every non-root node in a binary tree has exactly one parent
(D) Every node in a binary tree has exactly two children
(E) None of the above
他的解釋如下：
Look carefully at the definition for a binary tree.
It states that every binary tree is either empty, or it has a root node and tw
o binary trees as children.
So, every binary tree node has two children, but not every binary tree has a n
ode.(看不太懂這句給的結論)
※ 編輯: s9e0ay917 (223.136.141.231), 07/06/2018 10:54:45
8F：→ outofyou: 他都刻意只有說children，沒有說child node， 07/06 11:58
9F：→ outofyou: 二元樹裡degree有0,1,2,3可能,定義好edge要有連node即可 07/06 12:06
10F：→ outofyou: 會有其他樹在討論時把leaf node的children做考慮， 07/06 12:07
11F：→ outofyou: 所以要看個別討論的對象及個別定義的方式。 07/06 12:08
12F：推 EXPCDR: 那個..請問為什麼二元樹degree可能為3 07/06 14:37
13F：→ outofyou: 抱歉，我用的定義是有二元樹結構的無向圖中的節點degree07/06 19:23
15F：推 EXPCDR: 二元樹可以為空，空數node數為0，所以A錯07/06 22:11
16F：→ EXPCDR: 他是說所有二元樹的node都有兩個children，注意他不是說c07/06 22:13
17F：→ EXPCDR: hildren node。但不是所有二元樹都有node，例如空數就沒07/06 22:13
18F：→ EXPCDR: 有node07/06 22:13
很謝謝你的解釋！！
19F：→ eggy1018: Binary tree 每個node 一定有兩個child07/07 00:05
20F：→ eggy1018: Child 有value 就是node, 沒有就是empty07/07 00:06
謝謝你，我了解了:)
※ 編輯: s9e0ay917 (42.77.129.85), 07/09/2018 13:05:17