数据结构4

数据结构 4 字符串 树状结构

字符串实现方式

当然也有顺序实现和链接实现。顺序存储使用字符数组存储字符串。C语言中使用普通数组进行处理，将每个操作由一个函数实现，这些函数实现在ctring库中，但无法用运算符操纵字符串，还存在内存溢出的问题。而C++采用动态数组进行存储，实现了一个string类，根据字符串长度重新分配空间，解决了C语言存在的缺陷，但在时间性能上有所下降。

链接存储我们自然而然想到使用单链表，虽然在时间上有了很大优化，但空间利用率较低，于是我们可以考虑块状链表。我们允许一个结点存在空余空间。进行分裂结点和合并结点的操作。

树状结构——处理层次关系的数据结构

树是由n个结点组成的有限集合T，并且满足：
1.有一个根结点
2.其余结点分为m个集合，这些集合本身也是一棵树有些问题可以看成是树的结构，如八皇后问题（本质是DFS）

树有一些特殊的术语：

• 根结点、叶结点、内部结点

• 结点的度（一个结点的直接后继数）和树的度（结点的最大度）

• 儿子结点

• 父亲结点

• 兄弟结点

• 祖先结点

• 子孙结点

• 结点所处层次

• 树的高度（一棵树上最大的层次号）

• 有序树

• 无序树

• 森林

二叉树

满二叉树：任意一层的结点个数都达到了最大值完全二叉树：在满二叉树的最底层自右向左依次去掉若干结点

二叉树的性质：

• 第 i 层最多 2^(i - 1)个结点

• 高度为k，最多有2^k - 1个结点

• n0 = n2 + 1

• 具有n个结点的完全二叉树高度是[log_2 n] + 1

• 对于完全二叉树，左儿子为2i，右儿子为2i + 1

二叉树的运算

一个重要的操作：遍历前序遍历、中序遍历、后序遍历

如斐波那契数列的求解过程，我们采用后序遍历
再如快速排序过程，我们采用前序遍历（先进行划分）

前序+中序可以确定一棵二叉树后序+中序也可确定一棵二叉树但前序+后序不可确定一棵二叉树

二叉树的存储

把树的层次关系映射成线性关系，对于完全二叉树来说这是容易做到的，但对于非完全二叉树来说，就需要添加一些哑结点，把一棵普通的树修补成一棵完全二叉树（空间浪费）。更多情况下我们选择链接存储二叉树。标准形式：二叉链表（只存储儿子结点）广义的存储方式：三叉链表（2个儿子结点+父结点）

二叉树是递归定义的，所以操作可用递归实现，我们一般把这些递归函数设为二叉树类的私有成员函数。

二叉树的遍历操作可以采用递归实现前序：实现find(x) 查找操作中序 后序
层次（可用队列实现，回顾广搜BFS）递归实现：形式优美，易懂

成员函数实现

获得子结点

T lchild(T x,T flag){
    Node *tmp = find(x,root);
    if(tmp == nullptr || tmp -> left == nullptr){ //短路判别
        return flag;
    }
    return tmp -> left -> data;
}

创建一棵树可通过非递归实现（队列），也可通过递归实现

前序、中序、后序遍历的非递归实现——栈的模拟递归

（联系2025.03.16晚上机课）栈的模拟递归中元素为Data

struct Data{
    Node *p;//参数
    int pc;//程序计数器（核心数据）
};

为任务设定状态（也就是通过pc这一变量确认进行到哪一步了）

表达式树

中缀表达式
构建过程总结：顺序扫描中缀表达式直至结束

1. 运算数先检查当前的表达式树是否存在。如果不存在，则表示扫描到的是第一个运算数，将它作为树根。如果树存在，则将此运算数作为前一运算符的右孩子。

2. • & -
     运算优先级低，将它作为根结点，原来的树作为它的左子树
3. • & /
     与根结点比较：（1）如果根结点也是 * 或 /，则根结点先执行，故将当前运算符作为根结点，原来的树作为左子树；（2）如果根结点是 + 或 - ，则根结点应该后执行，所以将当前运算符作为右子树的根结点，原来的右子树作为新根结点的左子树。

括号的处理
用递归的观点看这个问题：将括号内的子表达式构建一棵子树作为整个表达式的一个运算数

表达式树类的设计——二叉链表

数据成员：指向根结点的指针结点类型：值的类型、值及左右指针公有成员函数：构造函数、result函数（后序遍历整棵树）私有成员函数：递归的create、带有递归参数的result函数、getToken（create函数的子函数，获取语法单位）

哈夫曼树

在计算机中，每个字符用一个编码来表示大多数编码系统都采用等长编码，如ASCII编码
前缀编码
字符只放在叶结点中，由于字符只放在叶结点中，所以每个字符的编码都不可能是其他字符编码的前缀。故前缀编码可被唯一解码！让出现频率高的字符拥有较短的编码可以节省空间，于是我们有了：
哈夫曼树！哈夫曼树是一棵最小代价的二叉树，在这棵树上，所有的字符都包含在叶结点上。要使得整棵树的代价最小，显然权值大的叶子应当尽量靠近树根，权值小的叶子可以适当离树根远一些。哈夫曼算法很巧妙：给定一个具有n个权值{ w1,w2,………wn }的结点的集合

1. F = { T1,T2,………Tn }

2. 初始时，设集合 A = F。

3. 执行 i = 1 至 n -1 的循环，在每次循环时执行以下操作:

• 从当前集合中选取权值最小、次最小的两个结点，以这两个结点作为内部结点 bi 的左右儿子，bi 的权值为其左右儿子权值之和。

• 在集合中去除这两个权值最小、次最小的结点，并将内部结点bi 加入其中。这样，在集合A中，结点个数便减少了一个。

这样，在经过了n-1 次循环之后，集合A中只剩下了一个结点，这个结点就是根结点。

哈夫曼树只有度数为0和2的结点，所以一棵哈夫曼树有2n-1个结点。由于编码的获得需要父结点信息，所以我们采用用数组表示的三叉链表。被编码元素存储在数组的后一半。哈夫曼树的生成是从右向左填写数组的前一半。特别注意的是：哈夫曼树的实现仍然是链接存储，不是顺序存储！（又不是完全二叉树，只是事先开好空间）

存储设计：

• 结点表示：结点的数据、权值和父结点和左右孩子的位置

• 哈夫曼树的存储：一个动态结点数组

操作：

• 构造函数：构建一棵哈夫曼树，给出节点数据数组，权值数组和数据个数

• 获取树上结点的哈夫曼编码，返回一个数组，数组的元素由数据和编码两部分组成的

树和森林（一般的树而非二叉树）

树的标准存储：除有数据字段外，还有K个指针字段（K为树的度数）广义标准存储：在标准形式的基础上，增加指向父亲结点的字段。

为了节省空间，我们可以采用孩子兄弟链表示法（用的最多的表示方法）左链：第一个儿子；右链：下一个兄弟

还有一种表示方法：双亲表示法
只记录每个结点的父结点位置