1，什么是树？
2，什么是树的度？
3，结点的层次
4 线性结构和树结构的比较
5 树的三种存储结构（双亲表示法，孩子表示法，孩子兄弟表示法）
6，二叉树的定义
7，满二叉树 和 完全二叉树
8 ，二叉树的性质
9， 二叉树的存储结构
1，什么是树？
树是n个结点的有序集合，n = 0 时为空树，
1，在非空树中，有且仅有一个可以称为根的结点。
2，n>1时，其余结点可分为m个互不相交的有限集，其中每一个集合本身是一颗树，并且称为根的子树。
注意子树一定是不可以相交的
2，什么是树的度？
1，树内各结点的度的最大值
2，结点拥有的子树数称为结点的度
3，结点的层次
从根开始定义，根为第一层。根的孩子为第二层，依次类推。
树中结点的最大层次称为树的深度或高度。
4 线性结构和树结构的比较
- 线性结构
第一个数据元素无前驱
最后一个数据元素无后继
中间元素，一个前驱一个后继 - 树结构
根结点，无双亲，唯一
叶结点，无孩子，可以有多个
中间结点，一个双亲，多个孩子。
5 树的三种存储结构（双亲表示法，孩子表示法，孩子兄弟表示法）
- 双亲表示法
1，连续的空间地址作储存结点
2，data 数据域 指针域指向双亲
缺点是找不到孩子结点
改进方式是再增加一个指针域指向孩子结点 - 孩子表示法
设计思想：每个结点有多个指针域，每个指针指向一棵子树的根结点。这种方法叫多重链表表示法
方案一：每个结点指针域的个数等于树的度
当所有的结点度数大致相等时才会高效
方案二：每个结点有三部分构成data 数据域，degree度域，指针域
但是需要维护每个结点的度的数值，运算上带来时间上的损耗。
孩子表示法：有2部分构成
1，顺序存储结构存储一个一维数组，数据域放data，指针域指向该结点的孩子链表
2，线性表中的元素，数据域放的是指向该元素在数组中的下标。指针域指向下一个孩子结点的指针
缺点：找不到双亲 ，在表头结点里再加一个指针域，指向父母结点。 - 孩子兄弟表示法
听名字就知道它的指针域要指向孩子和兄弟
孩子指针域：指向第一个孩子结点
兄弟指针域：指向此结点右边的兄弟结点
6，二叉树的定义
二叉树是n个结点的有限集合，该集合或者为空集（空二叉树）或者由一个根结点和两颗互不相交的，分别称为根结点的左子树和右子树的二叉树组成。
左子树和右子树是有顺序的，次序不能颠倒。
7，满二叉树 和 完全二叉树
所有的分支结点都存在左子树和右子树。
对于一个n个结点的二叉树，如果编号为i的结点与同样深度的满二叉树中编号为i的结点位置完全一致。
给每个结点按照满二叉树的结构逐层顺序编号，如果编号出现空档，说明不是完全二叉树。否则就是。
8 二叉树的性质
1在二叉树的第i层上最多有2^（i-1） 个结点
2深度为k的二叉树，至多有(2^k) - 1个结点
3n0 = n2 + 1
假设终端结点个数为n0，度为2的结点个数为n2，度为1的结点个数为n1
2个等式
n = n1 + n2 + n0
总线数 = n-1 = n1 + 2n2
4二叉树的深度为|log 2 n| + 1
|x|代表不大于x的最大整数
5对一颗有n个结点的完全二叉树,对任一结点i
5.1i = 1 ,结点i 是二叉树的根，无双亲。若i > 1则其双亲是结点|i / 2|
5.2如果2i > n 则结点i 无左孩子（结点i 为叶子结点）。否则其左孩子为结点2i
5.3如果2i + 1 > n 则结点i无右孩子
（5，1先推导完全二叉树的左侧左孩子的特点，2，再推导中间结点和左孩子的特点关系）
否则其右孩子是结点2i+ 1
9 二叉树的存储结构
- 二叉树的顺序存储结构
用一维数组存储二叉树中的结点
把不存在的结点设为^
一般用于完全二叉树 - 二叉链表
结点 一个数据域，2个指针域
如果有需要还可以增加一个指向双亲的指针域，那么就成三叉链表了
