什么是叶子节点,根节点?(7)某二叉树中有n个度为2的结点,则该二叉树中的叶子结点数为(A)A)n+1B)n-1C)2nD)n/2怎么算的阿?

Question

什么是叶子节点,根节点?
(7) 某二叉树中有n个度为2的结点,则该二叉树中的叶子结点数为(A)
A) n+1
B) n-1
C) 2n
D) n/2
怎么算的阿?

Answer 1

结点的孩子结点个数即为该结点的度.
度为0的结点叫叶子结点.
处在树的最顶端(没有双亲)的结点叫根结点.
设该二叉树总结点数为N,叶子结点个数为n0,度为1的结点个数为n1.
下面可得两等式:
(1) N = n + n0 + n1;
依据:很显然,二叉树总结点数等于度分别为0,1,2的结点个数总和.
(2) N = 2n + n1 +1;
依据:二叉树的树杆(即左右斜线)数等于总结点数减1,这个隐含的条件很关键哦!
由(1)(2)两式即可求得:n0=n+1;
故答案为A
----------------------
回答完毕!