Tree1-1 | Hexo

树的基本概念
1. 树的定义：树是N(N>=0)个结点的有限集合，N=0时，称为空树，这是一种特殊情况。
  - 任意一颗非空树中应满足：
    - 有且仅有一个特定的称为根的结点
    - 当N>1时，其余结点可分为m(m>0)个互不相交的有限集合T1，T2，…Tm,其中每个集合本身又是一棵树，
      
      并且称为根结点的子树。
  - 树的定义是递归的，是一种递归的数据结构。树作为一种逻辑结构，同时也是一种分层结构
    - 特点：
      1. 除了树的根结点外都有且仅有一个前驱结点；因此在n个结点的树中有n-1条边
      2. 树中的所有结点可以有零个或多个后继结点
2. 基本术语
  1. 结点的度：树中该结点的子结点个数
  2. 树的度：树中结点最大的度数
  3. 分支结点：度大于0的结点；
  4. 叶子结点：度等于0的结点
  5. 结点的深度、高度和层次
    - 结点的层次从树根开始定义，根结点为第1层(有些是0层开始)，以此类推；
    - 结点的深度：是从根结点开始自顶向下组成累加
    - 结点的高度：是从叶子结点开始自底向上逐层累加
    - 树的高度：是树中结点的最大层数
  6. 路径和路径长度：
    - 树中两个结点的路径：是由这两个结点之间所经过的结点序列构成的；A和K中间经过结点B和结点E
    - 而路径长度：是从路径上所经过的边的个数;结点A和结点K的路径长度为3
  7. 森林：m(m>=0)棵互不相交的树的集合
3. 树具有基本性质：
  1. $$树中的结点数等于所有结点的度数加1.$$
  2. $$度为m的树中第i层上至多有 m^{i-1} 个结点$$
  3. $$高度为h的m叉树至多有(m^h-1)/(m-1)个结点$$
  4. $$具有n个结点的m叉树的最小高度为\ulcorner\log_m(n(m-1)+1)\urcorner$$
4. 扩展：
  - 要使具有n个结点、度为4的树的高度最大，那么就要使得每一层得结点数尽可能得少，除了最后一层，其余每层都为一个结点，最终树得高度为n-3.
  - 要使得度为4、高度为h得总结的个数最少，那么满足以下两个条件：
    1. 至少有一个结点有4个子结点
    2. 每一层结点数尽可能的少，结点个数为h+3
  - 要使得度为4、高度为h得总结的个数最多，则应使每一个非叶子结点的度均为4，即为满树；总结点个数最多为：$1+4+4^2+…+4^{h-1}$
  - $$\small{设数中度为i(i=0、1、2、…、n)的结点数分别为N_i,数中结点总数为N，则N=分支数+1，而分支数又等于树中各结点的度之和，即}$$
    $$N=1+N_1+2N_2+……+nN_n=N_0+N_1+2N_2+……+nN_n$$
  - 要求含有n个结点的3叉树的最小高度，那么满足条件的一定是一颗完全3叉树:$$设含有n个结点的完全3叉树的高度为h，第h层至少有1个结点，至多有3^{h-1}个结点$$
    则有：
    $$1+3^1+3^2+…+3^{h-2}<n\leqq1+3^1+3^2+…+3^{h-1}$$
    $$即：(3^{h-1}-1)/2<n\leqq(3^h-1)/2$$
    $$得： 3^{h-1}<2n+1\leqq{3^h}$$
    $$也即： h<\log_3(2n+1)+1,h\geqq{\log_3(2n+1)}$$
    $$由于h只能是正整数，h=\ulcorner\log_3(2n+1)\urcorner,故这样得3叉最少高度是\ulcorner\log_3(2n+1)\urcorner$$
    - 运用的是等比求和公式：
      $$ S_n=\frac{a_1(1-q^n)}{1-q}(q\neq1) $$
  - $$根据“树中所有结点得度数加1等于结点数”得结论，有n=\sum_{i=0}^m {i\times n_i}=n_1+2n_2+3n_3+…+mn_m+1$$
    $$又有: n=n_0+n_1+n_2+…+n_m$$
    $$所以：n_0=(n_1+2n_2+3n_3+…+mn_m+1)-(n_1+n_2+…+n_m)=n_2+2n_3+…+(m-1)n_m+1=1+\sum_{i=2}^m {(i-1)n_i}$$