1、树的基本概念　　
结点的度（Degree）：一个结点的度是其子树的个数。
树的度：树的所有结点中最大的度数。
叶结点（Leaf）：是度为0的结点；叶结点也可称为端结点。
父结点（Parent）：有子树的结点是其子树的根结点的父结点。
子结点（Child）：若A结点是B结点的父结点，则称B结点是A结点的子结点；子结点也称孩子结点。
兄弟结点（Sibling）：具有同一父结点的各结点彼此是兄弟结点。
分支：树中两个相邻结点的连边称为一个分支。
路径和路径长度：从结点n1到nk的路径被定义为一个结点序列n1 , n2 ,… , nk ，对于1<= i < k, ni是 ni+1的父结点。一条路径的长度为这条路径所包含的边（分支）的个数。
祖先结点(Ancestor)：沿树根到某一结点路径上的所有结点都是这个结点的祖先结点。
子孙结点(Descendant)：某一结点的子树中的所有结点是这个结点的子孙。
结点的层次（Level）：规定根结点在1层，其它任一结 点的层数是其父结点的层数加1。
树的高度（Height）：树中所有结点中的最大层次是这棵树的高度。（也有把根定义成高度为1的）
2、树的性质
树的结点树为所有结点度数加1（加根结点）。

度为m的树中第i层最多有m^(i-1)个结点。

高度为h的m次树至多(m^h-1)/(m-1)个结点。

具有n个结点的m次树的最小高度为logm( n(m-1) + 1 ) 向上取整。

二叉树：有限结点集合，或为空，或为一个根结点和两棵互不相交的左子树和右子树组成。
　　满二叉树：每个分支结点都有左孩子结点和右孩子结点。
• 　叶子结点都在最下一层
• 　只有度为0和2的结点
　　完全二叉树：二叉树的最下面两层的结点度数小于2，且最下面一层的叶子结点依次排列在该层的最左边的位置。
• 　某结点i为叶子结点或只有左孩子结点，则编号大于i的结点均为叶子结点
• 　结点总数为奇数时，度数为1的结点为0；偶数时，度数为1的结点为1
二叉树的性质

  1. 非空二叉树上叶子结点树等于双分支结点树加1
  2. 总分支数 = n1 + 2n2 ，总分支数 = n - 1 ，总结点数 = n0 + n1 + n2
  3. 非空二叉树上第i层上至多有2i - 1个结点
  4. 高度为h的二叉树至多有2h - 1个结点
  5. 完全二叉树中的 i 结点，若2i ≤ n，i为分支结点，否则为叶子结点；若i结点有左孩子结点，编号为2i，若i结点有右孩子结点，编号为2i + 1