二叉树相关计算

树的结点的度:这个节点的子树的个数
二叉树中的节点只能分为度为: 0, 1,2;
设二叉树的节点总数:N
度为0,1,2的节点个数为:N0, N1, N2
N = N0 + N1 + N2
二叉树的边总数:N- 1
N- 1 = N1 + 2 * N2

2式带入1式的得:N2+ 1 = N0 + N1
如果要叶子结点多,则N1= 0;

把N2用N0代替带入1式得:N = N0 – 1 + N0;
得到叶子结点计算公式: N0 = (N+ 1)/ 2;

高度为h满的二叉树

节点个数:2^h – 1
叶子结点个数:2^(h-1)


版权声明:本文为qq_45432665原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。