二叉树二度节点和叶子节点的数量关系

二叉树二度节点和叶子节点的数量关系:

假设共有节点 N 个, 二度几点 x 个,一度节点y个, 则叶子节点个数(设为z)?

N个节点,那么共有树枝N – 1个

1个二度节点有2个树枝,叶子没有,一度节点有1个,那么推导出一共有 2x + y 个

2x + y = N – 1;

x   + y + z = N;

由以上两式得出,z = x + 1;

完毕。

叶子节点的个数=二度节点的个数+1

发表评论

电子邮件地址不会被公开。 必填项已用*标注

16 + 15 =

− 5 = 3