本博客摘自《王道数据结构》，仅用于学习和记录。
树形结构框架
树的定义
树是n（n≥0）个节点的有限集。当n=0时，称为空树。在任意一颗非空树中应满足：
（1）有且仅有一个特定的称为根的结点
（2）当n>1时，其余节点可分为m(m>0)个互不相交的有限集T1，T2,’’’,Tm,其中每个集合本身又是一棵树，并且称为根的子树
树的定义是递归的，即在树的定义中又用到了其自身，树是一种递归的数据结构。树作为一种逻辑结构，同时也是一种分层结构，具有以下两个特点：
1）树的根结点没有前驱，除根结点外的所有结点有且只有一个前驱
2）树中所有结点可以有零个或多个后继
树适合于表示具有层次结构的数据。树中的某个结点（除根结点外）最多只和上一层的一个结点（即其父结点）有直接关系，根结点没有直接上层结点，因此在n个结点的树中有n-1条边。而树中每个结点与其下一层的零个或多个结点（即其子女结点）有直接关系。
基本术语
1）考虑结点K。根A到结点K的唯一路径上的任意结点，称为结点K的祖先。如结点B是结点K的祖先，而结点K是结点B的子孙。路径上最接近结点K的结点E称为K的双亲，而K为结点E的孩子，根A是树中唯一没有双亲的结点。有相同双亲的结点称为兄弟，如结点K和结点L有相同的双亲E，即K和L为兄弟。
2）树中一个结点的孩子个数称为该结点的度，树中结点的最大度数称为树的度。如结点B的度为2，结点D的度为3，树的度为3.
3）度大于0的结点称为分支结点（又称为非终端结点）；度为0（没有子女结点）的结点称为叶子结点（又称终端结点）。在分支结点中，每个节点的分支数就是该结点的度。
4）结点的深度、高度和层次。
结点的层次从树根开始定义，根结点为第1层，它的子节点为第2层，以此类推。双亲在同一层的结点为堂兄弟，图中结点G与E,F,H,I,J互为堂兄弟。
结点的深度是从根结点开始自顶向下逐层累加的。
结点的高度是从叶结点开始自底向上逐层累加的。
树的高度（或深度）是树中结点的最大层数。图中树的高度是4。
5）有序树和无序树。树中结点的各子树从左到右是有次序的，不能互换，称该树为有序树，否则称为无序树。假设图中为有序树，若将子结点位置互换，则变成一颗不同的树。
6）路径和路径长度。树中两个结点之间的路径是由这两个结点之间所经过的结点序列构成的，而路径长度是路径上所经过的边的个数。
7）森林。森林是m(m≥0)棵互不相交的树的集合。森林的概念与树的概念十分相近，因为只要把树的根结点删去就成了森林。反之，只要给m棵独立的树加上一个结点，并把这m棵树作为该结点的子树，则森林就变成了树。
树的性质
树具有如下最基本的性质：
1）树中的结点数等于所有结点的度数加1。
2）度为m的树中第i层上至多有m(i-1)个结点(i≤1)。
3）高度为h的m叉树至多有(mh-1)/(m-1)个结点。
4）具有n个结点的m叉树的最小高度为「logm(n(m-1)+1)」。
