树的基本概念

概念：
        树：(Tree)是n (n≥0)个结点的有限集。n=0时称为空树。在任意一棵非空树中: (1)有且仅有一一个特定的称为根(Root) 的结点: (2)当n>1时，其余结点可分为m (m>0)个互不相交的有限集T1、T2、...*. T.其中每一个集合本身又是一棵树，并且称为根的子树(SubTree)。简便来说，n=0时为空树，n≠0，一个树有且只有一个根，其他的都是子树，子树之间是不相交的。

        叶子节点/终端节点：该结点下无子树,没有分支。
        非叶子节点/非终端节点：该结点下有子树。

        度：

• 结点的度：一个节点含有的子树的个数；
• 树的度：树中结点度的最大值

        树的深度/高度：树的层数，根节点为第1层开始数。（下图中，a数的深度/高度为5）

         二叉树：（Binary Tree)是n(n≥0）个结点的有限集合,该集合或者为空集(称为空二叉树),或者由一个根结点和两棵互不相交的、分别称为根结点的左子树和右子树的二叉树组成。简易理解为如果有分支，最多有2个。

• 每个结点最多只能有2个子树，也就是说二叉树的度必须 ≤ 2
• 二叉树的子树有左右之分，左右次序不能颠倒
• 二叉树有5种形态：空树（空二叉树）、只有一个根节点、根+左子树、根+右子树、根+左子树+右子树

满二叉树：每一层节点均达到最大值，叶子结点在同一层。假设树的深度为k，结点个数为2^k-1。

完全二叉树：当前树除了最下面一层外，其余层均满，而最下面一层的结点均靠左。