树的直径

  • 带权：树形DP
  • 不带权：经典做法
    • 任取一点作为起点，找到距离该点最远的点u
    • 从u开始找到最远的一点v，u-v就是一条直径

树的重心

重心是指树中的一个结点，如果将这个点删除后，剩余各个连通块中点数的最大值最小，那么这个节点被称为树的重心。

树的中心

树的中心指在树中找到一个点，使得该点到树中其他结点的最远距离最近。

二叉树

基本定义：
二叉树指树中节点的度不大于2的有序树。
二叉树是一棵空树，或者是一棵由一个根节点和两棵互不相交的分别被称为左子树和右子树组成的非空树，左子树和右子树同样是二叉树。

特殊类型：
满二叉树：指一棵二叉树只有度为0的节点和度为2的节点，且所有度为0的节点均在同一层。
完全二叉树：深度为k，有n个节点的二叉树，当且仅当其每一个节点都与深度为k的满二叉树中编号为1-n的节点一一对应时，称为完全二叉树

相关术语：
节点：包含数据元素以及若干指向子树分支的信息
节点的度：一个节点拥有子树的数目
叶子节点：节点度为0或者没有子树的节点
分支节点：度不为0或者有子树的节点
树的度：指数中所有节点的度的最大值
节点的层次：从根节点开始，假设根节点为第1层，根节点的子节点为第2层，依此类推，如果某一个节点位于第L层，则其子节点位于第L+1层
树的深度：也称为树的高度，树中所有节点的层次最大值称为树的深度
有序树：如果树中各棵子树的次序是有先后次序，则称该树为有序树
无序树：如果树中各棵子树的次序没有先后次序，则称该树为无序树
森林：由m（m≥0）棵互不相交的树构成一片森林。如果把一棵非空的树的根节点删除，则该树就变成了一片森林，森林中的树由原来根节点的各棵子树构成

二叉树的性质：
a. 二叉树的第i层上至多有2i - 1 i >= 1个节点
b. 深度为h的二叉树至多含有2h - 1个节点
c. 若在任意一棵二叉树中，有n0个叶子节点，有n2个度为2的节点，则必有n0=n2+1
d. 具有n个节点的满二叉树深为log2n+1
e. 若对一棵有n个节点的完全二叉树进行顺序编号（1≤i≤n），那么，对于编号为i（i≥1）的节点：
当i=1时，该节点为根，它无双亲节点 。
当i>1时，该节点的双亲节点的编号为i/2 。
若2i≤n，则有编号为2i的左节点，否则没有左节点。
若2i+1≤n，则有编号为2i+1的右节点，否则没有右节点。