一颗有n个结点的满二叉树共有几个叶子节点和几个非终端节点

2024-12-18 18:51:20
推荐回答(1个)
回答1:

因为 二叉树中,有这样一个性质,如果其终端结点数(也就是叶子节点)的个数为n0,度为2的结点数为n2,则n0=n2+1;
假设叶子节点有x个,则度为2的个数为 x-1:
所以: 2x-1 = n; 所以 x = (n+1)/2 (满二叉树)

所以 叶子节点个数为 :(n+1)/2
非终端结点为 : (n+1)/2-1