树的一种生长模式

KeyTo9_Fans

我们按照如下方式随机地构造一个图$G$。

一开始，图$G$有$2$个顶点（标号为$1$和$2$）和连接这$2$个顶点的$1$条边：

1——2

接下来按照如下的方式不断地在图$G$中增加$1$个顶点和$1$条边，直到图$G$的顶点数达到$N$为止：

————————————————————
增加顶点之前，设$k$为图$G$的顶点数，那么新增的顶点的标号是$(k+1)$。

增加边之前，我们先从顶点$1$到$k$这$k$个顶点中随机选$1$个顶点，

某个顶点被选中的概率与这个顶点的度数成正比，

也就是说，顶点$i$（$1\leq i\leq k$）被选中的概率是${d(i)}/{2(k-1)}$，

其中，$d(i)$表示顶点$i$的度数，$2(k-1)$是顶点$1$到$k$的度数之和。

记顶点$x$是被选中的顶点，那么新增的边连接顶点$x$和顶点$(k+1)$。
————————————————————

例如：当$N=3$时，构造出来的图$G$有$2$种可能：

1——2
|
3

或

1——2——3

这两种构造结果出现的概率均为$50%$。

容易验证，按照这种方式构造出来的图一定是一棵树。

我们将顶点$1$定为树根。

给定$N$，求：

$(1)$树根的度数的期望值是多少？

$(2)$树高（即树根到其余顶点的最大距离）的期望值是多少？

$(3)$树叶（即度数为$1$的顶点）所占比例的期望值是多少？