树

数是拥有n个结点的有限集，n=0时为空树，任意一个非空树中 ，有且仅有一个特定的称为根，当n>1的时候，其余的结点可分为m个互不交集的有限集，每一个集合又是一个树，称为子树

• n>0时根结点是唯一的，不可能存在多个根结点
• m>0的时候不同的子树不能有交集，

结点拥有的子树称为结点的度。 度为0 的为叶子结点。度不为0的称为分支结点。分支结点也称作内部结点。树的度，为树中各个结点中最大的度的数。

结点的层次 从根开始定义起，根为第一层，根的孩子为第二层，依次类推。双亲在同一层的结点互为兄弟结点，树中的最大层次为树的深度。

树中的结点的各子树看成从左到右 是有次序的不能交换的，则成为有序树，否则成为无序数。

森林是m棵互不相机的树的集合。

树的几种存储结构

双亲表示法: 数据域和parent指针
孩子标示法: 数据域和多个孩子指针，孩子指针的个数取决于树度的个数，即各个结点(各个子树)的度的最大值。 还有一种方案是各个结点的孩子指针的个数为各个子结点的度， 这样的话空间得到了极大的控制，但是时间方面性能稍差。 
兄弟标示法: 数据域，孩子结点的指针，兄弟结点的指针

二叉树 是由n个结点的有限集合，该集合或者为空集，或者有一个根结点和2棵互不相交的，分别称为左子树和右子树的二叉树组成。

  * 每个结点最多有二棵子树，可有有一个也可以没有
  * 左右子树是分开的，次序不能颠倒
  * 及时树中的某个结点只有一颗子树，也要区分是左子树还是右子树

特殊二叉树

*  斜树
*  满二叉树 
    1. 叶子结点只能存在最下面一层
    2. 相同深度的二叉树，满二叉树结点最多
    3. 非叶子的节点数都是2
* 完全二叉树
   理解完全二叉树只需要掌握一点，除了最下面一层，上面的不允许出现断档，因为完全二叉树与相同深度的满二叉树必须保持序号的相同。最下面一层允许出现断档也只允许最后面元素的右侧

二叉树的性质

1.在二叉树的第i层最多有2 i-1 个节点
2.一个不为空的2叉树，深度为k,,那么最多有2k-1个节点
3.n0 = n2 +1 
4.完全二叉树的深度为|log2 n|+1

二叉树的遍历

二叉树的遍历是指在根节点出发，按照某种顺序依次访问二叉树中所有的结点，使得每个结点被访问依次且仅被访问一次

1. 前序遍历 根左右
2. 中序遍历   左根右
3. 后序遍历 左右根
4. 层序遍历

我们为什么要研究这么多的方法？

我们用图形的方式来表现树的结构，应该说是非常直观和易于理解的，但是对于计算机来说，它只有循环、判断等方式，也就是说，它只会处理线性序列。因此我们这么处理之后计算机很容易的进行识别。

线索二叉树的实现

线索化的实质就是二叉链表中的空指针改为指向前驱或者后继的线索，由于前驱和后继只有遍历2叉树的时候才可以获取到，所以线索化的过程本质就是遍历的过程。

树和森林的遍历问题

树的遍历分为2种方式

• 先根遍历，先访问树的根节点 然后遍历根的每棵子树
• 后根遍历，先访问每棵子树，最后访问根节点