• 一、树的定义与基本术语
  • 1、树的定义
  • 2、树的基本术语
    • 结点分类
    • 结点间的关系
    • 树的其他相关概念
    • 线性结构与树结构区别
• 二、二叉树
  • 1、二叉树的定义
  • 2、特殊的二叉树
    • 斜树
    • 满二叉树
    • 完全二叉树
  • 3、二叉树的性质
    • 性质1
    • 性质2
    • 性质3
    • 性质4
    • 性质5

一、树的定义与基本术语

1、树的定义

• 树是n（n>=0）个结点的有限集合
• 如果n=0，称为空树；
• 如果n>0, 称为非空树, 对于非空树:
  (1)有且仅有一个特定的称为根(Root)的结点；
  (2)当n>1时，其余结点可分为m(m>0)个互不相交的有限集T1、T2、……、Tm，其中每一个集合本身又是一棵树，并且称为根的子树(SubTree)。
  （此为递归定义）

注意:
1.n>0时根结点是唯一的，不可能存在多个根结点。
2.m>0时，子树的个数没有限制，但它们一定是互不相交的。

2、树的基本术语

结点分类

• 结点：包含一个数据元素及若干指向其子树的分支
• 结点的度：结点拥有的子树数
  
• 叶结点（终端结点）：度为0的结点[没有子树的结点]
• 分支结点(非终端结点)：度不为0的结点[包括根结点],除根结点之外分支结点也称内部结点

结点间的关系

• 孩子：结点的子树的根[直接的后继，可能有多个]
• 双亲：孩子的直接前驱[最多只能有一个]
• 兄弟：同一双亲的孩子
• 子孙：以某结点为根的树中的任一结点都称为该结点的子孙
• 祖先：从根到该结点所经分支上的所有结点

树的其他相关概念

• 层次：根结点为第一层，其孩子为第二层，依此类推
• 深度：树中结点的最大层次
• 有序树：子树之间存在确定的次序关系。
• 无序树:子树之间不存在确定的次序关系。
  （如果将树中结点的子树看成从左至右是有次序的，不能互换的，则该树称为有序树，否则称为无序树。）
• 森林：互不相交的树的集合。对树中每个结点而言，其子树的集合即为森林。

任何一棵非空树是一个二元组：  Tree = （root，F）
其中：root 被称为根结点，F被称为子树森林

线性结构与树结构区别

二、二叉树

对于这种在某个阶段都是两种结果的情形，比如开和关、0和1、真和假、上和下、对与错、正面和反面等，都适合用树状结构来建模，而这种树是很特殊的树状结构，叫做二叉树。

1、二叉树的定义

• 二叉树(Binary Tree)是n(n≥0)个结点的有限集合，该集合或者为空集(称为空二叉树)，或者由一个根结点和两棵互不相交的、分别称为根结点的左子树和右子树的二叉树组成。如下图：
  

• 每个结点最多有两棵子树，所以二叉树中不存在度大于2的结点。

• 左子树和右子树是有顺序的，次序不能任意颠倒。

• 即使树中某结点只有一棵子树，也要区分它是左子树还是右子树。如下图，树1和树2是同一棵树，但它们却是不同的二叉树。
  

• 二叉树具有五种基本形态：

1. 空二叉树；
2. 只有一个根结点；
3. 根结点只有左子树；
4. 根结点只有右子树；
5. 根结点既有左子树又有右子树。
   如果有三个结点，则存在如下五种二叉树：
   

2、特殊的二叉树

斜树

所有结点都只有左子树的二叉树叫左斜树。所有结点都只有右子树的二叉树叫右斜树。

• 斜树有很明显的特点，就是每一层都只有结点，结点的个数与二叉树的深度相同。
• 其实线性表的结构可以理解为树的一种极为特殊的表现形式。

满二叉树

在一棵二叉树中，如果所有分支结点都存在左子树和右子树，并且所有叶子都在同一层上，这样的二叉树称为满二叉树
如下图：

• 满二叉树的特点：

1. 叶子只出现在最下一层，出现在其他层就不可能达到平衡。
2. 非叶子结点的度一定是2。
3. 在同样深度的二叉树中，满二叉树的结点个数最大，叶子个数也最多。

完全二叉树

如果对一颗有n个结点的二叉树按层序排序，如果编号为i（1<=i<=n）的结点与同样深度的满二叉树中编号为i的结点在二叉树中位置完全相同，则称这颗二叉树为完全二叉树

• 完全二叉树的一些特点

1. 叶子结点只出现在最下面两层
2. 最下层的叶子一定集中在左部连续位置
3. 倒数第二层，如果有叶子结点，一定在右部连续位置
4. 如果结点度为1，则一定只有左孩子
5. 同样结点数的二叉树，完全二叉树的深度最小

3、二叉树的性质

性质1

在二叉树的第i层上至多有2^i-1个结点（i>=1）

性质2

深度为k的二叉树至多有2^k-1个结点（k>=1）

性质3

对任意一个二叉树，如果其终端结点数为n₀，度为2的结点数为n₂，则n₀ = n₂+1。

性质4

具有n个结点的完全二叉树的深度为[log₂n]+1（[]表示向下取整）

性质5

如果对一颗有n个结点的完全二叉树的结点按层序编号，对任意一个结点i（1<=i<=n）有：
1. 如果i=1，则结点i为二叉树的根，无双亲；如果i>1，则其双亲为结点[i/2]。
2. 如果2i>n，则则结点i无左孩子（且结点i为叶子结点）；否则其左孩子为结点2i。
3. 如果2i+1>n，则则结点i无右孩子；否则其右孩子为结点2i+1。