内容发布更新时间 : 2024/12/26 16:39:31星期一 下面是文章的全部内容请认真阅读。
补充重点：
1.空串和空白串有无区别？ 答：有区别。
空串(Null String)是指长度为零的串；
而空白串(Blank String),是指包含一个或多个空白字符‘ ’(空格键)的字符串.
2.“空串是任意串的子串；任意串S都是S本身的子串，除S本身外，S的其他子串称为S的真子串。”
第六章 树和二叉树 内容提要：
◆ 树是复杂的非线性数据结构，树，二叉树的递归定义，基本概念，术语。
树：由一个或多个(n≥0)结点组成的有限集合T，有且仅有一个结点称为根（root），当n>1时，其余的结点分为m(m≥0)个互不相交的有限集合T1,T2，?，Tm。每个集合本身又是棵树，被称作这个根的子树 。
二叉树：是n（n≥0）个结点的有限集合，由一个根结点以及两棵互不相交的、分别称为左子树和右子树的二叉树组成。 术语：P88
◆ 二叉树的性质，存储结构。
性质1: 在二叉树的第i层上至多有2i-1个结点（i>0）。 性质2: 深度为k的二叉树至多有2k-1个结点（k>0）。
性质3: 对于任何一棵二叉树，若2度的结点数有n2个，则叶子数（n0）必定为n2＋1 性质4: 具有n个结点的完全二叉树的深度必为 ?
性质5: 对完全二叉树，若从上至下、从左至右编号，则编号为i 的结点，其左孩子编号必为2i，其右孩子编号为2i＋1；其双亲的编号必为i/2（i＝1 时为根,除外）。 二叉树的存储结构： 一、顺序存储结构
按二叉树的结点“自上而下、从左至右”编号，用一组连续的存储单元存储。 若是完全/满二叉树则可以做到唯一复原。 不是完全二叉树：一律转为完全二叉树！
方法很简单，将各层空缺处统统补上“虚结点”，其内容为空。 缺点：①浪费空间；②插入、删除不便 二、链式存储结构
用二叉链表即可方便表示。一般从根结点开始存储。
优点：①不浪费空间；②插入、删除方便
◆ 二叉树的遍历。
指按照某种次序访问二叉树的所有结点，并且每个结点仅访问一次，得到一个线性序列。 遍历规则———
二叉树由根、左子树、右子树构成，定义为D、 L、R 若限定先左后右，则有三种实现方案：
DLR LDR LRD 先序遍历 中序遍历 后序遍历
◆ 树的存储结构，树、森林的遍历及和二叉树的相互转换。
回顾2：二叉树怎样还原为树？
要点：逆操作，把所有右孩子变为兄弟！ 讨论1：森林如何转为二叉树？
法一：① 各森林先各自转为二叉树；② 依次连到前一个二叉树的右子树上。 法二：森林直接变兄弟，再转为二叉树 讨论2：二叉树如何还原为森林？
要点：把最右边的子树变为森林，其余右子树变为兄弟 树和森林的存储方式： 树有三种常用存储方式：
①双亲表示法 ②孩子表示法 ③孩子—兄弟表示法
问：树→二叉树的“连线—抹线—旋转” 如何由计算机自动实现？ 答：用“左孩子右兄弟”表示法来存储即可。 存储的过程就是树转换为二叉树的过程！
树、森林的遍历：
① 先根遍历：访问根结点；依次先根遍历根结点的每棵子树。 ② 后根遍历：依次后根遍历根结点的每棵子树；访问根结点。 讨论：树若采用“先转换，后遍历”方式，结果是否一样？ 1. 树的先根遍历与二叉树的先序遍历相同； 2. 树的后根遍历相当于二叉树的中序遍历； 3. 树没有中序遍历，因为子树无左右之分。
① 先序遍历
若森林为空，返回；
访问森林中第一棵树的根结点；
先根遍历第一棵树的根结点的子树森林；
先根遍历除去第一棵树之后剩余的树构成的森林。 ② 中序遍历
若森林为空，返回；
中根遍历森林中第一棵树的根结点的子树森林； 访问第一棵树的根结点；
中根遍历除去第一棵树之后剩余的树构成的森林。
◆ 二叉树的应用：哈夫曼树和哈夫曼编码。
Huffman树：最优二叉树（带权路径长度最短的树） Huffman编码：不等长编码。 树的带权路径长度：
（树中所有叶子结点的带权路径长度之和）
构造Huffman树的基本思想：权值大的结点用短路径，权值小的结点用长路径。 构造Huffman树的步骤（即Huffman算法）：
(1) 由给定的 n 个权值{ w1, w2, ?, wn }构成n棵二叉树的集合F = { T1, T2, ?, Tn } （即森林） ，其中每棵二叉树 Ti 中只有一个带权为 wi 的根结点，其左右子树均空。
(2) 在F 中选取两棵根结点权值最小的树 做为左右子树构造一棵新的二叉树，且让新二叉树根结点的权值等于其左右子树的根结点权值之和。
(3) 在F 中删去这两棵树，同时将新得到的二叉树加入 F中。
(4) 重复(2) 和(3) , 直到 F 只含一棵树为止。这棵树便是Huffman树。 具体操作步骤：
学习重点：（本章内容是本课程的重点）
◆ 二叉树性质及证明方法，并能把这种方法推广到K叉树。
◆ 二叉树遍历，遍历是基础，由此导出许多实用的算法，如求二叉树的高度、各结点的层次数、度为0、1、2的结点数。
◆ 由二叉树遍历的前序和中序序列或后序和中序序列可以唯一构造一棵二叉树。由前序和后序序列不能唯一确定一棵二叉树。