第五章 串
串:串是由零个或多个字符组成的有限序列，又名叫字符串。
串中字符数目n称为串的长度。
零个字符的串称为空串。
串的比较是通过组成串的字符之间的编码来进行的，而字符的编码指的是字符在对应字符集中的序号。
常用的字符编码有ASCII 和Unicode。
第六章 树
树的定义：树是n(n>=0)结点的有限集。n=0时称为空树。在任意一颗非空树中：（1）有且只有一个特定的称为根（Root）的结点；（2）当n>1时，其余结点可分为m(m＞0)个互不相交的有限集T1，T2...Tn,其中每一个集合本省又是一棵树，并且称为根的子树（SubTree）。
注意：
（1）n>0时，根节点是唯一的；
（2）子树的个数没有限制，但是子树一定是互不相交的。下面两个图的结构都不是树。
结点的分类
结点拥有的子树数称为节点的度。度为0的结点成为叶结点或终端结点。度不为0的结点称为非终端结点或分支结点。除根节点外，分支结点也称为内部结点。树的度是树内各结点的度的最大值。
结点的层次
结点的层次从根开始定义起，根为第一层，根的孩子为第二层。树中结点最大的层次称为树的深度或高度。
如果将树中各结点的子树看成从左至右是有次序的，不能互换的，则称该树是有序树，否则称无序树。
森林是m(m>0)棵互不相交的树的集合。
线性表和树的异同点：
树的存储结构
1 双亲表示法
在每个结点中，附设一个指示器指示其双亲结点到链表中的位置。
注意双亲域，长子域和左右兄弟域的灵活运用。
2 孩子表示法
把每个结点的孩子结点排列起来，以单链表作为存储结构，则n个结点有n个孩子链表，如果是叶子结点则此单链表为空。然后n个头指针又组成一个线性表，采用顺序存储结构，放进一个一维数组中。
3 孩子兄弟表示法
任意一棵树，它的结点的第一个孩子如果存在就是唯一的，它的右兄弟如果存在也是唯一的。因此，我们设置两个指针，分别指向该节点的第一个孩子和此节点的右兄弟。
二叉树
定义：二叉树是n(n>=0)个结点的有限集合，该集合或者为空集（称为空二叉树），或者由一个根节点和两颗互不相交的，分别称为根节点的左子树和右子树的二叉树组成。
二叉树的特点：
1 每个结点最多有两颗子树。
2左子树和右子树是有顺序的，不能任意颠倒。
3 即使某个结点只有一颗子树，也要区分左右。
根据以上特点总结二叉树的五种基本形态：
1 空二叉树。
2只有一个根节点。
3根节点之后左子树。
4 根节点只有右子树。
5 根节点既有左子树，又有右子树。
斜树：所有结点都只有左子树的二叉树叫做左斜树，都只有右结点的二叉树叫做右斜树。
满二叉树：在一颗二叉树中，如果所有分支结点都存在左子树和右子树，并且所有叶子都在同一层上，这样的二叉树称为满二叉树。
完全二叉树：对一颗具有n个结点的二叉树按层序编号，如果编号为i(1<=i<=n)的结点与同样深度的满二叉树中编号为i的结点在二叉树中的位置完全相同，则这棵二叉树称为完全二叉树。
二叉树的性质
1 在二叉树的第i层上最多有2^(i-1)个结点 (i>=1)。
2 深度为k的二叉树最多有2^k -1个结点(k>=1)。
3 对于任何一颗二叉树T,如果其叶子结点数为n0,度为2的结点数为n2,则n0=n2+1。
4 具有n个结点的完全二叉树的深度为log2n+1。
二叉树的存储结构
顺序存储结构：一般只适用于完全二叉树，因为其他类型的二叉树会浪费大量的存储空间。
二叉链表：二叉树每个结点最多有两个孩子，所以为它设计一个数据域和两个指针域是比较自然的想法，我们称这样的链表叫做二叉链表。
二叉树的遍历：是指从根结点出发，按照某种次序依次访问二叉树中所有结点，使得每个结点被访问一次且仅被访问一次。
二叉树的遍历方法
1 前序遍历
规则：若二叉树为空，则空操作返回，否则先访问根节点，然后前序遍历左子树，再前序遍历右子树。
2 中序遍历
规则：若二叉树为空，则空操作返回，否则从根结点开始（注意并不是先访问根结点），中序遍历根结点的左子树，然后是访问根结点，最后中序遍历右子树。
3 后序遍历
规则：若二叉树为空，则空操作返回，否则从左到右先叶子后结点的方式遍历访问左右子树，最后访问根结点。
4 层序遍历
规则：若二叉树为空，则空操作返回，否则从树的第一层，也就是根结点开始访问，从上而下逐层遍历，在同一层中，按照从左到右的顺序对结点逐个访问。
二叉树遍历的性质：
1 已知前序和中序遍历序列可以唯一确定一颗二叉树。
2 已知后序和中序遍历序列可以唯一确定一颗二叉树。
线索二叉树
定义：每个结点都有一个指向前驱和后继的指针（线索），加上线索的二叉链表成为线索链表，相应的二叉树就称为下所二叉树。
其实线索二叉树就是把二叉树变成了一个双向链表。
在实际问题中，如果所用的二叉树需要经常遍历或查找结点时需要某种遍历序列中的前驱和后继，那么采用线索二叉树的结构就是非常不错的选择。
赫夫曼树的应用-文档压缩技术。
