[理工] 資結 Child Node

[s9e0ay917 (Meg)]

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://www.ptt.cc/bbs/Grad-ProbAsk/M.1530795333.A.E1D.html
※ 編輯: s9e0ay917 (223.140.130.240), 07/05/2018 21:36:26
→ outofyou: 空的左子樹，有問題嗎？
B只有一個child node但敘述上說B有2個child node 我的問題在這裡
※ 編輯: s9e0ay917 (223.140.130.240), 07/06/2018 00:02:04
→ h90243768: Binary tree 可以為空
這個明白：) 所以圖片的B節點有兩個child node，這是正確的嗎？
※ 編輯: s9e0ay917 (223.140.130.240), 07/06/2018 00:03:10
→ h90243768: 是 文後面有說啊 B的左子樹為空樹
這樣的話，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
推 EXPCDR: 好怪 通常這樣不會說他有兩個子點吧，不然每個二元樹的no
→ EXPCDR: de degree就永遠為2了，那就跟Strict 二元樹的定義一樣了
推 EXPCDR: 我覺得他說B的左子點是empty tree不是在表達他有左子點，
→ EXPCDR: 就只是在表達他左子點上的位置是放空樹
謝謝你的解釋，我好像明白你的意思，但這網站有題練習題(我放在這裡了)，說明每個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
→ outofyou: 他都刻意只有說children，沒有說child node，
→ outofyou: 二元樹裡degree有0,1,2,3可能,定義好edge要有連node即可
→ outofyou: 會有其他樹在討論時把leaf node的children做考慮，
→ outofyou: 所以要看個別討論的對象及個別定義的方式。
推 EXPCDR: 那個..請問為什麼二元樹degree可能為3
→ outofyou: 抱歉，我用的定義是有二元樹結構的無向圖中的節點degree
→ outofyou: 參https://en.wikipedia.org/wiki/Tree_(graph_theory)
推 EXPCDR: 二元樹可以為空，空數node數為0，所以A錯
→ EXPCDR: 他是說所有二元樹的node都有兩個children，注意他不是說c
→ EXPCDR: hildren node。但不是所有二元樹都有node，例如空數就沒
→ EXPCDR: 有node
很謝謝你的解釋！！
→ eggy1018: Binary tree 每個node 一定有兩個child
→ eggy1018: Child 有value 就是node, 沒有就是empty
謝謝你，我了解了:)
※ 編輯: s9e0ay917 (42.77.129.85), 07/09/2018 13:05:17