树

树，这是一棵树，这是一种非线性结构。在前面我们所学习的都是线性结构，而他们的特点是表中的元素相互之间都是线性关系，逻辑较为清晰，容易进行查找、插入和删除操作，这种数据结构描述的是一种元素只唯一前驱元素和唯一后继元素的模型。
而树这种非线性结构是相对于线性结构而言的，相比起线性结构中元素之间一对一的关系，树型结构中元素之间是一对多的关系。树是一种十分重要的非线性结构。

树的基本概念

树的定义

树是n（n>=0）个元素的的有限集合，既然被叫做树，那么自然有根有叶子。在任何一颗非空树中：

• 有且仅有一个节点被称为根节点，而且我们一般把根节点提到整棵数的最上面
• 当n>1时，除根以外的其余节点可一被分为m（m>0）个互不相交的有限集合T1，……,Tn,其中每一个集合本身又是一颗树，并且称为根的子树

这真的是个很绕的东西，不过由此可以看出，树的定义是具有递归性的，即树中有树，当一颗树只有一个节点时，该节点被称为根节点。当有多个节点时，除了根节点外，它还有多棵子树，每棵子树都互不相交。

树的相关术语

一般而言，就像图片描述的，图中的圆圈代表节点，线代表边，圈内的东东就是这个节点的信息。

• 节点：树中的数据元素称为节点，每个节点都保存了该节点的信息，即数据元素和数据项与数据元素之间的关系
• 节点的度：节点拥有子树的个数
• 树的度：树中各节点的度的最大值
• 叶子节点： 树中度为0的节点，也叫做终端节点
• 分支节点： 树中度不为0的节点，称为分支节点或非终端节点
• 儿子：节点子树的根，儿子节点简称为子节点
• 父亲：有儿子的就是父亲，父亲节点简称为父节点
• 兄弟：有同一父亲的节点被称为兄弟节点
• 堂兄弟：位于同一层，但是没有同一父亲的子节点称为堂兄弟
• 树的深度：树中节点节点的最大层数，图中的树深度为3
• 节点的层次：从根节点开始，根为第一层，根的孩子为第二层，以此类推，如果某节点在第k层，那么其子树的根就在k+1层。
• 根：唯一一个没有前驱的节点（无父节点），此节点为根节点
• 森林： 指m棵互不相交的树的集合，一棵树的子树就构成一个森林
• 有序树： 如果树中节点的各棵子树规定从左至右是有序的（不能互换），则称为有序树，否则称为无序树。二叉树就是一种有序树。
• 无序树：不是有序树就是无序树了（= =||），就是节点的各个子树可以互换位置

二叉树

树型结构中有一种特殊的树叫做二叉树，二叉树的结构也比较简单，规律性较强，并且可以证明，即使一般的树也能转化成二叉树。而且许多实际问题抽象出来的数据结构往往就是二叉树的形式。

二叉树的定义

二叉树是个有限元素的集合，该集合为空或者由一个根和两个互不相交的左子树和右子树组成。在二叉树中，一个元素也称为一个节点。

二叉树的基本特征：

• 每个节点最多只有两棵子树，即不存在度大于2的节点
• 左子树和右子树次序不能颠倒，即二叉树是有序树，而且哪怕只有
  一颗子树，也要区分是左子树还是右子树。

二叉树有五中基本形态：

• 空集
• 根有两颗子树
• 根只有一颗子树（左子树或右子树）
• 根没有子树

在二叉树中有两种特殊的二叉树：满二叉树和完全二叉树

满二叉树

在一棵树中所有的分支节点都存在左子树和右子树，并且所有的叶子节点都在同一层上，这样的二叉树称为满二叉树。

满二叉树

完全二叉树

一棵深度为k且具有n个节点的二叉树，对树中节点按从上至下，从左至右的顺序进行编号，当且仅当节点都与深度为k的满二叉树中编号从1至n的节点一一对应
时，才称这棵二叉树为完全二叉树。显然满二叉树也是完全二叉树的一种。
完全二叉树的特点：

• 叶子节点只可能在层次最大的两层上出现

• 对任一节点，其右分支下的儿子的最大层次为h，则其左分支下的儿子最大层次为
  h或h+1

  
  完全二叉树