树/二叉树的基本性质

(一:树的基本性质)P_126

1.树中的节点数等于所有节点的度数加1(N=1+ N1+2N2+3N3+……=No+N1+N2+N3+……)

2.度为m的树中第i层上最多有m^(i-1)个节点

3.高度为h的m叉树最多有(m^h - 1)/(m-1)个节点

4.具有n个节点的m叉树的最小高度为logm (n(m-1)+1) 向上取整

5.高度为h,度为m的树至少有h-m-1个节点

(二:二叉树的基本性质)P_130

1.非空二叉树上的叶子节点数等于度为2的叶子节点数+1(No=N2 + 1)

2.非空二叉树上第k层上最多有2^(k-1)个节点

3.高度为h的二叉树最多有2^h - 1

4.具有n个节点的完全二叉树的高度为log2 (n+1)向上取整 或 log2 n向下取整+1

原文地址:https://www.cnblogs.com/-slz-2/p/13547056.html