树与二叉树的相关概念
结点的度：一个结点拥有结点的数，1结点度为2,3结点度为1，7结点度为0
树的度：所有结点度数最高的数，上图树的度为2
叶子结点：树的末尾，没有孩子结点的结点，4、5、7、8是叶子结点
分支结点：有相应的分支，2、3、6
内部结点：非根节点也非叶子结点
父结点、子节点：是相对关系的，1和2,1是父结点，2是子结点
兄弟结点：属于同一个父结点，4、5
层次：树的层次，上图是4层
满二叉树：没缺失的部分
完全二叉树：除了最底层都是满的，且底层是从左到右排列的树
非完全二叉树：不满足完全二叉树的条件的树
二叉树的遍历
层次遍历：按层次顺序 1 2 3 4 5 6 7 8
前序遍历：根 左 右顺序 1 2 4 5 7 8 3 6
中序遍历：左 根 右顺序 4 2 7 8 5 1 3 6
后序遍历：左 右 根顺序 4 8 7 5 2 6 3 1
反向构造二叉树
需要知道两种遍历序列
树转二叉树
从根开始把树一个结点的最左边的孩子结点转为二叉树的结点的左子结点，把该左子结点的兄弟结点转为该左子结点的右子结点
查找二叉树
根的左子结点比根结点小，右子结点都要比根结点大，这种二叉树叫做查找二叉树或者二叉排序树，极大提高查找的速率
最优二叉树（哈夫曼树）（重点）
用于哈夫曼编码，该编码是一种用于压缩方式
树的路径长度：左右结点的数相加
权：某个叶子结点上面的数值就是权，代表某一种字符出现的频度
带权路径长度：路的长度*全值，比如2的路的长度是2
树的带权路径长度（树的代价）：把所有结点的带权路径长度相加
构造一个哈夫曼树的要达到的效果是让一颗树的带权路径长度是最短的情况
例题：
线索二叉树
在二叉树的基础上用虚线的箭线把结点串起来
线索二叉树目的是因为二叉树很多指针是空的，把空闲的资源利用起来
先把二叉树序列写出来，有缺失的结点的前驱结点用绿色箭头，后驱结点用红色箭头
平衡二叉树
定义：任意结点的左右子树深度相差不超过1
每结点的平衡度只能为-1、0或1
平衡度=结点的左子数深度-结点的右子数深度
不平衡的二叉树基本思路把它折叠成平衡二叉树，数列的中间数一般就为平衡二叉树的根节点
一个二叉树越平衡查找效率越高
