[理工] 资结 Child Node

楼主: s9e0ay917 (Meg)   2018-07-05 20:55:29
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
作者: EXPCDR (EXPCDR)   2018-07-06 08:53:00
好怪 通常这样不会说他有两个子点吧,不然每个二元树的node degree就永远为2了,那就跟Strict 二元树的定义一样了我觉得他说B的左子点是empty tree不是在表达他有左子点,就只是在表达他左子点上的位置是放空树
作者: h90243768 (卤蛋菘)   2018-07-06 00:02:00
Binary tree 可以为空是 文后面有说啊 B的左子树为空树
作者: outofyou   2018-07-05 23:45:00
空的左子树,有问题吗?
作者: outofyou   2018-07-06 11:58:00
他都刻意只有说children,没有说child node,二元树里degree有0,1,2,3可能,定义好edge要有连node即可会有其他树在讨论时把leaf node的children做考虑,所以要看个别讨论的对象及个别定义的方式。
作者: EXPCDR (EXPCDR)   2018-07-06 14:37:00
那个..请问为什么二元树degree可能为3
作者: outofyou   2018-07-06 19:23:00
抱歉,我用的定义是有二元树结构的无向图中的节点degree参https://en.wikipedia.org/wiki/Tree_(graph_theory)
作者: EXPCDR (EXPCDR)   2018-07-06 22:11:00
二元树可以为空,空数node数为0,所以A错他是说所有二元树的node都有两个children,注意他不是说children node。但不是所有二元树都有node,例如空数就没有node
作者: eggy1018 (羅密歐與豬過夜)   2018-07-07 00:05:00
Binary tree 每个node 一定有两个childChild 有value 就是node, 没有就是empty

Links booklink

Contact Us: admin [ a t ] ucptt.com