7、二叉树1）概念：二叉树是结点数为0或每个结点最多只有左右两颗子树的树。4）哈夫曼树为最优二叉树。
数据结构第七章教材?1、数据结构1）线性结构（线性表，栈，队列等），我来为大家讲解一下关于数据结构第七章教材?跟着小编一起来看一看吧!
数据结构第七章教材
1、数据结构
1）线性结构（线性表，栈，队列等）
2）非线性结构：至少存在一个数据元素有不止一个直接前驱或后继（树，图等）
2、树的定义
1）树是n个数据元素的有限集（记为T）对任意一棵树T有：存在唯一一个称为根的数据元素；
2）当n>1时，其他数据元素可分为m（m>0）个互不相交的有限集T1，T2，.....,Tm，其中每个集合Ti（i=1，2，.....,m）本身又是一棵树，并称树Ti是根的子树.
3、树的表示法
1）分支图表示法
2）嵌套集合表示法
3）广义表表示法
4、树的基本术语
1）树的结点：包含一个DE和指向其子树的所有分支；
2）结点的度：一个结点拥有的子树的个数，度为零的结点称为叶结点；
3）树的度：树中所有结点的度的最大值Max（D（I）），含义：树中最大分支数为树的度
4）结点的层次及树的深度：根为第一层，根的孩子为第二层，如果结点为第k层，则其孩子为k 1层，树中结点的最大层次称为树的深度或高度
5）森林：是m（m≥0）棵互不相交的树的集合，森林与树概念相近，相互很容易转换。
5、树的基本运算
INITATE（T）初始化操作，创建一棵空树ROOT(T) 求根函数，求树T的根PARENT（T，x）求双亲函数，在树T中求x的双亲CHILD（T，x，i）求第i个孩子函数，在树T中求结点x的第i个孩子LSIBLING（T，x）求左兄弟函数，在树T中求x的左兄弟RSIBLING（T，x）求右兄弟函数，在树T中求x的右兄弟。CRT-TREE（x，F）建树函数，建立以结点x为根，森林F为子树的树。INS- CHILD（y，i，x）插入子树操作，将x作为y的第i根子树DEL-CHILD（x，i）删除子树操作，删除x的第i棵子树。TRAVERSE（T）遍历树操作，按顺序访问树T中各个结点。CLEAR（T）置空树操作，将树T置为空树。
6、除根没有双亲，其余的结点都有双亲。
7、二叉树
1）概念：二叉树是结点数为0或每个结点最多只有左右两颗子树的树。二叉树是一种特殊的树。特点：每个结点最多只有两棵子树，即不存在结点度大于2的结点；子树有左右之分，不能颠倒。
2）二叉树是有序树。
8、二叉树性质
1）在二叉树的第i层上至少有2（i-1） 方个结点（n≥1）
2)深度为k的二叉树至多有2（k-1）方个结点（k≥1）。（深度一定，二叉树的最大结点数也确定）
3）二叉树中，终端结点数n0与度为2的结点数n2有如下关系：n0=n2 1 除根结点外，每个结点都是另一结点的孩子。
9、满二叉树：深度为k，且有2（k-1）方个结点的二叉树
1）特点：每一层上结点数都达到最大， 度为1的结点n1=0 结点层序编号方法：从根结点起从上到下逐层（层内从左到右）对二叉树的结点进行连续编号。
10、完全二叉树：深度为k，结点数为n的二叉树，当且仅当每个结点的编号都与相同深度的满二叉树中从1到n的结点一一对应时，称为完全二叉树。
1）特点：每个结点i的左子树的深度Lhi-其结点i的右子树的深度Rhi等于0或1，即叶结点只可能出现在层次最大或次最大的两层上。
2）完全二叉树结点数n满足2（k-1）方-1≤2k方-1
3）满二叉树一定是完全二叉树，反之不成立。
4）含有n个结点的二叉链表中，有n 1个空链域。
11、遍历二叉树
1）遍历二叉树是指按一定的规律对二叉树的每个结点，访问且仅访问一次的处理过程。访问是一种抽象操作，是对结点的某种处理，例如可以是求结点的度、或层次、打印结点的信息，或做其他任何工作。一次遍历后，使树中结点的非线性排列，按访问的先后顺序变为某种线性排列。
2）遍历的次序：中序遍历，后序遍历，先序遍历
12、对于二叉树，结点只有一个孩子的时候也有左右之分的。
13、二叉树的存放采用的是二叉链表。
14、根结点先进栈，左结点紧跟根后面进栈，右结点在根出栈后入栈 每个结点都要进一次和出一次栈，并且总是访问栈顶元素。
15、线索二叉树
16、遍历中序线索二叉树
1）中序线索二叉树中，找结点的后继算法
17、遍历先序线索二叉树
1）先序线索二叉树中，找结点的后继算法 算法思想：对任意结点p 若p有左孩子，则后继为左孩子；若p无左孩子，有右孩子，则后继为右孩子；若p无左孩子，也无右孩子，则后继为右线索；
18、树变为二叉树的方法
1）在兄弟之间加一条线；
2）对每一个结点，只保留它与第一个孩子的连线，去掉与其他孩子的连线；
3）以树根为轴心，将整棵树顺时针旋转45度。
特点：根无右子树
19、森林与二叉树的对应关系
1）森林转换为二叉树的方法：将森林F={T1,T2....Tm}的各棵树分别转成二叉树BT1,BT2....BTm 将BTi 1作为BTi根结点的右子树（i=1，2，......,m 1）得到一颗BT
2）将当前根结点和其左子树作为森林的一棵树，并将其右子树作为森林的其他子树。
3）重复上面直到某结点的右子树为空。
20、哈夫曼树：是一类带权路径长度最短的树
1）概念：两结点间的路径：从一结点到另一结点所经过的结点序列
2）路径长度：路径上的分支数
3）树的路径长度：从根到每一结点的路径长度之和。
4）哈夫曼树为最优二叉树。
21、完全二叉树是路径长度最短的二叉树。
22、HT不唯一性，可能出现在1）构造新树时，左、右孩子未作规定。2）当有多个权值相同的树，可作有候选树时，选择谁未作规定。
