数据结构中树的各种计算公式

  • 树（Tree）是n（n≥0）个结点的有限集。n=0时称为空树。在任意一棵非空树中：（1）有且仅有一个特定的称为根（Root）的结点；（2）当n>1时，其余结点可分为m（m>0）个互不相交的有限集T1、T2、…、Tm，其中每一个集合本身又是一棵树，并且称为根的子树
  • 二叉树（ Binary Tree）是n（n≥0）个结点的有限集合，该集合或者为空集（称为空二叉树），或者由一个根结点和两棵互不相交的、分别称为根结点的左子树和右子树的二叉树组成。

二叉树各种计算公式

  1. n 个节点的二叉树一共有 ((2n)!)/(n! * (n+1)!) 种
  2. n 层二叉树的第 n 层最多为 2^(n-1) 个
  3. 二叉树节点计算公式 N = n0+n1+n2，度为 0 的叶子节点比度为 2 的节点数多一个。N=1n1+2n2+1
  4. 对任何一棵二叉树 T，如果其终端节点数为 n0，度为 2 的节点数为 n2，则 n0=n2+1
  5. 具有 n 个节点的完全二叉树的深度为 log2(n) + 1
  6. 深度为k的二叉树至多有2^k－1个结点（k>1），最少有2^(k-2)个叶子结点
  7. 如果对一棵有n个结点的完全二叉树（其深度为log2n+1）的结点按层序编号（从第1层到第log2n+1层，每层从左到右），对任一结点i（1<i<n）有：

1.如果i=1，则结点是二叉树的根，无双亲；如果i>1，则其双亲是结点i／2

2.如果2i>n，则结点i无左孩子（结点i为叶子结点）；否则其左孩子是结点 2i.

3.如果2i+1>n，则结点i无右孩子；否则其右孩子是结点2i+1 8. 总结点为N，n为奇数叶子结点等于 (n+1)/2，偶数等于n/2 9. 任一树中，结点数=度数对应结点树+1 10. 计算结点，结点数=分叉树+1，度之和等于所有结点数-1 11. 含有n个结点的二叉链表中，链域一共有2n个，非空链域n-1，空n+1 12. 二叉排序树查找时间复杂度O(n)，平衡二叉排序树O(logn)

Contents