【数据结构与算法 CC++】树二叉树计算公式总结

0.变量说明

• 度为 m m m 的结点数 = n m n_m nm​;
• i i i : 第 i i i 层 或 第 i i i 号结点;
• h h h : 树的高度;
• c e i l ceil ceil 向上取整, f l o o r floor floor 向下取整 ;

1. 树的计算公式 (通用)

1. 总 结 点 数 = n 0 + n 1 + n 2 + . . . + n m = 总 分 支 数 + 1 总结点数 =n_0+n_1+n_2+...+n_m = 总分支数 + 1 总结点数=n0​+n1​+n2​+...+nm​=总分支数+1 ;
2. 总 分 支 数 = 1 ∗ n 1 + 2 ∗ n 2 + . . . + m ∗ n m 总分支数 = 1*n_1+2*n_2+...+m*n_m 总分支数=1∗n1​+2∗n2​+...+m∗nm​ ;
3. 度为 m m m 的树的第 i i i 层上最多有 m i − 1 m^{i-1} mi−1 个结点 ( i ≥ 1 ) (i\ge1) (i≥1) ;
4. 高度为 h h h 的 m m m 叉树最多有 m h − 1 / m − 1 m^h-1/m-1 mh−1/m−1 个结点;
5. 具有 n n n 个结点的 m m m 叉树的最小高度为 c e i l ( l o g m ( n ( m − 1 ) + 1 ) ) ceil (log_m(n(m-1)+1)) ceil(logm​(n(m−1)+1)) ;

2. 二叉树计算公式

1. 非空二叉树中 n 0 = n 2 + 1 n_0 = n_2+1 n0​=n2​+1 ;
2. 非空二叉树中 结点数为 n n n时, 边 数 = n − 1 边数=n-1 边数=n−1 ;
3. 高为 h h h 的二叉树 最多 有 2 h − 1 2^{h-1} 2h−1 个结点 ;

3. 满二叉树计算公式

1. 编号问题 : 编号为 i i i 的结点
   • 双亲为 f l o o r ( i / 2 ) floor(i / 2) floor(i/2)
   • 左孩子编号为 2 i 2i 2i ;
   • 右孩子编号为 2 i + 1 2i+1 2i+1

4. 完全二叉树计算公式

1. 编号问题 : 编号为 i 的结点 :
   • i ≤ f l o o r ( n / 2 ) i\le floor(n/2) i≤floor(n/2) 则 i 为分支结点, 否则 i 就是叶子结点
   • 按层编号, 当编号为 i 的结点为 叶子结点或只含左子节点 , 则编号大于 i 的都是叶子结点;
   • 总结点数为奇数, 每个分支节点都要左右子结点;
   • 总结点数为偶数, 编号最大者( i = n / 2 i=n/2 i=n/2) 只有左子节点;
   • n个结点的完全二叉树的高度为 h = c e i l ( l o g 2 ( n + 1 ) ) h=ceil(log_2(n+1)) h=ceil(log2​(n+1)) 或 h = f l o o r ( l o g 2 n ) + 1 h=floor(log_2n)+1 h=floor(log2​n)+1;
   • 若某节点编号为 i :
     • 2 i ≤ n 2i\le n 2i≤n i的左子节点编号为 2 i 2i 2i, 否则就是没有左子节点;
     • 2 i + 1 ≤ n 2i+1\le n 2i+1≤n i的右子节点编号为 2 i + 1 2i+1 2i+1, 否则就是没有右子节点;
     • 最后一个分支结点的编号为 f l o o r ( n / 2 ) floor(n/2) floor(n/2) ;